hdu 4965 Fast Matrix Calculation (矩阵快速幂，2014多校#9)
题目链接
题意：Step 1: Calculate a new NN matrix C = AB. Step 2: Calculate M = C^(N*N). Step 3: For each element x in M, calculate x % 6. All the remainders form a new matrix M’. Step 4: Calculate the sum of all the elements in M’.
思路： 水题。。就一个trick...
朴素的矩阵乘法的复杂度是n^3的。。。按照题目的顺序求的话。。。。求M矩阵时会超时。。。（而且1000*1000的数组也不能放到结构体里...?
我们可以根据矩阵乘法的结合律。
M = (AB)^(NN) = A * (BA)^(NN-1) * B
然后就可以搞了。
1/* ***********************************************
2Author :111qqz
3Created Time :Wed 19 Oct 2016 08:39:49 PM CST
4File Name :code/hdu/4965.cpp
5************************************************ */
6#include <cstdio>
7#include <cstring>
8#include <iostream>
9#include <algorithm>
10#include <vector>
11#include <queue>
12#include <set>
13#include <map>
14#include <string>
15#include <cmath>
16#include <cstdlib>
17#include <ctime>
18#define fst first
19#define sec second
20#define lson l,m,rt<<1
21#define rson m+1,r,rt<<1|1
22#define ms(a,x) memset(a,x,sizeof(a))
23typedef long long LL;
24#define pi pair < int ,int >
25#define MP make_pair
26using namespace std;
27const double eps = 1E-8;
28const int dx4[4]={1,0,0,-1};
29const int dy4[4]={0,-1,1,0};
30const int inf = 0x3f3f3f3f;
31const int N=1E3+5;
32int n,K;
33struct Mat
34{
35 int mat[10][10];
36 void clear()
37 {
38 ms(mat,0);
39 }
40}C,M;
41Mat operator * ( Mat a, Mat b)
42{
43 Mat ans;
44 ans.clear();
45 for ( int i = 0 ; i < K ; i++)
46 {
47 for ( int j = 0 ; j < K ; j++)
48 {
49 for ( int k = 0 ; k < K ; k++)
50 {
51 ans.mat[i][j] = (ans.mat[i][j] + a.mat[i][k] * b.mat[k][j])%6;
52 }
53 }
54 }
55 return ans;
56}
57Mat operator ^ ( Mat a,int b)
58{
59 Mat ans;
60 ans.clear();
61 for ( int i = 0 ; i < K ; i++) ans.mat[i][i] = 1;
62 while (b>0)
63 {
64 if (b&1) ans = ans * a;
65 b = b >> 1;
66 a = a * a;
67 }
68 return ans;
69}
70int A[N][10],B[10][N],ans[2][N][N];
71int main()
72{
73 #ifndef ONLINE_JUDGE
74 freopen("code/in.txt","r",stdin);
75 #endif
76 while (~scanf("%d%d",&n,&K))
77 {
78 if (n==0&&K==0) break;
79 ms(A,0);
80 ms(B,0);
81 C.clear();
82 for ( int i = 0 ; i < n ; i++)
83 for ( int j = 0 ; j < K ; j++)
84 scanf("%d",&A[i][j]);
85 for ( int i = 0 ; i < K ; i++)
86 for ( int j = 0 ; j < n ; j++)
87 scanf("%d",&B[i][j]);
88 for ( int i = 0 ; i < K ; i++)
89 for ( int j = 0 ; j < K ; j++)
90 for ( int k = 0 ; k < n ; k++)
91 C.mat[i][j] = (C.mat[i][j] + B[i][k] * A[k][j])%6;
92 M = C^(n*n-1);
93 ms(ans,0);
94 for ( int i = 0 ; i < n ; i++)
95 for ( int j = 0 ; j < K ;j++)
96 for ( int k = 0 ; k < K ; k++)
97 ans[0][i][j] =( ans[0][i][j] + A[i][k] * M.mat[k][j])%6;
98 for ( int i = 0 ; i < n ; i++)
99 for ( int j = 0 ; j < n ; j++)
100 for ( int k = 0 ; k < K ; k++)
101 ans[1][i][j] =( ans[1][i][j] + ans[0][i][k] * B[k][j])%6;
102 LL sum = 0 ;
103 for ( int i = 0 ; i < n ; i++)
104 for ( int j = 0 ; j < n ; j++)
105 sum = sum + ans[1][i][j];
106 printf("%lld\n",sum);
107 }
108 #ifndef ONLINE_JUDGE
109 fclose(stdin);
110 #endif
111 return 0;
112}