水经验（逃
这个东西为什么能有紫啊……
推个递推式也没紫吧，这个烂大街的 trick 也没紫吧（
无脑上生成函数啊（
设 \(F(x)\) 为 \(a\) 的生成函数，则 \[
\begin{aligned}
F(x) &= 233xF(x) + 666x^2F(x) + x \\
(1-233x-666x^2)F(x) &= x \\
F(x) &= \frac x{1-233x-666x^2}
\end{aligned}
\]
然后下一步就是得把这玩意部分分式展开。
大力待定系数设 \(1-233x-666x^2=(1-ax)(1-bx)=1-(a+b)x+abx\)（逃
则有 \(\begin{cases}a+b=233\\ab=-666\end{cases}\)。
解得 \(\begin{cases}a=\frac{233+13\sqrt{337}}2\\b=\frac{233-13\sqrt{337}}2\end{cases}\)。
然后继续大力待定系数设 \(\frac x{1-233x-666x^2}=\frac A{1-ax} + \frac B{1-bx}\)。
解得 \(\begin{cases}A=\frac1{13\sqrt{337}}\\B=-\frac1{13\sqrt{337}}\end{cases}\)。
故 \(F(x) = \frac1{13\sqrt{337}}(\frac1{1-ax}-\frac1{1-bx})\)。
又有 \(a_n = \frac1{13\sqrt{337}}[(\frac{233+13\sqrt{337}}2)^n-(\frac{233-13\sqrt{337}}2)^n]\)。
关于那个根号，似乎可以扩域做，不过 \(337\) 是有二次剩余的。
跑个二次剩余算法得到 \(216284168^2 \equiv 783715839^2 \equiv 337 \pmod {(10^9+7)}\)。
随便拿一个来算就是了。
然后看起来要 \(O(1)\) 询问。
问题相当于支持 \(O(1)\) 询问 \(a^b\)，\(a\) 是常数，\(0 \le b < 10^9+7\)。
可以设一个块大小 \(W\)，预处理出 \(1,a,a^2,a^3,\ldots,a^{W-1}\) 和 \(1,a^W,a^{2W},a^{3W},\ldots,a^{W(W-1)}\)。
则可支持 \(O(1)\) 查询 \(0\le b < W^2\) 的 \(a^b\)。
然后如果把 \(W\) 设成 \(2\) 的次幂的话可以减少除法和取模的常数（用位运算代替）。
学出题人取了 \(W=2^{16}=65536\)。
代码： 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
using namespace std;
namespace Mker
{
unsigned long long SA,SB,SC;
void init(){scanf("%llu%llu%llu",&SA,&SB,&SC);}
unsigned long long rand()
{
SA^=SA<<32,SA^=SA>>13,SA^=SA<<1;
unsigned long long t=SA;
SA=SB,SB=SC,SC^=t^SA;return SC;
}
}
const int mod = 1e9 + 7;
const int w[] = {233230706,94153035,64353223,905847205,847809841};
const int W = 65536;
int T,n;
int pw[5][W],ans;
int main()
{
pw[1][0] = pw[2][0] = pw[3][0] = pw[4][0] = 1;
for(register int i = 1;i <= 4;++i)
for(register int j = 1;j < W;++j)
pw[i][j] = (long long)pw[i][j - 1] * w[i] % mod;
scanf("%d",&T),Mker::init();
for(;T;--T)
n = Mker::rand() % (mod - 1),ans ^= w[0] * ((long long)pw[1][n & (W - 1)] * pw[2][n >> 16] % mod - (long long)pw[3][n & (W - 1)] * pw[4][n >> 16] % mod + mod) % mod;
printf("%d\n",ans);
}