首页 > 代码库 > UVA11149_Power of Matrix

UVA11149_Power of Matrix

2024-07-14 23:13:49   220人阅读

题目简洁明了，给出矩阵，求前k次方和。

不知道这种方法是叫做二分幂还是倍增法，如果有知道的，请告诉我一下。

具体思想是这样的，A^1+A^2+A^3+......A^n=(E+A^(n/2))*(A^1+A^2+.....A^(n/2))，如果n为奇数，那么我们只要加上多余的哪一项就可以满足条件了，于是我们就通过这个公式不断的二分下去，用一个矩阵保存左边的矩阵的值，然后右边始终一直二分就可以了，整个复杂度是log^2的。

不过，我看别人的代码都比我跑得快，所以鄙人觉得应该有更简洁的方法，求指教啊。。。。

 

 

召唤代码君：

 

 

#include <iostream>#include <cstring>#include <cstdio>#define maxn 44using namespace std;int N,m;struct Mat{    int a[44][44];    Mat(){        for (int i=0; i<N; i++)            for (int j=0; j<N; j++) a[i][j]=0;    }    Mat(int x){        for (int i=0; i<N; i++){            for (int j=0; j<N; j++) a[i][j]=0;            a[i][i]=1;        }    }    Mat operator + (Mat M0) const {        Mat M1;        for (int i=0; i<N; i++)            for (int j=0; j<N; j++) M1.a[i][j]=(a[i][j]+M0.a[i][j])%10;        return M1;    }    Mat operator * (Mat M0) const {        Mat M1;        for (int i=0; i<N; i++)            for (int j=0; j<N; j++)                for (int k=0; k<N; k++)                    M1.a[i][j]=(M1.a[i][j]+a[i][k]*M0.a[k][j])%10;        return M1;    }    void input(){        for (int i=0; i<N; i++)            for (int j=0; j<N; j++) scanf("%d",&a[i][j]),a[i][j]%=10;    }    void output(){        for (int i=0; i<N; i++){            printf("%d",a[i][0]);            for (int j=1; j<N; j++) printf(" %d",a[i][j]);            printf("\n");        }        printf("\n");    }};Mat power(Mat M,int P){    Mat tot(1);    while (P){        if (P&1) tot=tot*M;        P>>=1,M=M*M;    }    return tot;}Mat count(Mat M,int P){    Mat M0,E(1),M1=E;    while (P){        if (P&1) M0=M0+M1*power(M,P);        P>>=1;        M1=M1*(E+power(M,P));    }    return M0;}int main(){    Mat M;    while (scanf("%d%d",&N,&m) && N!=0){        M.input();        M=count(M,m);        M.output();    }    return 0;}

 


联系
我们