Description
Given a n × n matrix A and a positive integer k, find the sum S = A + A2 + A3 + … + Ak.
Input
The input contains exactly one test case. The first line of input contains three positive integers n (n ≤ 30), k (k ≤ 109) and m (m < 104). Then follow n lines each containing n nonnegative integers below 32,768, giving A’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 4
0 1
1 1
Sample Output
1 2
2 3
Source
POJ Monthly--2007.06.03, Huang, Jinsong
正解：矩乘快速幂+二分
解题报告;
今天考试T1。
考场上面推了一个上午的式子，好不容易发现一个，而且是一个log的，结果太复杂了，没调出来。最后没办法了，临时yy了一个两个log的方法，好歹也过了。
考虑只有两种可能，题目相当于是要求一个前缀和，那么矩乘满足分配律，所以我们可以直接利用前面的结果乘起来就可以了。
还是数学题做少了，不会推式子，还是要多练。
当然还有一个log的方法，就是直接倒着做，其余的完全相同。
两个log：
//It is made by jump~
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <ctime>
#include <vector>
#include <queue>
#include <map>
#include <set>
using namespace std;
typedef long long LL;
#define RG register
int n,k,MOD;
int dui[],tail; struct juz{
LL s[][];
}a,c[],ini,mi[]; inline int getint()
{
RG int w=,q=; char c=getchar(); while((c<'' || c>'') && c!='-') c=getchar();
if (c=='-') q=, c=getchar(); while (c>='' && c<='') w=w*+c-'', c=getchar(); return q ? -w : w;
} inline juz jia(juz p,juz q){
juz tmp;
for(RG int i=;i<=n;i++)
for(RG int j=;j<=n;j++)
tmp.s[i][j]=p.s[i][j]+q.s[i][j],tmp.s[i][j]%=MOD;
return tmp;
} inline juz cheng(juz p,juz q){
juz tmp;
for(RG int i=;i<=n;i++) for(RG int j=;j<=n;j++) tmp.s[i][j]=;
for(RG int i=;i<=n;i++)
for(RG int j=;j<=n;j++)
for(RG int l=;l<=n;l++)
tmp.s[i][j]+=p.s[i][l]*q.s[l][j],tmp.s[i][j]%=MOD;
return tmp;
} inline void work(){
n=getint(); k=getint(); MOD=getint();
for(RG int i=;i<=n;i++) for(RG int j=;j<=n;j++) ini.s[i][j]=getint();
while(k>) dui[++tail]=k,k>>=; mi[tail]=ini; c[tail]=ini;
for(RG int i=tail-;i>=;i--) {
mi[i]=cheng(mi[i+],mi[i+]);//每次平方
c[i]=jia(c[i+],cheng(c[i+],mi[i+]));//前面的乘以之前的部分再加上自己可降低复杂度
if(dui[i]&) mi[i]=cheng(mi[i],ini),c[i]=jia(c[i],mi[i]);
}
for(RG int i=;i<=n;i++) { for(RG int j=;j<=n;j++) printf("%lld ",c[].s[i][j]); printf("\n"); }
} int main()
{
work();
return ;
}
一个log：
//It is made by jump~
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <ctime>
#include <vector>
#include <queue>
#include <map>
#include <set>
using namespace std;
typedef long long LL;
#define RG register
int n,k,MOD;
int dui[],tail; struct juz{
LL s[][];
}a,c[],ini,mi[]; inline int getint()
{
RG int w=,q=; char c=getchar(); while((c<'' || c>'') && c!='-') c=getchar();
if (c=='-') q=, c=getchar(); while (c>='' && c<='') w=w*+c-'', c=getchar(); return q ? -w : w;
} inline juz jia(juz p,juz q){
juz tmp;
for(RG int i=;i<=n;i++)
for(RG int j=;j<=n;j++)
tmp.s[i][j]=p.s[i][j]+q.s[i][j],tmp.s[i][j]%=MOD;
return tmp;
} inline juz cheng(juz p,juz q){
juz tmp;
for(RG int i=;i<=n;i++) for(RG int j=;j<=n;j++) tmp.s[i][j]=;
for(RG int i=;i<=n;i++)
for(RG int j=;j<=n;j++)
for(RG int l=;l<=n;l++)
tmp.s[i][j]+=p.s[i][l]*q.s[l][j],tmp.s[i][j]%=MOD;
return tmp;
} inline void work(){
n=getint(); k=getint(); MOD=getint();
for(RG int i=;i<=n;i++) for(RG int j=;j<=n;j++) ini.s[i][j]=getint();
while(k>) dui[++tail]=k,k>>=; mi[tail]=ini; c[tail]=ini;
for(RG int i=tail-;i>=;i--) {
mi[i]=cheng(mi[i+],mi[i+]);//每次平方
c[i]=jia(c[i+],cheng(c[i+],mi[i+]));//前面的乘以之前的部分再加上自己可降低复杂度
if(dui[i]&) mi[i]=cheng(mi[i],ini),c[i]=jia(c[i],mi[i]);
}
for(RG int i=;i<=n;i++) { for(RG int j=;j<=n;j++) printf("%lld ",c[].s[i][j]); printf("\n"); }
} int main()
{
work();
return ;
}