POJ 3233 Matrix Power Series --二分求矩阵等比数列和

题意:求S(k) = A+A^2+...+A^k.

解法:二分即可。

if(k为奇)  S(k) = S(k-1)+A^k

else        S(k) = S(k/2)*(I+A^(k/2))

代码:

#include <iostream>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#define SMod m
using namespace std; int n,m,k; struct Matrix
{
int m[][];
Matrix()
{
memset(m,,sizeof(m));
for(int i=;i<=n;i++)
m[i][i] = ;
}
}; Matrix Mul(Matrix a,Matrix b)
{
Matrix res;
int i,j,k;
for(i=;i<=n;i++)
{
for(j=;j<=n;j++)
{
res.m[i][j] = ;
for(k=;k<=n;k++)
res.m[i][j] = (res.m[i][j]+(a.m[i][k]*b.m[k][j])%SMod + SMod)%SMod;
}
}
return res;
} Matrix add(Matrix a,Matrix b)
{
Matrix res;
memset(res.m,,sizeof(res.m));
int i,j;
for(i=;i<=n;i++)
for(j=;j<=n;j++)
res.m[i][j] = (a.m[i][j]+b.m[i][j])%SMod;
return res;
} Matrix fastm(Matrix a,int b)
{
Matrix res;
while(b)
{
if(b&1LL)
res = Mul(res,a);
a = Mul(a,a);
b >>= ;
}
return res;
} Matrix getsum(Matrix a,int b)
{
Matrix A = a;
Matrix I;
if(b == )
return A;
if(b & )
return add(getsum(a,b-),fastm(a,b));
else
return Mul(getsum(a,b/),add(I,fastm(a,b/)));
} int main()
{
int i,j;
while(scanf("%d%d%d",&n,&k,&m)!=EOF)
{
Matrix ans;
for(i=;i<=n;i++)
for(j=;j<=n;j++)
scanf("%d",&ans.m[i][j]);
ans = getsum(ans,k);
for(i=;i<=n;i++)
{
printf("%d",ans.m[i][]%m);
for(j=;j<=n;j++)
printf(" %d",ans.m[i][j]%m);
puts("");
}
}
return ;
}
上一篇:SharePoint2007使用WebPart加载UserControl


下一篇:如何一步一步用DDD设计一个电商网站(四)—— 把商品卖给用户