矩阵快速幂:
Matrix Power Series
Time Limit: 3000MSMemory Limit: 131072K
Total Submissions: 16341Accepted: 6966
Description
Given a n × n matrix A and a positive integer k, find the sumS = A + A2 + A3 + … + Ak.
Input
The input contains exactly one test case. The first line of input contains three positive integersn (n ≤ 30), k (k ≤ 109) and m (m < 104). Then follown lines each containing n nonnegative integers below 32,768, givingA’s elements in row-major order.
Output
Output the elements of S modulo m in the same way as A is given.
Sample Input
2 2 40 11 1
Sample Output
1 22 3
题意:简单易懂;
题解:两次二分矩阵,具体看代码吧!
AC代码:
#include <cstdio>#include <iostream>#include <cstring>#include <algorithm>#include <vector>#include <cmath>#include <queue>#include <map>#include <set>#define eps 1e-9using namespace std;typedef long long ll;typedef pair<int,int>P;const int M = 1e5 + 100;const int INF = 0x3f3f3f3f;int n,mod,k;struct Mac {int c[33][33]; //原始矩阵void unit1() { //原始矩阵for(int i = 0; i < n; i++) {for(int j = 0; j < n; j++) {scanf("%d",&c[i][j]);}}}void unit2() { //单位矩阵c[0][0] = c[1][1] = 1;c[1][0] = c[0][1] = 0;}};Mac tmp,sum; //原始矩阵,和求和矩阵Mac mul(Mac a,Mac b) { //矩阵相乘Mac p;memset(p.c,0,sizeof(p.c));for(int i = 0; i < n; i++) {for(int j = 0; j < n; j++) {if(a.c[i][j]) {for(int k = 0; k < n; k++) {p.c[i][k] += (a.c[i][j] * b.c[j][k]) % mod;p.c[i][k] %= mod;}}}}return p;}Mac add(Mac a,Mac b) { //矩阵加法for(int i = 0; i < n; i++) {for(int j = 0; j < n; j++) {a.c[i][j] += b.c[i][j] % mod;a.c[i][j] %= mod;}}return a;}Mac quickmod(Mac a,int n) { //矩阵快速幂Mac p;p.unit2();while(n) {if(n & 1) p = mul(p,a);a = mul(a,a);n >>= 1;}return p;}Mac binary_matrix1(int k) { //二分矩阵快速幂Mac res;if(k == 1) {return tmp;}res = binary_matrix1(k / 2);res = mul(res,res);if(k & 1) res = mul(res,tmp);return res;}Mac binary_matrix2(int k){ //二分矩阵求矩阵幂之和 A1+A2+A3…;if(k == 1){return tmp;}Mac res = binary_matrix2(k / 2);Mac tp = binary_matrix1(k / 2);tp = mul(tp,res);sum = add(sum,tp);if(k & 1) sum = add(sum,binary_matrix1(k));return sum;}int main() {cin>>n>>k>>mod;tmp.unit1();for(int i = 0; i < n; i++){for(int j = 0; j < n; j++){sum.c[i][j] = tmp.c[i][j];}}Mac res = binary_matrix2(k);for(int i = 0; i < n; i++) {for(int j = 0; j < n; j++) {printf(j == n – 1 ? "%d\n" : "%d ",res.c[i][j]);}}return 0;}
，找回自我，歇够了，再飞回来，继续面对自己的人生。
