poj 3233 Matrix Power Series 矩阵求和

http://poj.org/problem?id=3233

题解 矩阵快速幂+二分等比数列求和

AC代码

#include <stdio.h>
#include <math.h>
#include <string.h>
#include <stdlib.h>
#include <iostream>
#include <sstream>
#include <algorithm>
#include <string>
#include <queue>
#include <map>
#include <vector>
using namespace std;
const int maxn = ;
const int inf = 0x3f3f3f3f,mod = ;
const double epx = 1e-;
typedef long long ll;
struct Matrix
{
int m[maxn][maxn]; //有哪位大佬知道为什么数组开大了会 Runtime Error
};
Matrix A,I;
int n,m,k;
Matrix add(Matrix a,Matrix b)
{
Matrix c;
for(int i=;i<n;i++)
{
for(int j=;j<n;j++)
{
c.m[i][j]=a.m[i][j]+b.m[i][j];
c.m[i][j]%=m;
}
}
return c;
}
Matrix multi(Matrix a,Matrix b)
{
Matrix c;
for(int i=;i<n;i++)
{
for(int j=;j<n;j++)
{
c.m[i][j]=;
for(int k=;k<n;k++)
{
c.m[i][j]+=a.m[i][k]*b.m[k][j];
}
c.m[i][j]%=m;
}
}
return c;
}
Matrix poww(Matrix a,int n)
{
Matrix ans=I;
while(n>)
{
if(n&)
ans=multi(ans,a);
n=n>>;
a=multi(a,a);
}
return ans;
}
Matrix sum(Matrix a,int n)
{
if(n==) return a;
Matrix t=sum(a,n/);
if(n&)
{
Matrix cur=poww(a,n/+);
t=add(t,multi(t,cur));
t=add(t,cur);
}
else
{
Matrix cur=poww(a,n/);
t=add(t,multi(t,cur));
}
return t;
}
int main()
{
cin>>n>>k>>m;
for(int i=;i<n;i++)
{
for(int j=;j<n;j++)
{
cin>>A.m[i][j];
A.m[i][j]%=m;
I.m[i][j]=(i==j);
}
}
Matrix ans=sum(A,k);
for(int i=;i<n;i++)
{
for(int j=;j<n;j++)
{
cout<<ans.m[i][j]<<" ";
}
cout<<endl;
}
return ;
}
上一篇:POJ3233 Matrix Power Series 矩阵乘法


下一篇:我关注的一些关于前端的文章(copy)