正題

題目鏈接: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\le T\le 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_0{x}_0^n+c_1{x}_1^n$，那么帶入$a_0$和$a_1$就有
$$\{\begin{array}{c}{c}_0+c_1=0\\ c_0\frac{233+\sqrt{56953}}{2}+c_1\frac{233?\sqrt{56953}}{2}=1\end{array}$$
解出來有$c_0=\frac{1}{\sqrt{56953}},c_1=?\frac{1}{\sqrt{56953}}$。

這樣我們就可以$O(T\log n)$求答案了，但是還是不夠。

先根據歐拉定理讓$n$模上$\phi (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-块速递推【特征方程,分块】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。