Matrix Power Series

描述

Given a n × n matrix A and a positive integer k, find the sum S = A + A2 + A3 + … + Ak.

输入

The input contains exactly one test case. The first line of input contains three positive integers n (n ≤ 30), k (k ≤ 10^9) and m (m < 10^4). Then follow n lines each containing n nonnegative integers below 32,768, giving A’s elements in row-major order.

输出

Output the elements of S modulo m in the same way as A is given.

样例输入

2 2 4 0 1 1 1

样例输出

1 2 2 3

解题思路：第一种方法：题意为给定矩阵A（以下代码中用ori表示)。以及k, mod ,求 A+A^2+A^3+......A^k    的和对mod取余。一開始用循环k次，递推的做法，超时。。。看了解题报告，求和的时候要用到二分求和。所求的和用s(k)表示。当k为偶数时：比方 k=6,那么  A+A^2+A^3+A^4+A^5+A^6=    A+A^2+A^3+   A^3*（A+A^2+A^3）   s(k)=s(k/2)+A^(n/2) * s(k/2) 即s(k)=(E+A^(n/2))*s(n/2)  （E为单位矩阵）当k为奇数时：s(k)=s(k-1)+A^k ,  那么k-1为偶数。能够依照上面的二分PS：代码要写细致啊，否则一个小错误查半天.....计算两个矩阵相乘时ret.arr[i][j]+=a.arr[i][k]*b.arr[k][j]; 居然写成了ret.arr[i][j]+=a.arr[i][k]*a.arr[k][j]; T T代码：
#include #include using namespace std;; int n; int m; int k; #define MAXN 40 typedef struct node//设置结构体的目的纯粹就是传值方便 { int data[MAXN][MAXN]; node()//结构体的构造函数 { memset(data,0,sizeof(data)); } } Matri;//定义矩阵结构体 Matri ma;//定义要求的矩阵 Matri multi_mod(Matri a,Matri b)//定义矩阵的的相乘函数并且返回给另一个矩阵，一定要注意矩阵的乘法先后顺序是不能够颠倒的 { Matri c;//保存最终结果并要返回的矩阵 for(int i=0; i0) { if(fn%2==1) result=multi_mod(result,a);//调用乘法注意相乘顺序 a=multi_mod(a,a); fn=fn/2; } return result;//返回结果矩阵 } Matri op(int opn,Matri r)//按照题目要求进行操作 { if(opn==1)//如果是一次方,返回原来的数组自己 return r; if(opn%2==0)//如果是偶数那么就返回s(n/2)+s(n/2)*a^(n/2) { Matri aa=op(opn/2,r); Matri bb=fast_power(r,opn/2); r=add(aa,multi_mod(bb,aa)); } else r= add(op(opn-1,r),fast_power(ma,opn));//如果是奇数那么就返回s(n-1)*a^(n) return r; } int main() { cin>>n>>k>>m; for(int i=0;i>ma.data[i][j]; } } Matri result=op(k,ma); for(int i=0;i