hdu 2604 Queuing 矩阵快速幂

链接：http://acm.hdu.edu.cn/showproblem.php pid=2604

题意：给出一个队列，其中站着f（女人）m（男人），让你求出队列中不含有fmf和fff的队列总共的种类数（对M取模）。队列长度达到1e6肯定不能用排列组合做。是用递归顺序求的方式。因为要取模，所以不能打表，只能每次求，这样就需要用到矩阵快速幂来降低时间复杂度了。

递推公式：（a[i][0]~aa[i][3]分别代表mm,mf,fm,ff结尾的队列）

a[i][0]=a[i-1][2]+a[i-1][0]

a[i][1]=a[i-1][0]

a[i][2]=a[i-1][1]+a[i-1][3]

a[i][3]=a[i-1][1]

所以右乘矩阵 1 0 1 0 即可。

1 0 0 0

0 1 0 1

0 1 0 0

代码：

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       using namespace std; #define maxn 10 int M,K; struct Matrix { int n,m; int a[maxn][maxn]; Matrix operator *(const Matrix &b)const { Matrix tmp; tmp.n=n; tmp.m=m; memset(tmp.a,0,sizeof(tmp.a)); for(int i=0; i
      
       >=1; m=m*m; } return tmp; } int main() { while(scanf("%d%d",&K,&M)!=EOF) { Matrix aa; aa.n=aa.m=4; aa.a[0][0]=aa.a[0][2]=aa.a[1][0]=aa.a[2][1]=aa.a[2][3]=aa.a[3][1]=1; aa.a[0][1]=aa.a[0][3]=aa.a[1][1]=aa.a[1][2]=aa.a[1][3]=aa.a[2][0]=aa.a[2][2]=aa.a[3][0]=aa.a[3][2]=aa.a[3][3]=0; Matrix bb; bb.n=1,bb.m=4; bb.a[0][0]=bb.a[0][1]=bb.a[0][2]=bb.a[0][3]=1; aa=M_quick_pow(aa,K-2); bb=bb*aa; int ans=0; for(int i=0;i<4;i++) ans=(ans+bb.a[0][i])%M; printf("%d\n",ans); } }