這道題的暴力分還是很良心嘛~~~~~

直接剛的話我發現本蒟蒻只會暴力，矩乘根本寫不出來，然后讓我們找一下規律，我們發現如果我們把這個序列在mod k的意義下擺出，并且在此過程中把值為1的的數減一，我們發現他可以成為一段一段的被0(我們在此只關注減1變為0的點)區間，我們繼續分析我們分析出來了這樣的性質：如果存在這樣的點，那么他右邊的點一定是兩個重復的數，而且往后是fibonacci數列（重頭開始）乘第一個數，那么他之后再出現這樣的0，的充要條件是其后存在一個fibonacci數是這段數第一個數的逆元。

我們先介紹一個結論（本蒟蒻并不會證）：斐波那契數列模k后一定是0,1,1開頭的純循環，而且這個循環節的長度≤6k。我們開一個數組vis[i]表示第一個在mod k意義下值為i的fibonacci數的位置，這樣我們求出某個數的逆元就知道以這個數為首項的數段的長度了（這樣我們就可以跳啦）。

現在我說一下到了現在我們做了什么，我們發現在mod k 的意義下，這個數列會是一個由0（再次強調我們在此只關注減1變為0的點）隔開散區間（一整個也算）開頭，之后要么成為循環，要么不再有0。先解釋成為循環：因為我們在mod k的意義下因此最多不過k個數段就可以找到循環。我們再解釋一下不在有0，這個就是當這個數段的第一項在mod k的意義下沒有逆元，或者有逆元但是找不到vis[]。

現在我們用k再乘一個不大的數的時間復雜度找出來我們要處理的假fibonacci在哪些位置減一，以及他到底是存在循環節還是到后來沒有了0，現在我們就可以想到一些矩陣，進行操作，但是這些矩陣一定要滿足可乘。對于循環節我們暴力處理兩邊和一個循環節，對于最后沒有0，我們就在后面直接fibonacci。

坑：I.via[1]!=1！！！！我們要找的是他后面第一個1，而我們前兩個數是受法律保護的。

　　II.對于處理一段一段的,最后一段可能頂到n，不滿

　　|||.一定要注意矩陣乘沒有交換律

