首页 > 代码库 > poj 3734 矩阵快速幂+YY
poj 3734 矩阵快速幂+YY
题目原意：N个方块排成一列，每个方块可涂成红、蓝、绿、黄。问红方块和绿方块都是偶数的方案的个数。
sol：找规律列递推式+矩阵快速幂
设已经染完了i个方块将要染第i+1个方块。
a[i]=1-i方块中，红、绿方块数量都是偶数的方案数
b[i]=1-i方块中，红、绿方块数量一个是偶数一个是奇数的方案数（红even绿odd 或 红odd绿even）
c[i]=1-i方块中，红、绿方块数量都是奇数的方案数
可以得出递推公式：
a[i+1]=2*a[i]+b[i]
b[i+1]=2*a[i]+2*b[i]+2*c[i]
c[i+1]=b[i]+2*c[i]
如何和矩阵结合起来呢？不妨把公式这样写一遍，
a[i+1]=2*a[i]+1*b[i]+0*c[i]
b[i+1]=2*a[i]+2*b[i]+2*c[i]
c[i+1]=0*a[i]+1*b[i]+2*c[i]
然后可以YY出一个矩阵：
因此，
这样就可以用矩阵快速幂求解了。
1 #include "iostream" 2 #include "vector" 3 #include "cstring" 4 using namespace std; 5 6 typedef unsigned long int ULL; 7 typedef vector<ULL> vec; 8 typedef vector<vec> mat; 9 const ULL P=10007;10 int n,m;11 12 mat mul(mat &A,mat &B) //return A*B13 {14 mat C(A.size(),vec(B[0].size()));15 for (int i=0;i<(int)A.size();i++)16 {17 for (int k=0;k<(int)B.size();k++)18 {19 for (int j=0;j<(int)B[0].size();j++)20 {21 C[i][j]=(C[i][j]+A[i][k]*B[k][j])%P;22 }23 }24 }25 return C;26 }27 28 mat m_pow(mat A,int m) //return A^m29 {30 mat B(A.size(),vec(A.size()));31 for (int i=0;i<(int)A.size();i++)32 B[i][i]=1;33 while (m>0)34 {35 if (m&1) B=mul(B,A);36 A=mul(A,A);37 m>>=1;38 }39 return B;40 }41 42 int main()43 {44 int T,N;45 cin>>T;46 while (T--)47 {48 cin>>N;49 mat A(3,vec(3));50 A[0][0]=2; A[0][1]=1; A[0][2]=0;51 A[1][0]=2; A[1][1]=2; A[1][2]=2;52 A[2][0]=0; A[2][1]=1; A[2][2]=2;53 54 A=m_pow(A,N);55 56 cout<<A[0][0]<<endl;57 }58 return 0;59 }60 61 /*62 int main()63 {64 int T;65 cin>>T;66 while (T--)67 {68 cin>>n>>m;69 mat A(n,vec(n));70 71 for (int i=0;i<n;i++)72 for (int j=0;j<n;j++)73 cin>>A[i][j];74 75 A=m_pow(A,m);76 77 ULL ans=0;78 for (int i=0;i<n;i++)79 {80 ans+=A[i][i];81 ans=ans%P;82 }83 cout<<ans<<endl;84 }85 return 0;86 }87 */
poj 3734 矩阵快速幂+YY
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。