2017.09.23 涂色游戏

TEST

题目：

Solution：

这里采用颜色数来进行计数（不然岂不是不可做？）
然后就顺理成章地有了以下内容

上述算法复杂度是 $O(n^2m+n^3)$ 显然不可接受
但是我们考虑 $dp[i][k]=dp[i-1][j]*trans[j][k]$ 的过程就类似于矩阵的乘法($C_{ij}=\sum_{k=1}^pA_{ik} \times B_{kj}$)
这样，把 $DP$ 作为左边的矩阵，$trans$ 作为右边的矩阵，答案就是 $DP \times trans^{m-1}$

#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;
}