題目鏈接：點擊查看

題目大意：給出一段程序，進(jìn)行優(yōu)化后提交

題目分析：其實就是找規(guī)律，大水題一個，偶爾也是需要做做水題找找自信（逃）

先將題目中的程序拿下來，跑上100項，然后拿到oeis里找一下規(guī)律，就立馬得到了遞推式：

F(n)=F(n-1)+2*F(n-2)+1

然后就是簡簡單單的矩陣快速冪了，寫一下矩陣然后直接上代碼了：

初始矩陣：（取n=3即可）

F(n-1)

F(n-2)

1

輔助矩陣：

1	1	0
2	0	0
1	0	1

答案矩陣：

F(n)

F(n-1)

1

因為我從n=3開始的，所以對n=1和n=2特判一下即可

一點坑都沒有的大水題。。上代碼：

#include<iostream> #include<cstdlib> #include<string> #include<cstring> #include<cstdio> #include<algorithm> #include<climits> #include<cmath> #include<cctype> #include<stack> #include<queue> #include<list> #include<vector> #include<set> #include<map> #include<sstream> #define Pi acos(-1.0) using namespace std;typedef long long LL;const int inf=0x3f3f3f3f;int mod;const int N=3;struct Ma {LL a[N][N];Ma(){memset(a,0,sizeof(a));}friend Ma operator*(const Ma& a,const Ma& b){Ma ans;for(int i=0;i<N;i++)for(int j=0;j<N;j++){ans.a[i][j]=0;for(int k=0;k<N;k++){ans.a[i][j]=(ans.a[i][j]+a.a[i][k]*b.a[k][j]%mod)%mod;}}return ans;} };Ma q_pow(Ma a,LL b) {Ma ans;for(int i=0;i<N;i++)ans.a[i][i]=1;while(b){if(b&1)ans=ans*a;a=a*a;b>>=1;}return ans; }int main() { // freopen("input.txt","r",stdin);int n;while(scanf("%d%d",&n,&mod)!=EOF){if(n==1){printf("%d\n",1%mod);continue;}else if(n==2){printf("%d\n",2%mod);continue;}Ma st;st.a[0][0]=2;st.a[0][1]=1;st.a[0][2]=1;Ma ans;ans.a[0][0]=1;ans.a[1][0]=2;ans.a[2][0]=1;ans.a[0][1]=1;ans.a[2][2]=1;ans=q_pow(ans,n-2);printf("%lld\n",(st*ans).a[0][0]);}return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的HDU - 4990 Reading comprehension(矩阵快速幂，水题)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。