对于数列S(n) = a + a^2 + a^3 +....+ a^n;
可以用二分的思想进行下列的优化。
if(n & 1)
S(n) = a + a^2 + a^3 + ....... + a^n;
= a + a^2 + a^3 +..+ a^((n-1) / 2) + a^((n-1) / 2 + 1) + a^((n-1) / 2 + 2) + ... + a^((n-1) / 2 + (n-1) / 2) + a^((n-1) / 2 + (n-1) / 2 + 1);
= (1 + a^((n-1) / 2 + 1)) * S((n-1)/2) + a^((n-1) / 2 + 1)
else
S(n) = a + a^2 + a^3 + ....... + a^n;
= a + a^2 + a^3 +..+ a^((n / 2) + a^(n / 2 + 1) + a^(n / 2 + 2) + ... + a^(n/ 2 + n / 2);
= (1 + a^(n / 2)) * S(n / 2);
这样就可以避免矩阵的除法了！ 还有就是MOD真的很慢。
#include<map>
#include<set>
#include<string>
#include<queue>
#include<stack>
#include<cmath>
#include<vector>
#include<cstdio>
#include<time.h>
#include<cstring>
#include<iostream>
#include<algorithm>
#define INF 1000000001
#define ll long long
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
using namespace std;
const int MAXN = ;
struct Mat
{
ll a[][];
}E;
int n,k,MOD;
Mat Matadd(Mat a,Mat b)
{
Mat c;
for(int i = ; i < n; i++){
for(int j = ; j < n; j++){
c.a[i][j] = (a.a[i][j] + b.a[i][j])%MOD;
}
}
return c;
}
Mat Matmul(Mat a,Mat b)
{
Mat c;
for(int i = ; i < n; i++){
for(int j = ; j < n; j++){
c.a[i][j] = ;
for(int k = ; k < n; k++){
c.a[i][j] += (a.a[i][k] * b.a[k][j])%MOD;
}
c.a[i][j] %= MOD;
}
}
return c;
}
Mat power(Mat a,int n)
{
Mat c;
c = E;
while(n){
if(n & ){
c = Matmul(c,a);
}
a = Matmul(a,a);
n >>= ;
}
return c;
}
Mat sum(Mat a,int k)//求S(k)
{
if(k == )return a;
Mat t = sum(a,k/);//S(k/2)
if(k & ){
Mat cur = power(a,k/ + );//a^(k/2 + 1)
t = Matadd(t,Matmul(t,cur));//(1 + a^(k/2+1))*S(k/2)
t = Matadd(t,cur);//(1 + a^(k/2 + 1))*S(k/2)
}
else {
Mat cur = power(a,k/);//a^(k/2)
t = Matadd(t,Matmul(t,cur));//(1 + a^(k/2))*S(k/2)
}
return t;
}
int main()
{
while(scanf("%d%d%d",&n,&k,&MOD) != EOF){
Mat a;
memset(E.a,,sizeof(E.a));
for(int i = ; i < n; i++)E.a[i][i] = ;
for(int i = ; i < n; i++){
for(int j = ; j < n; j++){
scanf("%lld",&a.a[i][j]);
a.a[i][j] %= MOD;
}
}
Mat ans = sum(a,k);
for(int i = ; i < n; i++){
for(int j = ; j < n; j++){
if(j == )printf("%lld",ans.a[i][j]);
else {
printf(" %lld",ans.a[i][j]);
}
}
printf("\n");
}
}
return ;
}