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);

    }

}