矩陣分治

注意不要用 (*this) 會改變原值

#include <iostream> #include <cstdio> #include <cstring> #include <cmath> #include <algorithm> #include <cstdlib> using namespace std; int n, p, k; struct Matrix{int num[35][35];void clear() {memset(num, 0, sizeof(num));}void unit() {clear();for(int i = 0; i < 35; i++) num[i][i] = 1;}Matrix operator * (const Matrix & b) {Matrix ans;ans.clear();for(int i = 1; i <= n; i++) {for(int j = 1; j <= n; j++) {int tmp = 0;for(int k = 1; k <= n; k++) {tmp += num[i][k] * b.num[k][j];tmp %= p;}ans.num[i][j] = tmp;}}return ans;}Matrix operator + (const Matrix & b) {Matrix ans;ans.clear();for(int i = 1; i <= n; i++) {for(int j = 1; j <= n; j++) {ans.num[i][j] = num[i][j] + b.num[i][j];ans.num[i][j] %= p;}}return ans;}Matrix operator ^ (int k) {Matrix ans, tmp = (*this);ans.unit();while(k) {if(k & 1) ans = ans * tmp;tmp = tmp * tmp;k >>= 1;}return ans;} }a, b; Matrix work(int cur) {if(cur == 1) return a;int mid = cur / 2;if(mid * 2 == cur) {Matrix t = work(mid);return t + t * (a ^ mid);}else {Matrix t = work(mid);return t + t * (a ^ mid) + (a ^ cur);} } int main() {cin >> n >> k >> p;for(int i = 1; i <= n; i++) {for(int j = 1; j <= n; j++) {cin >> a.num[i][j];a.num[i][j] %= p;}}b = work(k);for(int i = 1; i <= n; i++) {for(int j = 1; j <= n; j++) {printf("%d ", b.num[i][j]);}printf("\n");}return 0; }

轉載于:https://www.cnblogs.com/Mr-WolframsMgcBox/p/8676542.html

總結

以上是生活随笔為你收集整理的POJ 3233的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。