Luogu5110 块速递推

题面

题解

线性常系数齐次递推sb板子题

$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^2 \equiv 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;

}

Luogu5110 块速递推的相关教程结束。