#include <cstdio> #include <cmath> #include <cstring> #include <iostream> using namespace std; typedef long long LL; const LL N=1000010; LL n,k,p,vis[N],f[N*6],Ola,Stop,L,R,pos[N]; LL a[4][4],b[4][4],temp_ab[4][4],F[4],temp_F[4],S[4][4]; bool huzhi[N]; LL GCD(LL x,LL y){return x==0?y:GCD(y%x,x); } inline LL Min(LL x,LL y){return x<y?x:y; } inline void get_Ola(){LL lim=(LL)sqrt(k+0.5);LL x=k;Ola=k;for(LL i=2;i<=lim;i++)if(x%i==0){Ola=Ola/i*(i-1);while(x%i==0)x/=i;}if(x!=1){Ola=Ola/x*(x-1);} } //*******************GCD&&Ola*********************// inline void Multi_One(){memset(temp_F,0,sizeof(temp_F));for(int i=1;i<=3;i++)for(int j=1;j<=3;j++)temp_F[i]=(temp_F[i]+F[j]*a[j][i]%p+p)%p;memcpy(F,temp_F,sizeof(F)); } inline void Multi_Two(){memset(temp_ab,0,sizeof(temp_ab));for(int i=1;i<=3;i++)for(int j=1;j<=3;j++)for(int l=1;l<=3;l++)temp_ab[i][j]=(temp_ab[i][j]+a[i][l]*a[l][j]%p+p)%p;memcpy(a,temp_ab,sizeof(a)); } inline void Multi_Three(){memset(temp_F,0,sizeof(temp_F));for(int i=1;i<=3;i++)for(int j=1;j<=3;j++)temp_F[i]=((temp_F[i]+F[j]*b[j][i]%p)%p+p)%p;memcpy(F,temp_F,sizeof(F)); } inline void Multi_Four(){memset(temp_ab,0,sizeof(temp_ab));for(int i=1;i<=3;i++)for(int j=1;j<=3;j++)for(int l=1;l<=3;l++)temp_ab[i][j]=(temp_ab[i][j]+S[i][l]*a[l][j]%p+p)%p;memcpy(S,temp_ab,sizeof(S)); } inline void Multi_Five(){memset(temp_ab,0,sizeof(temp_ab));for(int i=1;i<=3;i++)for(int j=1;j<=3;j++)for(int l=1;l<=3;l++)temp_ab[i][j]=(temp_ab[i][j]+a[i][l]*a[l][j]%p)%p;memcpy(a,temp_ab,sizeof(a)); } inline void Multi_Six(){memset(temp_ab,0,sizeof(temp_ab));for(int i=1;i<=3;i++)for(int j=1;j<=3;j++)for(int l=1;l<=3;l++)temp_ab[i][j]=(temp_ab[i][j]+S[i][l]*b[l][j]%p+p)%p;memcpy(S,temp_ab,sizeof(S)); } inline void Multi_Seven(){memset(temp_F,0,sizeof(temp_F));for(int i=1;i<=3;i++)for(int j=1;j<=3;j++)temp_F[i]=(temp_F[i]+F[j]*S[j][i]%p+p)%p;memcpy(F,temp_F,sizeof(F)); } inline void Multi_E(){memset(temp_ab,0,sizeof(temp_ab));for(int i=1;i<=3;i++)for(int j=1;j<=3;j++)for(int l=1;l<=3;l++)temp_ab[i][j]=(temp_ab[i][j]+S[i][l]*S[l][j]%p+p)%p;memcpy(S,temp_ab,sizeof(S)); } //*********************Multi**********************// inline LL Pow(LL x,LL y,LL P){LL ans=1;while(y){if(y&1)ans=ans*x%P;y>>=1,x=x*x%P;}return ans; } inline void POW(int step){while(step){if(step&1)Multi_Seven();step>>=1,Multi_E();} } //**********************POW***********************// inline void Stop_Forever(){LL now=1,step=1;while(1){if(step>=n){Stop=n;break;}if(pos[now]){L=pos[now],R=step-1;break;}pos[now]=step;if(huzhi[now]==0){Stop=step-1;break;}LL Now=Pow(now,Ola-1,k);if(vis[Now]==0){Stop=step-1;break;}step+=vis[Now];now=f[vis[Now]-1]*now%k;} } //*********************Judge*********************// inline void F_H(){f[1]=1,f[2]=1;for(int i=3;i<=6*k;i++)f[i]=(f[i-1]+f[i-2])%k,vis[f[i]]=vis[f[i]]==0?i:vis[f[i]];for(int i=1;i<k;i++)if(GCD(i,k)==1)huzhi[i]=1; } inline void Pre(){b[1][1]=1;b[2][2]=1;b[3][2]=-1,b[3][3]=1;F[1]=0,F[2]=F[3]=1; } inline void Init(){scanf("%lld%lld%lld",&n,&k,&p);F_H();get_Ola();Stop_Forever();Pre(); } //***********************Pre**********************// inline void GO(LL step){memset(a,0,sizeof(a));a[1][2]=1;a[2][1]=1,a[2][2]=1;a[3][3]=1;while(step){if(step&1)Multi_One();step>>=1,Multi_Two();} } inline void GO_ON(int step){memset(a,0,sizeof(a));a[1][2]=1;a[2][1]=1,a[2][2]=1;a[3][3]=1;while(step){if(step&1)Multi_Four();step>>=1,Multi_Five();} } inline void Get_Boss(LL &now,LL &step){S[1][1]=1;S[2][2]=1;S[3][3]=1;while(step<R){LL Now=Pow(now,Ola-1,k);LL y=vis[Now];if(!step)y--;GO_ON(y);if(!step)y++;step+=y;Multi_Six();now=f[vis[Now]-1]*now%k;} } //****************Carry On******************// inline void Work_Stop(){LL now=1,step=0;while(step<Stop){LL Now=Pow(now,Ola-1,k);LL y=Min(n-step,vis[Now]);if(!step)y--;GO(y);if(!step)y++;step+=y;if(y==vis[Now])Multi_Three();now=f[vis[Now]-1]*now%k;}GO(n-step);printf("%lld",F[2]); } inline void Work_Forever(){LL now=1,step=0;while(step<L-1){LL Now=Pow(now,Ola-1,k);LL y=vis[Now];if(!step)y--;GO(y);if(!step)y++;step+=y;Multi_Three();now=f[vis[Now]-1]*now%k;}Get_Boss(now,step);POW((n-L+1)/(R-L+1));step=(n-L+1)/(R-L+1)*(R-L+1)+L-1;while(step<n){LL Now=Pow(now,Ola-1,k);LL y=Min(n-step,vis[Now]);GO(y);step+=y;if(y==vis[Now])Multi_Three();now=f[vis[Now]-1]*now%k;}printf("%lld",F[2]); } //*********************War*****************// int main(){Init();if(Stop)Work_Stop();else Work_Forever();return 0; }

?

轉載于:https://www.cnblogs.com/TSHugh/p/7287274.html

總結

以上是生活随笔為你收集整理的【BZOJ 2432】 [Noi2011]兔农 矩乘+数论的全部內容，希望文章能夠幫你解決所遇到的問題。

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