三校集训Part1 QZEZ Day6 B 题解

题意

一只萌萌的$ Galo $在沙滩上散步。突然,可怕的事情发生了!一只$ OvO $正在看着他!
为了逃脱被吃掉的命运,$Galo $稽中生智,扔出了自己研究了很久的一道题给昆西:
斐波那契数列是这样的一个数列
$F_0 = 1, F_1 = 2$
$F_i = F_{i−1} + F_{i−2}$
对于一个数,Galo 定义它的斐波那契表示为将其表示为一些斐波那契数的和, 并将其转化为二进制数。
例如 $G(9) = G(8 + 1) = G(F4 + F0) = (10001)_2 = 16 + 1 = 17$
那么$ 9 $就可以表示为$10001$。注意到这种表示并不是唯一的,例如$9$也可以表示为$ 1101$。为了使这种表
示唯一,$Galo $决定使用如下程序来得出表示

int decompose (n) {
    ans = 0
    while (n) {
        f i n d the l a r g e s t F[ i ] <= n
        ans |= (1 << i )
        n = n − F[ i ]
    }
    return ans
}

那么这样就可以使每个数有唯一的表示了!例如$ G(30) = (1010001)_2 = 64 + 16 + 1 = 81$
现在$ Galo $给出了一个区间$ [A, B]$, 他想知道$ G(A) \text{ xor } G(A + 1) .. \text{ xor } G(B – 1) \text{ xor } G(B) $是多少
昆西当然不知道怎么做了啊!这个问题就交给你了!
答案对$10^9+7$取模。
$A,B\leq 10^{15}$

思路

首先发现$A,B$范围很大,考虑使用异或前缀和。
那么答案就是$Ans_B \text{ xor } Ans_{A-1}$
定义$F(x)$表示$G(1) \text{ xor } G(2) \text{ xor }…\text{ xor } G(x)$
记$ P[i] = F({Fib}_i − 1)$
对于求一般的$ F(n)$, 对于求考虑逐位确定答案。
记$ i $为最大的$ Fib $数,满足$ {Fib}_i ≤ x$
那么第$ i $位的答案只与$ n − F ibi + 1 $的奇偶性有关
用$C++STL$中$bitset$实现

Code

顺便介绍一下$bitset$
常见操作有:位运算、$set$(将某位改为1),$reset$(将某位改为0),$flip$将某位取反。

#include<algorithm>
#include<bitset>
#include<complex>
#include<deque>
#include<exception>
#include<fstream>
#include<functional>
#include<iomanip>
#include<ios>
#include<iosfwd>
#include<iostream>
#include<istream>
#include<iterator>
#include<limits>
#include<list>
#include<locale>
#include<map>
#include<memory>
#include<new>
#include<numeric>
#include<ostream>
#include<queue>
#include<set>
#include<sstream>
#include<stack>
#include<stdexcept>
#include<streambuf>
#include<string>
#include<typeinfo>
#include<utility>
#include<valarray>
#include<vector>
#include<cctype>
#include<cerrno>
#include<cfloat>
#include<ciso646>
#include<climits>
#include<clocale>
#include<cmath>
#include<csetjmp>
#include<csignal>
#include<cstdarg>
#include<cstddef>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<ctime>
#define mod 1000000007
#define int long long
#define S bitset<105>
using namespace std;
inline int read(){
    int res=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') res=res*10+ch-'0',ch=getchar();
    return res*f;
}
inline void write(int x){
    if(x<0) putchar('-'),x=-x;
    if(x<10) putchar(x+'0');
    else{
        write(x/10);
        putchar(x%10+'0');
    }
}
//queue<int> q;
//set<int> s;
//priority_queue<int> q1;
//priority_queue<int,vector<int>,greater<int> > q2;
//list<int> l;
//stack<int> s;
int fib[110],P[88],V,A,B,ans;
S f[110],Ans;
void Print(S n){
    ans=0;for(int i=80;i>=0;i--) ans=(ans*2+n.test(i))%mod;
    write(ans);
}
S Get(int x){
    if(x==0){S s;s.reset();return s;}
    for(int i=80;i>=0;i--){
        if(fib[i]>x) ;
        else{
            S s;s.reset();
            s=f[i]^Get(x-fib[i]);
            if((x-fib[i]+1)&1==1) s.flip(i);
            return s;
        }
    }
}
signed main(){
    fib[0]=1;fib[1]=2;
    for(int i=2;i<=80;i++){
        fib[i]=fib[i-1]+fib[i-2];
    }
    f[0].reset();f[1].set(0);
    for(int i=2;i<=80;i++){
        f[i]=f[i-1]^f[i-2];
        if((fib[i]-fib[i-1])&1==1) f[i].flip(i-1);
    }
    A=read();B=read();
    Ans=Get(B)^Get(A-1);
    Print(Ans);putchar('\n');
    return 0;
}

暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