POJ 3233_Matrix Power Series

题意：

求n*n矩阵的幂和

分析：

逐个加起来时间复杂度太高，通过在矩阵中套个矩阵和，再利用矩阵快速幂，最后时间复杂度为O(n3logn)

代码：

#include<cstdio>

#include<iostream>

#include<cstdio>

using namespace std;

typedef long long ll;

const int N= 85;

int n;

struct Matrix

{

    int row,cal;

    ll m[N][N];

};

Matrix init(Matrix a, ll t)

{

    for(int i = 0; i < a.row; i++)

        for(int j = 0; j < a.cal; j++)

            a.m[i][j] = t;

    return a;

}

Matrix mul(Matrix a,Matrix b, int mod)

{

    Matrix ans;

    ans.row = a.row, ans.cal = b.cal;

    ans = init(ans,0);

    for(int i = 0; i < a.row; i++)

        for(int j = 0; j < b.cal; j++)

            for(int k = 0; k < a.cal; k++)

                ans.m[i][j] = (ans.m[i][j] + a.m[i][k] * b.m[k][j])%mod;

    return ans;

}

Matrix quick_pow(int k, Matrix A, int mod)

{

    Matrix I;

    I.row = 2 * n, I.cal = n;

    I = init(I,0);

    for(int i = 0; i < n; i++)

            I.m[i][i] = 1;

    int cnt = 1;

    while(k){

        if(k&1) I = mul(A, I, mod);

        A = mul(A, A, mod);

        k>>=1;

    }

    return I;

}

int main (void)

{

    int k, mod;scanf("%d%d%d",&n,&k,&mod);

    Matrix A, I;

    A.row= A.cal = 2 * n;

    A = init(A, 0);

    for(int i = 0; i < n; i++)

        for(int j = 0; j < n; j++)

            scanf("%d",&A.m[i][j]);

    for(int i = n; i < 2 * n; i++){

         A.m[i][i] = 1;

         A.m[i][i - n] = 1;

    }

    Matrix res = quick_pow(k+1, A, mod);

    int tmp;

    for(int i = n; i < 2 * n; i++){

        for(int j = 0; j < n; j++){

          if(i - j == n) tmp = (res.m[i][j] - 1+mod)%mod;

         else tmp = res.m[i][j];

          printf("%d%c",tmp, j == n-1?'\n':' ');

        }

    }

    return 0;

}

样例都调不出来，半天才发现自己原来的模板乘法写错了，神奇的竟然用错的模板过了两道题。。。真是连自己都不能信了，懒惰的后果，下次一定要自己重新动手！！

---

哦因为之前习惯写I∗Ak的形式，所以a.cal=b.cal，现在换个右乘，错误就暴露了。