POJ 3233 Matrix Power Series 矩阵快速幂求A+A2+A3+…+Ak

本文主要是介绍POJ 3233 Matrix Power Series 矩阵快速幂求A+A2+A3+…+Ak，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意 ：给出n k m 和一个n*n的矩阵A 求A + A² +A³ + … + A^k

参考http://blog.csdn.net/wangjian8006/article/details/7868864

构造矩阵很重要啊！！！ 弱菜不会啊

#include <cstdio>
#include <cstring>
const int mod = 10000;
const int maxn = 66;
struct Mat
{int a[maxn][maxn];
};
Mat A, B;
int n, m;
Mat get(Mat x, Mat y)
{Mat z;memset(z.a, 0, sizeof(z.a));for(int i = 1; i <= 2*n; i++)for(int j = 1; j <= 2*n; j++)for(int k = 1; k <= 2*n; k++){z.a[i][j] += x.a[i][k]*y.a[k][j];z.a[i][j] %= m;}return z;
}
void Mat_pow(int x)
{//puts("s");if(x <= 0)return;while(x){if(x&1)B = get(B, A);A = get(A, A);x >>= 1;}
}
int main()
{int x;while(scanf("%d %d %d", &n, &x, &m) != EOF){memset(A.a, 0, sizeof(A.a));memset(B.a, 0, sizeof(B.a));for(int i = 1; i <= n; i++)for(int j = 1; j <= n; j++)scanf("%d", &A.a[i][j]);for(int i = 1; i <= n; i++){A.a[i][i+n] = A.a[i+n][i+n] = 1;B.a[i][i] = B.a[i+n][i+n] = 1;}Mat_pow(x+1);for(int i = 1; i <= n; i++){for(int j = 1; j <= n; j++){if(i == j){B.a[i][j+n] += m-1;B.a[i][j+n] %= m;}if(j-1)printf(" ");printf("%d", B.a[i][j+n]);}puts("");}}return 0;
}

 

这篇关于POJ 3233 Matrix Power Series 矩阵快速幂求A+A2+A3+…+Ak的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---