三校集训Part1 QZEZ Day6 B 题解
三校集训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;
}
腾讯云开发者
