POJ 3233 Matrix Power Series——矩阵快速幂

POJ 3233 Matrix Power Series——矩阵快速幂

挑战程序设计P205，重点是构造出新的矩阵

#include #include #include #include using namespace std;const int maxn = 100;int n, k, m;struct Matrix { int sz, mat[maxn][maxn]; Matrix(int x) { sz = x; memset(mat, 0, sizeof(mat)); } Matrix operator * (const Matrix& x) const { Matrix ans(sz); for (int i = 0; i < sz; i++) { for (int j = 0; j < sz; j++) { for (int t = 0; t < sz; t++) { ans.mat[i][j] = (ans.mat[i][j] + mat[i][t]*x.mat[t][j]) % m; } } } return ans; }};Matrix mpow(Matrix& a) { Matrix ans(a.sz); for (int i = 0; i < a.sz; i++) ans.mat[i][i] = 1; while (k) { if (k & 1) ans = ans * a; a = a * a; k >>= 1; } return ans;}int main() { while (~scanf("%d %d %d", &n, &k, &m)) { Matrix a(n), b(n<<1); for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { scanf("%d", &a.mat[i][j]); b.mat[i][j] = a.mat[i][j]; } b.mat[i+n][i] = b.mat[i+n][i+n] = 1; } b = mpow(b); Matrix ans(n); for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { for (int k = 0; k < n; k++) { ans.mat[i][j] = (ans.mat[i][j] + b.mat[i+n][k]*a.mat[k][j]) % m; } ans.mat[i][j] = (ans.mat[i][j] + b.mat[i+n][j+n]) % m; } ans.mat[i][i] = (ans.mat[i][i] - 1 + m) % m; } for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { printf("%d", ans.mat[i][j]); if (j != n-1) printf(" "); } printf("\n"); } } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。