首页 > 代码库 > hdu 4686 矩阵乘法优化递推关系
hdu 4686 矩阵乘法优化递推关系
这里有一份解题报告
解题报告
这是理论知识:
点我
最主要的是构造乘法矩阵,这个是通过递推关系得到的。
有了它,求数列的第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 }
PS:杭电不支持long long lld 输出,(╯‵□′)╯︵┻━┻
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。