Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 131072/131072 K (Java/Others) Total Submission(s): 170 Accepted Submission(s): 99
1 #include<iostream> 2 #include<cstring> 3 #include<cstdlib> 4 #include<cstdio> 5 #include<algorithm> 6 #include<cmath> 7 #include<queue> 8 #include<map> 9 10 #define N 1005 11 #define M 15 12 #define mod 6 13 #define mod2 100000000 14 #define ll long long 15 #define maxi(a,b) (a)>(b)? (a) : (b) 16 #define mini(a,b) (a)<(b)? (a) : (b) 17 18 using namespace std; 19 20 int n,k; 21 int a[N][10],b[10][N],d[10][10],f[N][10],g[N][N],h[N][N]; 22 int ans; 23 24 typedef struct{ 25 int m[10][10]; 26 } Matrix; 27 28 Matrix e,P; 29 30 Matrix I = {1,0,0,0,0,0,0,0,0,0, 31 0,1,0,0,0,0,0,0,0,0, 32 0,0,1,0,0,0,0,0,0,0, 33 0,0,0,1,0,0,0,0,0,0, 34 0,0,0,0,1,0,0,0,0,0, 35 0,0,0,0,0,1,0,0,0,0, 36 0,0,0,0,0,0,1,0,0,0, 37 0,0,0,0,0,0,0,1,0,0, 38 0,0,0,0,0,0,0,0,1,0, 39 0,0,0,0,0,0,0,0,0,1, 40 }; 41 42 Matrix matrixmul(Matrix aa,Matrix bb) 43 { 44 int i,j,kk; 45 Matrix c; 46 for (i = 1 ; i <= k; i++) 47 for (j = 1; j <= k;j++) 48 { 49 c.m[i][j] = 0; 50 for (kk = 1; kk <= k; kk++) 51 c.m[i][j] += (aa.m[i][kk] * bb.m[kk][j])%mod; 52 c.m[i][j] %= mod; 53 } 54 return c; 55 } 56 57 Matrix quickpow(int num) 58 { 59 Matrix m = P, q = I; 60 while (num >= 1) 61 { 62 if (num & 1) 63 q = matrixmul(q,m); 64 num = num >> 1; 65 m = matrixmul(m,m); 66 } 67 return q; 68 } 69 70 int main() 71 { 72 int i,j,o; 73 //freopen("data.in","r",stdin); 74 //scanf("%d",&T); 75 //for(int cnt=1;cnt<=T;cnt++) 76 //while(T--) 77 while(scanf("%d%d",&n,&k)!=EOF) 78 { 79 if(n==0 && k==0) break; 80 memset(d,0,sizeof(d)); 81 memset(f,0,sizeof(f)); 82 memset(g,0,sizeof(g)); 83 memset(h,0,sizeof(h)); 84 ans=0; 85 for(i=1;i<=n;i++){ 86 for(j=1;j<=k;j++){ 87 scanf("%d",&a[i][j]); 88 } 89 } 90 91 for(i=1;i<=k;i++){ 92 for(j=1;j<=n;j++){ 93 scanf("%d",&b[i][j]); 94 } 95 } 96 97 for(i=1;i<=k;i++){ 98 for(o=1;o<=k;o++){ 99 for(j=1;j<=n;j++){ 100 d[i][o]+=(b[i][j]*a[j][o])%6; 101 } 102 d[i][o]%=6; 103 P.m[i][o]=d[i][o]; 104 } 105 } 106 107 108 109 e=quickpow(n*n-1); 110 111 112 for(i=1;i<=n;i++){ 113 for(o=1;o<=k;o++){ 114 for(j=1;j<=k;j++){ 115 f[i][o]+=(a[i][j]*e.m[j][o])%6; 116 } 117 f[i][o]%=6; 118 } 119 } 120 121 for(i=1;i<=n;i++){ 122 for(o=1;o<=n;o++){ 123 for(j=1;j<=k;j++){ 124 g[i][o]+=(f[i][j]*b[j][o])%6; 125 } 126 g[i][o]%=6; 127 } 128 } 129 /* 130 for(i=1;i<=n;i++){ 131 for(o=1;o<=n;o++){ 132 for(j=1;j<=n;j++){ 133 h[i][o]+=(g[i][j]*g[j][o])%6; 134 } 135 h[i][o]%=6; 136 } 137 } 138 139 */ 140 141 for(i=1;i<=n;i++){ 142 for(o=1;o<=n;o++){ 143 ans+=g[i][o]; 144 } 145 } 146 printf("%d\n",ans); 147 148 } 149 150 return 0; 151 }
hdu 4965 矩阵快速幂 矩阵相乘性质,布布扣,bubuko.com
原文:http://www.cnblogs.com/njczy2010/p/3922956.html