P5110 【块速递推】

太菜了，不会生成函数，于是用特征方程来写的这道题

首先我们知道，形如\(a_n=A*a_{n-1}+B*a_{n-2}\)的特征方程为\(x^2=A*x+B\)

于是此题的递推式就是：\(x^2=233x+666\)，即：\(x^2-233x-666=0\)

用求根公式解得：\(x_1=\dfrac{233+\sqrt{56953}}{2}, x_2=\dfrac{233-\sqrt{56953}}{2}\)

由于\(188305837≡\sqrt{56953}(mod\ 1e9+7)\)

所以变成：$x_1 = \(94153035\)‬$, \(x_2=905847205\)

跟据特征方程的结论：\(a_n=αx_1^n+β*x_2^n\)

因为\(a_0=0, a_1=1\)，所以有：

\(α+β=0\)

\(94153035*α+905847205*β=1\)

解得：\(α=\dfrac{1}{188305837}=233230706, β=-\dfrac{1}{188305837}=-233230706\)

所以\(a_n=233230706*94153035^n-233230706*905847205^n\)

由于询问较多，所以我们要用\(O(1)\)光速幂求解

\(Code:\)

#include<bits/stdc++.h>

using namespace std;

#define il inline

#define re register

il int read() {

    re int x = 0, f = 1; re char c = getchar();

    while(c < '0' || c > '9') { if(c == '-') f = -1; c = getchar();}

    while(c >= '0' && c <= '9') x = x * 10 + c - 48, c = getchar();

    return x * f;

}

#define rep(i, s, t) for(re int i = s; i <= t; ++ i)

#define maxn 300

const int mod = 1000000007;

const int x1 = 94153035, x2 = 905847205, a = 233230706;

int n, m, ans;

int f1[65540], f2[65540], f3[65540], f4[65540];

int g1[65540], g2[65540], g3[65540], g4[65540];

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;

}

il int mul(int a, int b) {

    return 1ll * a * b % mod;

}

il int qpow1(int x) {

    return mul(f1[x & 65535], f2[x >> 16]);

}

il int qpow2(int x) {

    return mul(g1[x & 65535], g2[x >> 16]);

}

int main() {

    f1[0] = g1[0] = 1;

    rep(i, 1, 65536) f1[i] = mul(f1[i - 1], x1), g1[i] = mul(g1[i - 1], x2);

	f2[0] = g2[0] = 1, f2[1] = f1[65536], g2[1] = g1[65536];

	rep(i, 2, 65536) f2[i] = mul(f2[i - 1], f2[1]), g2[i] = mul(g2[i - 1], g2[1]);

	int T = read(); init();

    while(T --) {

        n = (Rand()) % (mod - 1);

        ans ^= 1ll * a * (qpow1(n) - qpow2(n) + mod) % mod;

    }

    printf("%d", ans);

	return 0;

}

P5110 【块速递推】的相关教程结束。