909
POJ 3233 矩陣連乘+二分
這題2829MS險過。。應該會有更好的方法 首先矩陣連乘這沒說的 重要的是在於二分 有公式 k為奇數時 s(k)=a+(a+a^(k/2+1))*s(k/2)
k為偶數時 s(k)=(1+a^(k/2))*s(k/2) 例如s(7)=a+(a+a^4)*s(3) s(6)=(1+a^3)*s(3) 有了二分的方法這題明顯思路就清楚了
#include<cstdio>
#include<cmath>
#include<iostream>
using namespace std;
const int nMAX=35;
int MAX;
int M;
typedef struct
{
long long m[nMAX][nMAX];
} Matrix;
Matrix P,I;
Matrix matrixmul(Matrix a,Matrix b) //矩陣乘法
{
int i,j,k;
Matrix c;
for (i = 0 ; i < MAX; i++)
for (j = 0; j < MAX; j++)
{
c.m[i][j] = 0;
for (k = 0; k < MAX; k++)
c.m[i][j] += (a.m[i][k] * b.m[k][j])%M;
c.m[i][j] %= M;
}
return c;
}
Matrix quickpow(long long n)
{
Matrix m = P, b = I;
while (n >= 1)
{
if (n & 1)
b = matrixmul(b,m);
n = n >> 1;
m = matrixmul(m,m);
}
return b;
}
Matrix add(Matrix a,Matrix b)
{
Matrix c;
for(int i=0;i<MAX;i++)
for(int j=0;j<MAX;j++)
{
c.m[i][j]=0;
c.m[i][j]+=(a.m[i][j]+b.m[i][j])%M;
}
return c;
}
Matrix getsum(Matrix a,int k)
{
if(k==1)
return a;
Matrix t=getsum(a,k/2);
if(k&1)
return add(a,matrixmul(add(a,quickpow(k/2+1)),t));
return matrixmul(add(I,quickpow(k/2)),t);
}
int main()
{
long long k,m;
Matrix ans;
for(int i=0; i<nMAX; i++)
for(int j=0; j<nMAX; j++)
I.m[i][j]=i==j?1:0;
while(~scanf("%d%d%d",&MAX,&k,&m))
{
for(int i=0; i<MAX; i++)
for(int j=0; j<MAX; j++)
scanf("%d",&P.m[i][j]);
M=m;
ans=getsum(P,k);
// for(int i=0;i<MAX;i++)
// for(int j=0;j<MAX;j++)
// ans.m[i][j]%=m;
for(int i=0; i<MAX; i++)
for(int j=0; j<MAX; j++)
{
if(j<MAX-1)
printf("%d ",ans.m[i][j]);
else
printf("%d\n",ans.m[i][j]);
}
}
return 0;
}
最後更新：2017-04-04 07:03:38