POJ 3233 - Matrix Power Series

/* POJ 3233 题目链接：https://vjudge.net/problem/POJ-3233 题意： 给一个n*n矩阵A 求 S = A^1 + A^2 + A^3+ ... + A^m n ≤30, m ≤1e9 , A.mat[i][j] <= 2^15=32768 参考： http://blog.csdn.net/wangjian8006/article/details/7868864 二分+快速幂 例如 m = 19 19 A^1+A^2+A^3+...+A^19 / \ 19/2 = 9 A^1+A^2+...A^9 +A^10+ A^11+A^12+...A^19 = A^10*(A^1+A^2+...A^9) / \ 9/2 = 4 A^1+A^2+A^3+A^4 +A^5+ A^6+A^7+A^8+A^9 = A^5*(A^1+A^2+A^3+A^4) / \ 4/2 = 2 A^1+A^2 + A^3+A^4 = A^2*(A^1+A^2) / \ 2/2 = 1 A^1 + A^2 = A^1*A^1 | return A; */ #include <iostream> #include <algorithm> #include <cstdio> #include <cstring> #include <queue> #include <vector> #include <cmath> #include <stack> #include <string> #include <map> #include <set> #define pi acos(-1) #define LL long long #define ULL unsigned long long #define inf 0x3f3f3f3f #define INF 1e18 #define lson l,mid,rt<<1 #define rson mid+1,r,rt<<1|1 using namespace std; typedef pair<int, int> P; const int maxn = 35; const int maxm = 35; //const int mod = 1e8; int n, m, mod; struct Matrix{ int l, r; // line行 | row列 LL mat[maxn][maxm]; void initZero(){ l = r = 0; memset(mat, 0, sizeof(mat)); } void initUnit(){ l = r = 0; for (int i = 0; i < maxn; i++) mat[i][i] = 1; } Matrix operator * (const Matrix &M) const { Matrix tmp; tmp.initZero(); tmp.l = l; tmp.r = M.r; for (int i = 1; i <= l; i++){ for (int j = 1; j <= r; j++){ if(!mat[i][j]) continue; for (int k = 1; k <= M.r; k++){ // tmp.mat[i][k] += (mat[i][j] * M.mat[j][k]) % mod;// 多模一次会wa.... tmp.mat[i][k] += mat[i][j] * M.mat[j][k]; tmp.mat[i][k] %= mod; } } } return tmp; } Matrix operator ^ (int k) const { Matrix M = *this; Matrix tmp; tmp.initZero(); tmp.initUnit(); tmp.l = tmp.r = M.l; while (k){ if (k & 1) tmp = tmp * M; k >>= 1; M = M * M; } return tmp; } Matrix operator + (const Matrix &M) const { Matrix tmp; tmp.l = l; tmp.r = r; for (int i = 1; i <= l; i++){ for (int j = 1; j <= r; j++){ tmp.mat[i][j] = mat[i][j] + M.mat[i][j]; tmp.mat[i][j] %= mod; } } return tmp; } void print(){ for (int i = 1; i <= l; i++){ for (int j = 1; j <= r; j++) cout << mat[i][j] << (j==r?"\n":" "); } } }; Matrix A;//下标从1开始 Matrix solve(int k) { if (k == 1) return A; Matrix cur, nxt; cur = solve(k >> 1); if (k & 1){ nxt = A ^ ((k >> 1) + 1); return cur + nxt + cur * nxt; } else { nxt = A ^ (k >> 1); return cur + cur * nxt; } } int main(void) { // freopen("in.txt", "r", stdin); while (cin >> n >> m >> mod){ A.initZero(); A.l = A.r = n; for (int i = 1; i <= n; i++){ for (int j = 1; j <= n; j++){ cin >> A.mat[i][j]; } } Matrix ans = solve(m); ans.print(); } return 0; }