首页 > 代码库 > HDU 4965 矩阵快速幂

HDU 4965 矩阵快速幂

顺手写了下矩阵类模板

  利用到矩阵乘法的交换律 (A*B)^n == A * (B*A)^n-1 *B

 

#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>#include <cmath>#include <vector>#include <utility>#include <stack>#include <queue>#include <map>#include <deque>#define max(x,y) ((x)>(y)?(x):(y))#define min(x,y) ((x)<(y)?(x):(y))#define INF 0x3f3f3f3f#define MOD 6using namespace std;int n,m;struct Matrix{    int n,m;    vector< vector<int> >a;    Matrix(){};    Matrix(const Matrix & T) : n(T.n),m(T.m)    {        a.resize(n);        for(int i=0; i<n; i++)        {            a[i].resize(m);            for(int j=0; j<m; j++)                a[i][j]=T.a[i][j];        }    }    Matrix(int N, int M)    {        n=N;        m=M;        a.resize(N);        for(int i=0; i<N; i++)            a[i].resize(M);    }    Matrix & operator=(const Matrix &T)    {        n=T.n;        m=T.m;        a.resize(n);        for(int i=0; i<n; i++)        {            a[i].resize(m);            for(int j=0; j<m; j++)                a[i][j]=T.a[i][j];        }        return *this;    }    Matrix operator+(const Matrix &T) const    {        Matrix tmp(n,m);        for(int i=0; i<n; i++)            for(int j=0; j<m; j++)            tmp.a[i][j]=a[i][j]+T.a[i][j];        return tmp;    }    Matrix operator*(const Matrix &T) const    {        Matrix tmp(n,T.m);        for(int i=0; i<n; i++)            for(int j=0; j<T.m; j++)                for(int k=0; k<m; k++)                tmp.a[i][j]=(tmp.a[i][j]+a[i][k]*T.a[k][j])%MOD;        return tmp;    }    void input(int N, int M)    {        n=N;        m=M;        a.resize(n);        for(int i=0; i<n; i++)        {            a[i].resize(m);            for(int j=0; j<m; j++)            scanf("%d",&a[i][j]);        }    }    void output()    {        for(int i=0; i<n; i++)        {            for(int j=0; j<m; j++)                printf("%d ",a[i][j]);            printf("\n");        }    }    Matrix pow_m(int N)//矩阵满足n=m    {        Matrix ret(n,n),tmp(*this);        for(int i=0; i<n; i++)            ret.a[i][i]=1;        while(N)        {            if(N&1) ret=ret*tmp;            tmp=tmp*tmp;            N>>=1;        }        return ret;    }};int main(){    while(scanf("%d%d",&n,&m)!=EOF && n && m)    {        Matrix a,b,c,d;        a.input(n,m);        b.input(m,n);        c=b*a;        d=c.pow_m(n*n-1);        d=a*d*b;        int ans=0;        for(int i=0; i<d.n; i++)            for(int j=0; j<d.m; j++)            ans=ans+d.a[i][j];        printf("%d\n",ans);    }    return 0;}