1 条题解
-
0
首先推一下 的通项式。
搞一个生成函数
然后直接就列方程
得到
设
解方程，然后就可以得到 的通项式了。
然后算一下二次剩余，问题变成了求
发现快速幂是 的，会爆炸。
考虑分块一下，把 拆成 和 ，相当于 进制快速幂。
时就是 的了，就过了。
代码
#include<bits/stdc++.h> using namespace std; typedef unsigned long long ull; const int mod=1e9+7,Inv=233230706,S=1e5; namespace Mker{ ull SA,SB,SC; void init(){scanf("%llu%llu%llu",&SA,&SB,&SC);} int rand(){ SA^=SA<<32,SA^=SA>>13,SA^=SA<<1; ull t=SA; SA=SB,SB=SC,SC^=t^SA;return SC%(mod-1);//注意费马小定理 } } int cnt[5][S+5],Q,ans; void work(){ cnt[1][0]=cnt[2][0]=1; for(int i=1;i<=S;i++)cnt[1][i]=cnt[1][i-1]*94153035ll%mod,cnt[2][i]=cnt[2][i-1]*905847205ll%mod; cnt[3][0]=cnt[4][0]=1; for(int i=1;i<=S;i++)cnt[3][i]=1ll*cnt[3][i-1]*cnt[1][S]%mod,cnt[4][i]=1ll*cnt[4][i-1]*cnt[2][S]%mod; } int kuai(int a,int b){return 1ll*cnt[a+2][b/S]*cnt[a][b%S]%mod;} int solve(int n){return 1ll*Inv*(kuai(1,n)-kuai(2,n)+mod)%mod;} int main(){ scanf("%d",&Q); Mker::init(); work(); while(Q--)ans^=solve(Mker::rand()); printf("%d",ans); }
- 1
