@zzzc18 2017-09-24T08:45:38.000000Z 字数 1613 阅读 1365

2017.09.23 涂色游戏

TEST

Solution：

#include<cstdio>#include<cstring>#include<algorithm>using namespace std;typedef long long LL;const LL MAXN = 109;const LL MOD = 998244353;LL n,m,p,q;LL C[MAXN][MAXN];LL f[MAXN][MAXN];LL g[MAXN];struct Matrix{    LL num[MAXN][MAXN];    Matrix(){        memset(num,0,sizeof(num));    }};Matrix operator * (Matrix A,Matrix B){    LL i,j,k;    Matrix re;    for(i=1;i<=p;i++){        for(j=1;j<=p;j++){            for(k=1;k<=p;k++){                re.num[i][j]=(re.num[i][j]+A.num[i][k]*B.num[k][j])%MOD;            }        }    }    return re;}LL qpow_num(LL x,LL k){    LL i;    LL re=1,tmp=x;    for(i=1;i<=k;i<<=1){        if(i&k){            re*=tmp;            re%=MOD;        }        tmp*=tmp;        tmp%=MOD;    }    return re;}void INIT(){    LL i,j;    C[0][0]=1;    for(i=1;i<MAXN;i++){        C[i][0]=C[i][i]=1;        for(j=1;j<i;j++){            C[i][j]=(C[i-1][j]+C[i-1][j-1])%MOD;        }    }    f[0][0]=1;    for(i=1;i<MAXN;i++){        for(j=1;j<MAXN;j++){            f[i][j]=(f[i-1][j-1]*(p-(j-1))%MOD+f[i-1][j]*j%MOD)%MOD;        }    }    for(i=0;i<MAXN;i++)        g[i]=f[n][i];}LL calg(LL x){    return g[x]*qpow_num(C[p][x],MOD-2)%MOD;}void solve(){    Matrix ans,trans;    for(int i=1;i<=p;i++)ans.num[1][i]=g[i];    LL i,j,k;    for(i=1;i<=p;i++){        for(j=1;j<=p;j++){            for(k=max(q,max(i,j));k<=min(p,i+j);k++){                trans.num[i][j]=(trans.num[i][j]+C[i][i+j-k]*C[p-i][k-i])%MOD;            }            trans.num[i][j]=(calg(j)*trans.num[i][j])%MOD;        }    }    m--;    for(i=1;i<=m;i<<=1){        if(m&i){            ans=ans*trans;        }        trans=trans*trans;    }    LL ANS=0;    for(i=1;i<=p;i++){        ANS=(ANS+ans.num[1][i])%MOD;    }    printf("%lld\n",ANS);}int main(){    freopen("color.in","r",stdin);    freopen("color.out","w",stdout);    scanf("%lld%lld%lld%lld",&n,&m,&p,&q);    INIT();    solve();    return 0;}

• 私有
• 公开
• 删除