洛谷 P5110 块速递推
题意简述
已知 \(a_n=233a_{n-1}+666a_{n-2},a_0=0,a_1=1\)
有 \(5\times 10^7\) 组询问，求 \(a_n\) 模 \(10^9+7\) 的值
题解思路
必须要 \(O(1)\) 实现
设 \(a_n=c\cdot q^n\)，
则 $ c \cdot q^n=233c \cdot q^{n-1}+666c \cdot q^{n-2}$
化简后得 \(q^2-233q-666=0\)，解得 \(q_1= \frac{233+\sqrt{56953}}{2}\)，\(q_2= \frac{233-\sqrt{56953}}{2}\)
然后可以发现 \(\sqrt{56953}\) 在模 \(10^9+7\) 意义下恰好等于 \(188305837\)
在模意义下 \(q_1=94153035\)，\(q_2=905847205\)
所以 \(a_n=c_1\cdot q_1^n-c_2\cdot q_2^n\)，将 \(a_0=0,a_1=1\)带入，
即 \(\begin{cases} c_1-c_2=0 \\ c_1\cdot q_1-c_2\cdot q_2=1\end{cases}\) 解得 \(c_1=c_2=\frac{1}{q1-q2}\) 在模意义下即 \(233230706\)
所以 \(a_n=233230706\times(94153035^n-905847205^n)\)
此时用快速幂仍然会T，由于底数固定，所以可以分块。
取\(S=\lceil\sqrt{n_{max}}\rceil\)，这里为了方便取 \(S=2^{16}=65536\)
对于每一个\(n\)，都可以表示为\(k\cdot S+r,k∈[0,S),r∈[0,S)\)
所以分别预处理出 \(f_1[k]=q_1^k,k\in[0,S)\) 和 \(f_2[k]=q_1^{k\cdot S},k\in[0,S)\),则\(q^n=f_1[n/S]*f2[n\%S]=f_1[n>>16]*f1[n\&S]\)。
\(q_2\)同理，这样就可以\(O(1)\)求出答案
代码
#include <cstdio>
#define ll long long
#define ull unsigned ll
const int mod=1e9+7,S=65535,c1=94153035,c2=905847205,c3=233230706;
int T,ans;
ll f11[S+5]={1},f12[S+5]={1},f21[S+5]={1},f22[S+5]={1};
ull SA,SB,SC,t;
inline ull rnd() {
SA^=SA<<32,SA^=SA>>13,SA^=SA<<1;
t=SA,SA=SB,SB=SC; return SC^=t^SA;
}
int main() {
scanf("%d%llu%llu%llu",&T,&SA,&SB,&SC);
for (int i=1;i<=S;++i) f11[i]=f11[i-1]*c1%mod,f21[i]=f21[i-1]*c2%mod;
const int x1=f11[S]*c1%mod,x2=f21[S]*c2%mod;
for (int i=1;i<=S;++i) f12[i]=f12[i-1]*x1%mod,f22[i]=f22[i-1]*x2%mod;
for (;T;--T) {
t=rnd()%(mod-1); const int t1=t&S,t2=t>>16;
ans^=((f11[t1]*f12[t2]-f21[t1]*f22[t2])%mod+mod)*c3%mod;
}
printf("%d\n",ans);
}