Matrix Power Series
| Time Limit: 3000MS |
|
Memory Limit: 131072K |
| Total Submissions: 10211 |
|
Accepted: 4333 |
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
題意很簡(jiǎn)單不用描述了
網(wǎng)上在推薦這題的時(shí)候可能有些誤區(qū)
網(wǎng)上說(shuō)是二分再二分，
其實(shí)是這樣的，因?yàn)橛?jì)算a^k可以二分，這是第二個(gè)二分
而第一個(gè)二分是指的對(duì)a^1+a^2+....+a^k可以分成兩半
k是偶數(shù)時(shí)候
f[k]=(a^1+a^2+....+a^(k/2))+a^(k/2)*[a^1+a^2+....+a^(k/2)]
即 f[k]=f[k/2]+[a^(k/2)]*f[k/2]
奇數(shù)時(shí)候
f[k]=f[k-1]+a^k
以上描述的兩次二分是第一種做法
第二種做法
運(yùn)用線性代數(shù)的
令B= A E
0 E
那么
B^(k+1)= A^(k+1) E+A+...A^k
0 E
然后就不用多說(shuō)了
剛開(kāi)始想出第一種方法，覺(jué)著也不難寫 ，
然后wa到死 tle到死
一直超時(shí)，那個(gè)取模那個(gè)如果不取就wa，取了就tle，真心糾結(jié)了
然后忍不了了
寫的第二個(gè)
不知道為什么還是那么長(zhǎng)時(shí)間
應(yīng)該是我寫的代碼質(zhì)量不好
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<iostream>
#define maxn 35*2
using namespace std;
struct node
{
__int64 x[maxn][maxn];
void init()
{
memset(x,0,sizeof(x));
}
void init1()
{
memset(x,0,sizeof(x));
for(int i=1; i<maxn; i++)
x[i][i]=1;
}
};
node e;
int m,n,k;
void print1(node x)
{
for(int i=1; i<=n; i++)
{
for(int j=1+n; j<=2*n; j++)
{
printf("%d",x.x[i][j]);
if(j==n*2) printf("\n");
else printf(" ");
}
}
}
node add1(node x)
{
node tmp;
tmp=x;
for(int i=1;i<=n;i++)
{
for(int j=n+1;j<=2*n;j++)
tmp.x[i][j]=(tmp.x[i][j]%m+m)%m;
}
for(int i=1; i<=n; i++)
tmp.x[i][i+n]=(tmp.x[i][i+n]-1+m)%m;
return tmp;
}
node mul(node t1,node t2)
{
node tmp;
tmp.init();
for(int i=1; i<=2*n; i++)
for(int j=1; j<=2*n; j++)
{
tmp.x[i][j]=0;
for(int k=1; k<=2*n; k++)
{
tmp.x[i][j]=(tmp.x[i][j]+t1.x[i][k]*t2.x[k][j])%m;
}
}
return tmp;
}
node ap(node a,int p)
{
int tmp;
node x,ans;
tmp=p;
ans.init1();
x=a;
while(tmp)
{
if(tmp%2==1) ans=mul(ans,x);
tmp=tmp/2;
x=mul(x,x);
}
return ans;
}
int main()
{
node a,ans,b;
scanf("%d%d%d",&n,&k,&m);
a.init();
for(int i=1; i<=n; i++)
for(int j=1; j<=n; j++)
{
scanf("%d",&a.x[i][j]);
a.x[i][j]=a.x[i][j]%m;
}
b=a;
for(int j=1; j<=n; j++)
{
b.x[j][j+n]=1;
b.x[j+n][j+n]=1;
}
ans=ap(b,k+1);
ans=add1(ans);
print1(ans);
return 0;
}
那個(gè)第一種方法tle，待會(huì)去優(yōu)化下代碼，應(yīng)該能過(guò)
呼，第一種方法終于過(guò)了
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<iostream>
#define maxn 35
#define inf 0x7fffffff
using namespace std;
struct node
{
__int64 x[maxn][maxn];
void init()
{
memset(x,0,sizeof(x));
}
void init1()
{
memset(x,0,sizeof(x));
for(int i=1; i<maxn; i++)
x[i][i]=1;
}
};
node e;
int m,n,k;
void print(node x)
{
for(int i=1; i<=n; i++)
{
for(int j=1; j<=n; j++)
{
printf("%d",x.x[i][j]);
if(j==n) printf("\n");
else printf(" ");
}
}
}
node add(node t1,node t2)
{
node tmp;
for(int i=1; i<=n; i++)
for(int j=1; j<=n; j++)
{
tmp.x[i][j]=(t1.x[i][j]+t2.x[i][j])%m;
}
return tmp;
}
node mul(node t1,node t2)
{
node tmp;
tmp.init();
for(int i=1; i<=n; i++)
for(int j=1; j<=n; j++)
{
tmp.x[i][j]=0;
for(int k=1; k<=n; k++)
{
tmp.x[i][j]=(tmp.x[i][j]+t1.x[i][k]*t2.x[k][j]);
if(tmp.x[i][j]>=inf)
{
tmp.x[i][j]=tmp.x[i][j]%m;
}
}
tmp.x[i][j]=(tmp.x[i][j])%m;
}
return tmp;
}
node ap(node a,int p)
{
int tmp;
node x,ans;
tmp=p;
ans.init1();
x=a;
while(tmp)
{
if(tmp%2==1) ans=mul(x,ans);
tmp=tmp/2;
x=mul(x,x);
}
return ans;
}
node getsum(node x,int n)
{
int k;
node ans,tmp;
k=n;
if(k==1) return x;
if (k%2==0)
{
tmp=getsum(x,k/2);
ans=add(tmp,mul(ap(x,k/2),tmp));
}
else
{
tmp=getsum(x,k/2);
ans=add(add(tmp,mul(ap(x,k/2),tmp)),ap(x,k));
}
return ans;
}
int main()
{
node a,ans,b;
scanf("%d%d%d",&n,&k,&m);
a.init();
for(int i=1; i<=n; i++)
for(int j=1; j<=n; j++)
{
scanf("%d",&a.x[i][j]);
a.x[i][j]=a.x[i][j]%m;
}
ans=getsum(a,k);
print(ans);
return 0;
}