题解 P5110 【块速递推】
xgzc
2019-01-08 10:52:11
这里给出一种使用特征方程解此题的方法
**Warning: 大波公式警告**
----
$a_n=233a_{n-1}+666a_{n-2}$的特征方程为
$$x^2=233x+666$$
$$x^2-233x+666=0$$
$$x_1=\frac{233+\sqrt{56953}}2,x_2=\frac{233-\sqrt{56953}}2$$
$$\therefore a_n=\alpha x_1^n+\beta x_2^n$$
$$\because a_0=0,a_1=1$$
$$\therefore \begin{cases} \alpha+\beta=0\\ \alpha x_1+\beta x_2=1 \end{cases}$$
$$\therefore \begin{cases} \alpha=\frac1{\sqrt{56953}} \\ \beta=-\frac1{\sqrt{56953}} \end{cases}$$
$$\therefore a_n=\frac1{\sqrt{56953}}\left(\left(\frac{233+\sqrt{56953}}2\right)^n-\left(\frac{233-\sqrt{56953}}2\right)^n\right)$$
$$\because 188305837 \equiv \sqrt{56953} \; (\text{mod}\;10^9+7)$$
$$\therefore a_n \equiv 233230706 \times\left(94153035^n-905847205^n\right)$$
求里面两个底数的$n$次方如何$O(1)$求？~~分段打表~~
设$f_1(n)=x^{65536n},f_2(n)=x^n$
则：
$$ x^n=f_1(n/65536)\times f_2(n\%65536) $$
就可以了。
复杂度$\text{O}(T)$，$T$是询问次数
### 代码
```cpp
#include<cstdio>
#include<cstring>
#include<cctype>
#include<algorithm>
#define RG register
namespace Maker
{
unsigned long long SA, SB, SC;
void init() { scanf("%llu%llu%llu", &SA, &SB, &SC); }
inline 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), alpha(233230706), x_1(94153035),
x_2(905847205), x_3(64353223), x_4(847809841);
const int maxn(65536 + 5);
int f_1[maxn], f_2[maxn], f_3[maxn], f_4[maxn], T, ans;
inline int Pow_1(int x) { return 1ll * f_3[x >> 16] * f_1[x & 65535] % Mod; }
inline int Pow_2(int x) { return 1ll * f_4[x >> 16] * f_2[x & 65535] % Mod; }
int main()
{
f_1[0] = f_2[0] = f_3[0] = f_4[0] = 1;
for(RG int i = 1; i < 65536; i++) f_1[i] = 1ll * f_1[i - 1] * x_1 % Mod;
for(RG int i = 1; i < 65536; i++) f_2[i] = 1ll * f_2[i - 1] * x_2 % Mod;
for(RG int i = 1; i < 65536; i++) f_3[i] = 1ll * f_3[i - 1] * x_3 % Mod;
for(RG int i = 1; i < 65536; i++) f_4[i] = 1ll * f_4[i - 1] * x_4 % Mod;
scanf("%d", &T); Maker::init(); unsigned long long n;
while(T--) n = Maker::rand() % (Mod - 1),
ans ^= 1ll * alpha * (Pow_1(n) - Pow_2(n) + Mod) % Mod;
printf("%d\n", ans);
return 0;
}
```