hdu 4686 矩阵乘法优化递推关系-白红宇

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

阅读量：6239 次

发布时间：2019-06-22

本文共 1665 字，大约阅读时间需要 5 分钟。

这里有一份解题报告

这是理论知识：

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

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

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 #include 
         
           5 #include 
          
            6 #include 
            7 #include
            
              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 }