首页 > 代码库 > hdu 4965 Fast Matrix Calculation

hdu 4965 Fast Matrix Calculation

2024-07-18 14:28:46   226人阅读

直接按照题目上的做 A*B 形成一个N*N的矩阵C，再用C求其n*n次幂。这样果断超时啊。

看了题解（AB）^n 可以写成 A (BA)^(n-1) B ,  B*A 形成的矩阵就是K*K的，这里果断省了一大把时间啊，这么简单的变换为毛我们就是没想到 TAT 

 

 1 #include<iostream> 2 #include<cstdio> 3 #include<map> 4 #include<algorithm> 5 #include<cstring> 6 #define INF 9999999 7 using namespace std; 8 struct node 9 {10     int mat[1002][7];11 } a,b,c;12 13 14 node mul(node a,node b,int n,int m,int p)15 {16     node c;17     memset(c.mat,0,sizeof(c.mat));18     for(int i=0; i<n; i++)19         for(int j=0; j<m; j++)20             if(a.mat[i][j])21             {22                 for(int k=0; k<p; k++)23                     c.mat[i][k]=(c.mat[i][k]+a.mat[i][j]*b.mat[j][k])%6;24             }25     return c;26 }27 28 node solve(node a,int num,int n)29 {30     node b;31     memset(b.mat,0,sizeof(b.mat));32     for(int i=0; i<n; i++)33         b.mat[i][i]=1;34     while(num)35     {36         if(num%2)37             b=mul(b,a,n,n,n);38         a=mul(a,a,n,n,n);39         num/=2;40     }41     return b;42 }43 44 int main()45 {46     int n,m;47     while(~scanf("%d%d",&n,&m))48     {49         if(n==0&&m==0)50             break;51         for(int i=0; i<n; i++)52             for(int j=0; j<m; j++)53                 scanf("%d",&a.mat[i][j]);54 55         for(int i=0; i<m; i++)56             for(int j=0; j<n; j++)57                 scanf("%d",&b.mat[i][j]);58                 59         if(n==1)60             c=mul(a,b,n,m,m);61         else62         {63             c=mul(b,a,m,n,m);64             c=solve(c,n*n-1,m);65             66             c=mul(c,b,n,m,n);67             c=mul(a,c,n,m,n);68             69         }70         int ans=0;71         for(int i=0; i<n; i++)72             for(int j=0; j<n; j++)73                 ans+=c.mat[i][j];74         printf("%d\n",ans);75     }76     return 0;77 }

 


联系
我们