首页 > 代码库 > hdu 4686 矩阵乘法优化递推关系

hdu 4686 矩阵乘法优化递推关系

2024-07-08 21:49:18   216人阅读

这里有一份解题报告

解题报告

这是理论知识：

点我

最主要的是构造乘法矩阵，这个是通过递推关系得到的。

有了它，求数列的第n项可以在log(n)的时间里求出来。

 1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <set> 5 #include <algorithm> 6 #include <map> 7 #include<vector> 8 #define maxn 1010 9 #define mod 100000000710 using namespace std;11 typedef long long ll;12 struct Matrix{13     ll a[10][10];14 }res,A,F,ans,temp;15 Matrix mul(Matrix a,Matrix b){16     memset(temp.a,0,sizeof(temp.a));17     for(int i=0;i<5;++i){18         for(int j=0;j<5;++j){19             for(int k=0;k<5;++k){20                 temp.a[i][j]+=(a.a[i][k]*b.a[k][j])%mod;21                 temp.a[i][j]%=mod;22              }23         }24     }25     return temp;26 }27 void quick_pow(ll k){28     memset(res.a,0,sizeof(res.a));29     for(int i=0;i<5;++i)res.a[i][i]=1;30     while(k){31         if(k&1)res = mul(res,A);32         A = mul(A,A);33         k>>=1;34     }35 }36 int main (){37     ll  a0,ax,ay;38     ll b0,bx,by;39     ll n;40     ll f1,a1,b1,s0;41     while(cin>>n){42         cin>>a0>>ax>>ay;43         cin>>b0>>bx>>by;44         if(n==0){printf("0\n");continue;}45         a1 = ((a0*ax)%mod+ay)%mod;46         b1 = ((b0*bx)%mod+by)%mod;47         f1 = (a1*b1)%mod;48         s0 = (a0*b0)%mod;49         memset(A.a,0,sizeof(A.a));50         A.a[0][0]=(ax*bx)%mod;51         A.a[1][0]=(ax*by)%mod;52         A.a[2][0]=(ay*bx)%mod;53         A.a[3][0]=(ay*by)%mod;54         A.a[1][1]=ax%mod;55         A.a[3][1]=ay%mod;56         A.a[2][2]=bx%mod;57         A.a[3][2]=by%mod;58         A.a[3][3]=1;59         A.a[0][4]=1;60         A.a[4][4]=1;61         memset(F.a,0,sizeof(F.a));62         F.a[0][0]=f1%mod;63         F.a[0][1]=a1%mod;64         F.a[0][2]=b1%mod;65         F.a[0][3]=1;66         F.a[0][4]=s0%mod;67         quick_pow(n-1);68         ans=mul(F,res);69         printf("%lld\n",(ans.a[0][4])%mod);70     }71     return 0;72 }
View Code

PS：杭电不支持long long lld 输出，(╯‵□′)╯︵┻━┻


联系
我们