hdu2604 queuing(dp+矩阵倍增)

63 阅读 0 评论 42 点赞

我是靠谱客的博主过时往事，最近开发中收集的这篇文章主要介绍hdu2604 queuing(dp+矩阵倍增)，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

f[i]表示i个人排队时为E-queue的方案数。则有：f[n]=f[n-1]+f[n-3]+f[n-4]
解释一下：第n个人为m时，前n-1个只要合法就行，所以是f[n-1].
第n个人为f时，前n-1个人合法不能保证这n个都合法，我们再看第n-1位，第n-1位为m时，第n-2为显然只能是m,这样的话只要保证前n-3个合法即可，所以是f[n-3]。第n-1位为f时，第n-2为显然只能是m，第n-3位显然只能是m，所以只要保证前n-4位合法即可，所以是f[n-4].

#include <cstdio>
#include <cstring>
#define ll long long
int const N=4;
int mod,n;
struct matrix{
    int mat[N][N];
    matrix(bool t){
        memset(mat,0,sizeof(mat));
        if(t) for(int i=0;i<4;++i) mat[i][i]=1;
    }
    matrix operator*(matrix b){
        matrix re(false);
        for(int i=0;i<4;++i)
            for(int j=0;j<4;++j)
                for(int k=0;k<4;++k)
                    re.mat[i][j]=((ll)re.mat[i][j]+mat[i][k]*b.mat[k][j])%mod;
        return re;
    }
    matrix operator^(int k){
        matrix re(true);
        matrix base(false);
        memcpy(base.mat,mat,sizeof(mat));
        for(;k;k>>=1,base=base*base)
            if(k&1)  re=re*base;
        return re;
    }
};
int main(){
//  freopen("hdu2604.in","r",stdin);
    matrix trans(false);
    trans.mat[1][0]=1;
    trans.mat[2][1]=1;
    trans.mat[3][2]=1;
    trans.mat[0][3]=1;
    trans.mat[1][3]=1;
    trans.mat[3][3]=1;
    matrix ans(false);
    ans.mat[0][0]=1;
    ans.mat[0][1]=2;
    ans.mat[0][2]=4;
    ans.mat[0][3]=6;
    while(scanf("%d%d",&n,&mod)!=EOF){
        matrix a(false);
        a=trans^(n-3);
        matrix res(false);
        res=ans*a;
        printf("%dn",res.mat[0][3]);
    }
    return 0;
}