洛谷 5110 块速递推

水经验（逃
这个东西为什么能有紫啊……
推个递推式也没紫吧，这个烂大街的 trick 也没紫吧（

无脑上生成函数啊（
设 F(x) 为 a 的生成函数，则 F(x)=233xF(x)+666x2F(x)+x(1−233x−666x2)F(x)=xF(x)=x1−233x−666x2

然后下一步就是得把这玩意部分分式展开。
大力待定系数设 1−233x−666x2=(1−ax)(1−bx)=1−(a+b)x+abx（逃
则有 {a+b=233ab=−666。
解得 {a=233+13√3372b=233−13√3372。

然后继续大力待定系数设 x1−233x−666x2=A1−ax+B1−bx。
解得 {A=113√337B=−113√337。
故 F(x)=113√337(11−ax−11−bx)。
又有 an=113√337[(233+13√3372)n−(233−13√3372)n]。

关于那个根号，似乎可以扩域做，不过 337 是有二次剩余的。
跑个二次剩余算法得到 2162841682≡7837158392≡337(mod(109+7))。
随便拿一个来算就是了。

然后看起来要 O(1) 询问。
问题相当于支持 O(1) 询问 ab，a 是常数，0≤b<109+7。
可以设一个块大小 W，预处理出 1,a,a2,a3,…,aW−1 和 1,aW,a2W,a3W,…,aW(W−1)。
则可支持 O(1) 查询 0≤b<W2 的 ab。
然后如果把 W 设成 2 的次幂的话可以减少除法和取模的常数（用位运算代替）。
学出题人取了 W=216=65536。

代码：

#include <cstdio>
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);
}