HDU6185
递推式
思路:
知道递推式之后,这就变成了一道矩阵快速幂的板子题,个人认为这道题难就难在一开始的打表推公式
代码附:
#pragma GCC optimize("Ofast","inline","-ffast-math") #pragma GCC target("avx,sse2,sse3,sse4,mmx") #include<bits/stdc++.h> #define int long long using namespace std; const int N = 2e5+10; const int mod=1000000007 ; struct node { int a[5][5]; node() { memset(a,0,sizeof(a)); } inline void build() { for(int i=0; i<4; ++i) a[i][i]=1; } }; node operator *(const node &x,const node &y) { node z; for(int i=0; i<4; ++i) for(int j=0; j<4; ++j) for(int k=0; k<4; ++k) z.a[i][j]=(z.a[i][j]+x.a[i][k]*y.a[k][j]%mod)%mod; return z; } signed main() { ios::sync_with_stdio(false); cin.tie(0); int n; while(cin>>n) { node a,ans; if(n==1) { cout<<1<<endl; continue; } if(n==2) { cout<<5<<endl; continue; } if(n==3) { cout<<11<<endl; continue; } if(n==4) { cout<<36<<endl; continue; } ans.build(); a.a[0][0]=1,a.a[0][1]=1,a.a[1][0]=5,a.a[1][2]=1,a.a[2][0]=1,a.a[2][3]=1,a.a[3][0]=-1; n-=4; while(n) { if(n&1) ans=ans*a; n>>=1; a=a*a; } node b; b.a[0][0]=36,b.a[0][1]=11,b.a[0][2]=5,b.a[0][3]=1; ans=b*ans; cout<<(ans.a[0][0]+mod)%mod<<endl; } return 0; }
P.S.因为是矩阵乘法,所以一定要注意乘的顺序
本文来自网络收集,不代表计算机技术网立场,如涉及侵权请联系管理员删除。
ctvol管理联系方式QQ:251552304
本文章地址:https://www.ctvol.com/addevelopment/897432.html