正题

题目链接:https://www.luogu.com.cn/problem/P5110

---

题目大意

数列\(a\)满足

\[a_n=233a_{n-1}+666a_{n-2},a_0=0,a_1=1
\]

\(T\)组询问给出\(n\)求\(a_n\)

\(1\leq T\leq 5\times 10^7\)，\(n\)在\(\text{unsigned long long}\)范围内

---

解题思路

上面那个递推式的特征方程就是\(x^2-233x-666\)，直接带式子解出来\(x_0=\frac{233+\sqrt{56953}}{2},x_1=\frac{233-\sqrt{56953}}{2}\)。

然后设\(a_n=c_0x_0^n+c_1x_1^n\)，那么带入\(a_0\)和\(a_1\)就有

\[\left\{\begin{matrix}c_0+c_1=0\\c_0\frac{233+\sqrt{56953}}{2}+c_1\frac{233-\sqrt{56953}}{2}=1\end{matrix}\right.
\]

解出来有\(c_0=\frac{1}{\sqrt{56953}},c_1=-\frac{1}{\sqrt{56953}}\)。

这样我们就可以\(O(T\log n)\)求答案了，但是还是不够。

先根据欧拉定理让\(n\)模上\(\varphi(P)\)缩小范围

然后分块处理快速幂，处理出\(x^i\)和\(x^{i\sqrt P}(i\in[0,\sqrt P])\)，这个是\(O(\sqrt P)\)的，然后每次把\(n\)分为整块的成上末尾的就好了。

时间复杂度\(O(\sqrt P+T)\)

---

code

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<cmath>

#define ll long long

using namespace std;

const ll P=1e9+7,Phi=P-1;

const ll sq=188305837,T=32000;

ll Q,n,p0[T+1],p1[T+1],P0[T+1],P1[T+1],ans;

ll pw0(ll x){return P0[x/T]*p0[x%T]%P;}

ll pw1(ll x){return P1[x/T]*p1[x%T]%P;}

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%Phi;

	}

}

signed main()

{

	ll inv2=(P+1)/2;

	ll x0=(233+sq)*inv2%P,x1=(P+233-sq)*inv2%P;

	p0[0]=p1[0]=P0[0]=P1[0]=1;

	for(ll i=1;i<=T;i++)

		p0[i]=p0[i-1]*x0%P,p1[i]=p1[i-1]*x1%P;

	for(ll i=1;i<=T;i++)

		P0[i]=P0[i-1]*p0[T]%P,P1[i]=P1[i-1]*p1[T]%P;

	ll inv=233230706,c0=inv,c1=P-inv;

	scanf("%lld",&Q);Mker::init();

	while(Q--){

		n=Mker::rand();

//		scanf("%lld",&n);ans=0;

		ans^=(c0*pw0(n)+c1*pw1(n))%P;

//		printf("%lld\n",ans);

	}

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

}

P5110-块速递推【特征方程,分块】的相关教程结束。