POJ 3233 Matrix Power Series(矩阵等比求和)

题目链接

模板题。

#include <cstdio>
#include <cstring>
#include <iostream>
#include <map>
#include <algorithm>
#include <vector>
#include <string>
using namespace std;
int p[][],mat[][];
int t;
void qmod(int n,int MOD)
{
int c[][],i,j,k;
while(n)
{
memset(c,,sizeof(c));
if(n&)
{
memset(c,,sizeof(c));
for(i = ;i < t;i ++)
{
for(j = ;j < t;j ++)
{
for(k = ;k < t;k ++)
{
c[i][j] += mat[i][k] * p[k][j];
c[i][j] %= MOD;
}
}
}
memcpy(mat,c,sizeof(mat));
}
memset(c,,sizeof(c));
for(i = ;i < t;i ++)
{
for(j = ;j < t;j ++)
{
for(k = ;k < t;k ++)
{
c[i][j] += p[i][k] * p[k][j];
c[i][j] %= MOD;
}
}
}
memcpy(p,c,sizeof(p));
n >>= ;
}
}
int main()
{
int n,m,k,i,j;
while(scanf("%d%d%d",&n,&k,&m)!=EOF)
{
for(i = ;i < n;i ++)
{
for(j = ;j < n;j ++)
scanf("%d",&p[i][j]);
}
for(i = ;i < n;i ++)
{
p[i][i+n] = p[i+n][i+n] = ;
}
n <<= ;
for(i = ;i < n;i ++)
{
for(j = ;j < n;j ++)
mat[i][j] = (i == j);
}
t = n;
qmod(k+,m);
n >>= ;
for(i = ;i < n;i ++)
{
mat[i][i+n] --;
if(mat[i][i+n] < )
mat[i][i+n] += m;
}
for(i = ;i < n;i ++)
{
for(j = ;j < n;j ++)
{
if(j == n-)
printf("%d\n",mat[i][j+n]);
else
printf("%d ",mat[i][j+n]);
}
}
}
return ;
}
上一篇:POJ 3233 Matrix Power Series 矩阵快速幂


下一篇:POJ 3233 Matrix Power Series 矩阵快速幂+二分求和