题目链接：点击查看

题目大意：给出一段程序，进行优化后提交

题目分析：其实就是找规律，大水题一个，偶尔也是需要做做水题找找自信（逃）

先将题目中的程序拿下来，跑上100项，然后拿到oeis里找一下规律，就立马得到了递推式：

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; }

 

总结

以上是生活随笔为你收集整理的HDU - 4990 Reading comprehension(矩阵快速幂，水题)的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。