题意
一只萌萌的$ 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 $决定使用如下程序来得出表示
1
2
3
4
5
6
7
8
9
| 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$将某位取反。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
| #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');
}
}
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;
}
|