首页 > 代码库 > 【poj3233】 Matrix Power Series

【poj3233】 Matrix Power Series

http://poj.org/problem?id=3233 (题目链接)

题意:给出一个n×n的矩阵A,求模m下A+A2+A3++Ak 的值

Solution 
  今日考试就A了这一道题。。 
  当k为偶数时,原式=(Ak2+1)×(A1+A2+...+Ak2) 
  当k为奇数的时候将Ak乘上当前答案后抠出去,最后统计答案时再加上。所以我们就一路快速幂搞过去,AC

代码:

// poj3233#include<algorithm>#include<iostream>#include<cstdlib>#include<cstring>#include<cstdio>#include<cmath>#define LL long long#define inf 2147483640#define Pi acos(-1.0)#define free(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout);using namespace std;const int maxn=31;int A[maxn][maxn],B[maxn][maxn],C[maxn][maxn],T[maxn][maxn],tmp[maxn][maxn],ans[maxn][maxn],D[maxn][maxn];int n,m;void pow(int k) {    for (int i=1;i<=n;i++) {        for (int j=1;j<=n;j++) B[i][j]=0,T[i][j]=A[i][j];        B[i][i]=1;    }    while (k) {        if (k&1) {            for (int i=1;i<=n;i++)                for (int j=1;j<=n;j++) {                    tmp[i][j]=0;                    for (int k=1;k<=n;k++) tmp[i][j]=(tmp[i][j]+B[i][k]*T[k][j])%m;                }            for (int i=1;i<=n;i++)                for (int j=1;j<=n;j++) B[i][j]=tmp[i][j];        }        for (int i=1;i<=n;i++)            for (int j=1;j<=n;j++) {                C[i][j]=0;                for (int k=1;k<=n;k++) C[i][j]=(C[i][j]+T[i][k]*T[k][j])%m;            }        for (int i=1;i<=n;i++)            for (int j=1;j<=n;j++) swap(C[i][j],T[i][j]);        k>>=1;    }}void update() {    for (int i=1;i<=n;i++)        for (int j=1;j<=n;j++) {            tmp[i][j]=0;            for (int k=1;k<=n;k++) tmp[i][j]=(tmp[i][j]+ans[i][k]*B[k][j])%m;        }    for (int i=1;i<=n;i++)        for (int j=1;j<=n;j++) ans[i][j]=tmp[i][j];}int main() {        int k;    scanf("%d%d%d",&n,&k,&m);    for (int i=1;i<=n;i++)        for (int j=1;j<=n;j++) scanf("%d",&A[i][j]);    memset(ans,0,sizeof(ans));for (int i=1;i<=n;i++) ans[i][i]=1;    while (k>1) {        if (k&1) {            for (int i=1;i<=n;i++)                for (int j=1;j<=n;j++) T[i][j]=A[i][j];            pow(k);            for (int i=1;i<=n;i++)                for (int j=1;j<=n;j++) {                    tmp[i][j]=0;                    for (int k=1;k<=n;k++) tmp[i][j]=(tmp[i][j]+B[i][k]*ans[k][j])%m;                }            for (int i=1;i<=n;i++)                for (int j=1;j<=n;j++) D[i][j]=(D[i][j]+tmp[i][j])%m;        }        pow(k/2);        for (int i=1;i<=n;i++) B[i][i]=(B[i][i]+1)%m;        update();        k>>=1;    }    for (int i=1;i<=n;i++)        for (int j=1;j<=n;j++) B[i][j]=A[i][j];    update();    for (int i=1;i<=n;i++) {        for (int j=1;j<=n;j++) printf("%d ",(ans[i][j]+D[i][j])%m);        printf("\n");    }    return 0;}

  

 

【poj3233】 Matrix Power Series