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
題意很簡單不用描述了
網上在推薦這題的時候可能有些誤區
網上說是二分再二分，
其實是這樣的，因為計算a^k可以二分，這是第二個二分
而第一個二分是指的對a^1+a^2+....+a^k可以分成兩半
k是偶數時候
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]
奇數時候
f[k]=f[k-1]+a^k
以上描述的兩次二分是第一種做法
第二種做法
運用線性代數的
令B= A E
0 E
那么
B^(k+1)= A^(k+1) E+A+...A^k
0 E
然后就不用多說了
剛開始想出第一種方法，覺著也不難寫 ，
然后wa到死 tle到死
一直超時，那個取模那個如果不取就wa，取了就tle，真心糾結了
然后忍不了了
寫的第二個
不知道為什么還是那么長時間
應該是我寫的代碼質量不好
#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;
}
那個第一種方法tle，待會去優化下代碼，應該能過
呼，第一種方法終于過了
#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;
}