Description：

求广义斐波那契数列 $f(n)=233f(n-1)+666f(n-2)$ 第 $n$ 项的值。

要求 $O(1)$ 。

Solution：

上面那个数列的通项公式是： $$ f(n) \equiv 233230706×(94153035^{n}-905847205^{n}) \mod (10^9+7) $$ 由于费马小定理，指数不会超过 $1e9+6$ ，因此我们可以将 $a^n$ 分解为 $a^{k\times63356+r}$ ，预处理 $a$ 和 $a^{65536}$ 的 $1\sim 65536$ 次方，然后就可以 $O(1)$ 查询了。

然后考虑怎么得到上面那个通项公式，可以用 $OGF$ ，首先可以发现 $F(x)=\frac x{1-233x-666x^2}$ ，然后设方程 $1-233x-666x^2=0$ 的根为 $a,b$ ，那么： $$ \begin{align} F(x)&=\frac x{1-233x-666x^2}\\ &=\frac x{-666}\frac {1}{(x-a)(x-b)}\\ &=\frac x{-666(a-b)}\frac{(x-b)-(x-a)}{(x-a)(x-b)}\\ &=\frac x{-666(a-b)}\biggl(\frac1{b-x}-\frac1{a-x}\biggr)\\ &=\frac1{-666(a-b)}\biggl(\frac 1 b\frac x{1-\frac xb}-\frac 1a\frac x{1-\frac xa})\\ \end{align} $$ 由于： $$ \frac {kx}{1-kx}=\sum_{i\geqslant 1}k^ix^i $$ 因此： $$ F(x)=\sum_{i\geqslant 0}\biggl(\frac1{-666(a-b)}(\frac1{b^i}-\frac1{a^i})\biggr)\Rightarrow f_i=\frac1{-666(a-b)}(\frac1{b^i}-\frac1{a^i}) $$ 而： $$ a,b=\frac{233\pm\sqrt{56953}}{-1332} $$ 因此直接带入就可以得到上面那个式子了。

Code：

#include<bits/stdc++.h>

using namespace std;

int T;

#define MOD 1000000007

#define A 94153035

#define B 905847205

#define MAX 65536

struct powerdata

{

	int power1[MAX];

	int power2[MAX];

	void init(int k)

	{

		power1[0] = 1;

		for(register int i = 1;i < MAX;++i)power1[i] = 1ll * power1[i - 1] * k % MOD;

		k = 1ll * power1[MAX - 1] * k % MOD;

		power2[0] = 1;

		for(register int i = 1;i < MAX;++i)power2[i] = 1ll * power2[i - 1] * k % MOD;

		return;

	}

	inline int query(int k)

	{

		return 1ll * power2[k / MAX] * power1[k % MAX] % MOD;

	}

}p1,p2;

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;

	}

}

int main()

{

	scanf("%d",&T);

	Mker::init();p1.init(94153035);p2.init(905847205);

	register int ans = 0;

	for(register int i = 1;i <= T;++i)

	{

		register int n = Mker::rand() % (MOD - 1);

		ans ^= 233230706ll * (p1.query(n) - p2.query(n) + MOD) % MOD;

	}

	printf("%d\n",ans);

	return 0;

}