洛谷 5110.块速递推

水经验(逃
这个东西为什么能有紫啊……
推个递推式也没紫吧,这个烂大街的 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
#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);
}