android开发分享HDU6185 Covering(矩阵快速幂+数学)

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.因为是矩阵乘法，所以一定要注意乘的顺序