有这样一个小到大排列的无穷序列S：1, 2, 4, 5, 8……，其中任何一个数转为2进制不包括2个连续的1。给出一个长度为N的正整数数组A，A1, A2……An记录的是下标（下标从1开始）。求S[A1] Xor S[A2] Xor S[A3] ….. Xor S[An]的结果（Xor 为异或运算），由于该数很大，输出Mod 1000000007的结果。
例如：A = {1, 2, 3}，对应S[1] = 1, S[2] = 2, S[3] = 4。1 Xor 2 Xor 4 = 7。 Input 第1行：1个数N，表示数组A的长度(1 <= N <= 50000)。 第2 - N + 1行：每行一个数，对应数组A的元素A[i]（1 <= A[i] <= 10^18)。 Output 输出一个数，S[A1] Xor S[A2] Xor S[A3] ….. Xor S[An]的结果Mod 1000000007。 Input示例 3 1 2 3 Output示例 7
题解 发现数列与fib和2的幂有关，利用此规律二分判断每个数那几个位置上有1即可。
代码
#include<iostream> #include<cstdio> #include<cstring> #include<cstdlib> #include<set> #include<ctime> #include<vector> #include<cmath> #include<algorithm> #include<map> #define mod 1000000007 #define ll long long #define inf 1e9 using namespace std; inline ll read() { ll x=0LL,f=1LL;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } ll fib[100],fac[100]; int n,len,Xor[100]; void print() { int ans=0; for (int i=0;i<=len;i++) if (Xor[i]) ans=(ans+fac[i])%mod; printf("%d",ans); } int main() { fib[0]=fib[1]=1;fac[1]=2;fac[0]=1; for (int i=2;i<=88;i++) { fib[i]=fib[i-1]+fib[i-2]; fac[i]=(fac[i-1]<<1)%mod; } n=read(); for (int i=1;i<=n;i++) { ll x=read(); while (x) { int l=1,r=88; while (l!=r) { int mid=(l+r+1)>>1; if (fib[mid]<=x) l=mid;else r=mid-1; } x-=fib[l]; Xor[l-1]^=1; len=max(len,l-1); } } print(); return 0; }