poj 3233 矩阵快速幂+YY

题意:给你矩阵A,求S=A+A^1+A^2+...+A^n

sol:直接把每一项解出来显然是不行的,也没必要。

我们可以YY一个矩阵:

poj 3233     矩阵快速幂+YY

其中1表示单位矩阵

然后容易得到:

poj 3233     矩阵快速幂+YY

可以看出这个分块矩阵的左下角那块就可以得到要求的解S

我们取这一块,再减去一个单位矩阵1即可。

 #include "iostream"
#include "vector"
#include "cstring"
#include "cstdio"
using namespace std; //typedef unsigned long int ULL;
typedef vector<int> vec;
typedef vector<vec> mat;
int n,m,k,P; mat mul(mat &A,mat &B) //return A*B
{
mat C(A.size(),vec(B[].size()));
for (int i=;i<(int)A.size();i++)
{
for (int k=;k<(int)B.size();k++)
{
for (int j=;j<(int)B[].size();j++)
{
C[i][j]=(C[i][j]+A[i][k]*B[k][j])%P;
}
}
}
return C;
} mat m_pow(mat A,int m) //return A^m
{
mat B(A.size(),vec(A.size()));
for (int i=;i<(int)A.size();i++)
B[i][i]=;
while (m>)
{
if (m&) B=mul(B,A);
A=mul(A,A);
m>>=;
}
return B;
} int main()
{
//freopen("in.txt","r",stdin); cin>>n>>k>>P;
mat A(*n,vec(*n)); for (int i=;i<n;i++)
for (int j=;j<n;j++)
cin>>A[i][j];
for (int i=n;i<=*n-;i++)
{
A[i][i-n]=;
A[i][i]=;
} A=m_pow(A,k+); for (int i=n;i<*n;i++)
{
for (int j=;j<n;j++)
{
if (i==j+n)
A[i][j]--;
if (A[i][j]<) A[i][j]+=P;
cout<<A[i][j]<<" ";
}
cout<<endl;
}
return ;
}

注意:挑战程序设计那本书P205上取了左上角那块,估计是写错了orz

----------------------------

本题还有一种方法,reference:  http://www.cnblogs.com/ACShiryu/archive/2011/08/09/poj3233.html

上一篇:C++调用Object-C界面


下一篇:Android--从相册中选取照片并返回结果