题解 P5110 【块速递推】

· · 题解

这里给出一种使用特征方程解此题的方法

Warning: 大波公式警告

$$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是询问次数

代码

#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;
}