HDU-4965 Fast Matrix Calculation （矩陣快速幂）

Fast Matrix Calculation

http://acm.hdu.edu.cn/showproblem.php?pid=4965

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 131072/131072 K (Java/Others)

Problem Description One day, Alice and Bob felt bored again, Bob knows Alice is a girl who loves math and is just learning something about matrix, so he decided to make a crazy problem for her.

Bob has a six-faced dice which has numbers 0, 1, 2, 3, 4 and 5 on each face. At first, he will choose a number N (4 <= N <= 1000), and for N times, he keeps throwing his dice for K times (2 <=K <= 6) and writes down its number on the top face to make an N*K matrix A, in which each element is not less than 0 and not greater than 5. Then he does similar thing again with a bit difference: he keeps throwing his dice for N times and each time repeat it for K times to write down a K*N matrix B, in which each element is not less than 0 and not greater than 5. With the two matrix A and B formed, Alice’s task is to perform the following 4-step calculation.

Step 1: Calculate a new N*N matrix C = A*B.

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’. 

Bob just made this problem for kidding but he sees Alice taking it serious, so he also wonders what the answer is. And then Bob turn to you for help because he is not good at math.  

Input The input contains several test cases. Each test case starts with two integer N and K, indicating the numbers N and K described above. Then N lines follow, and each line has K integers between 0 and 5, representing matrix A. Then K lines follow, and each line has N integers between 0 and 5, representing matrix B.

The end of input is indicated by N = K = 0.  

Output For each case, output the sum of all the elements in M’ in a line.  

Sample Input

4 2
5 5
4 4
5 4
0 0
4 2 5 5
1 3 1 5
6 3
1 2 3
0 3 0
2 3 4
4 3 2
2 5 5
0 5 0
3 4 5 1 1 0
5 3 2 3 3 2
3 1 5 4 5 2
0 0
        

Sample Output

14
56
  
  

        

看到矩陣快速幂以為是一道模闆水題（其實就是一道模闆水題。。。），就歡快的找模闆了，發現n能取1000時，果斷CE（棧記憶體爆了）+TLE，然後就不知所措

最後隊友将C^(n*n)寫成(A*B)*(A*B)……才反應過來，利用矩陣點結合律，計算(B*A)^(n*n-1)就行了，思維太死了。。。

#include <cstdio>
#include <cstring>

using namespace std;

int n,k,ans;

const int MAXN=1001;
const int MOD=6;

struct Matrix {
    int x[MAXN][MAXN];
    void clear() {
        memset(x,0,sizeof(x));
    };
}a,b,c,tmp,pro;

void mul(const Matrix& x,const Matrix& y,int bound_1,int bound_2,int bound_3) {//剛開始寫了個帶優化O(n^3)的乘法，為了減少更改其他代碼，故參數多加了3個循環變量點上界以使其适用于所有情況
    tmp.clear();
    for(int i=0;i<bound_1;++i)
        for(int j=0;j<bound_2;++j)
            for(int k=0;k<bound_3;++k)
                tmp.x[i][j]=(tmp.x[i][j]+x.x[i][k]*y.x[k][j])%MOD;
}

void quick_pow(Matrix& x,int num) {//矩陣快速幂
    pro.clear();
    for(int i=0;i<k;++i)
        pro.x[i][i]=1;
    while(num>0) {
        if((num&1)==1) {
            mul(pro,x,k,k,k);
            pro=tmp;
        }
        mul(x,x,k,k,k);
        x=tmp;
        num>>=1;
    }
}

int main() {
    while(scanf("%d%d",&n,&k),n!=0&&k!=0) {
        a.clear();
        b.clear();
        c.clear();
        for(int i=0;i<n;++i) {
            for(int j=0;j<k;++j)
                scanf("%d",&a.x[i][j]);
        }
        for(int i=0;i<k;++i) {
            for(int j=0;j<n;++j) {
                scanf("%d",&b.x[i][j]);
            }
        }
        mul(b,a,k,k,n);//由于矩陣太大，函數傳回矩陣的話oj直接判CE，隻能用全局變量
        c=tmp;
        quick_pow(c,n*n-1);
        c=pro;
        mul(a,c,n,n,k);
        c=tmp;
        mul(c,b,n,n,k);
        c=tmp;
        ans=0;
        for(int i=0;i<n;++i)
            for(int j=0;j<n;++j)
                ans+=c.x[i][j];
        printf("%d\n",ans);
    }
    return 0;
}
           

看了題解後發現，隻在快速幂時用結構體，其餘時候用二位數組，手動乘法，可以減少大量點空間浪費和指派點時間浪費

#include <cstdio>
#include <cstring>

using namespace std;

const int MAXN=6;
const int MOD=6;

int n,m,ans;
int a[1001][1001],b[1001][1001],c[1001][1001];

struct Matrix {
    int x[MAXN][MAXN];
    Matrix() {
        memset(x,0,sizeof(x));
    }
    void clear() {
        memset(x,0,sizeof(x));
    };
}cur;

Matrix mul(const Matrix& x,const Matrix& y) {
    Matrix res;
    for(int i=0;i<MAXN;++i)
        for(int j=0;j<MAXN;++j)
            for(int k=0;k<MAXN;++k)
                res.x[i][j]=(res.x[i][j]+x.x[i][k]*y.x[k][j])%MOD;
    return res;
}

Matrix quick_pow(Matrix& x,int num) {//矩陣快速幂
    Matrix res;
    for(int i=0;i<MAXN;++i)
        res.x[i][i]=1;
    while(num>0) {
        if((num&1)==1)
            res=mul(res,x);
        x=mul(x,x);
        num>>=1;
    }
    return res;
}

int main() {
    while(scanf("%d%d",&n,&m),n!=0&&m!=0) {
        for(int i=0;i<n;++i)
            for(int j=0;j<m;++j)
                scanf("%d",&a[i][j]);
        for(int i=0;i<m;++i)
            for(int j=0;j<n;++j)
                scanf("%d",&b[i][j]);

        cur.clear();
        for(int i=0;i<m;++i)
            for(int j=0;j<m;++j)
                for(int k=0;k<n;++k)
                    cur.x[i][j]=(cur.x[i][j]+b[i][k]*a[k][j])%MOD;
        cur=quick_pow(cur,n*n-1);
        memset(c,0,sizeof(c));
        for(int i=0;i<n;++i)
            for(int j=0;j<n;++j)
                for(int k=0;k<m;++k)
                    c[i][j]=(c[i][j]+a[i][k]*cur.x[k][j])%MOD;
        memset(a,0,sizeof(a));
        for(int i=0;i<n;++i)
            for(int j=0;j<n;++j)
                for(int k=0;k<m;++k)
                    a[i][j]=(a[i][j]+c[i][k]*b[k][j])%MOD;

        ans=0;
        for(int i=0;i<n;++i)
            for(int j=0;j<n;++j)
                ans+=a[i][j];
        printf("%d\n",ans);
    }
    return 0;
}