Colorful Board Lightoj 考虑一周多后的灵感

Colorful Board Lightoj 思考一周多后的灵感

#include<stdio.h>
#include<string.h>
 
typedef long long lld;
const int mod=1000000007;
const int maxn=55;
lld dp[maxn][maxn][maxn];//dp[i][j][k]前i种颜色,奇的格子为j，偶的格子为k
 
void init(){
    int i,j,k;
    memset(dp,0,sizeof(dp));
    dp[0][0][0]=1;
    for(i=1;i<=50;i++)
        for(j=0;j<=50;j++)
            for(k=0;k<=50;k++){
                dp[i][j][k]+=dp[i-1][j][k];
                dp[i][j+1][k]+=dp[i-1][j][k];
                dp[i][j][k+1]+=dp[i-1][j][k];
 
                dp[i][j][k]%=mod;
                dp[i][j+1][k]%=mod;
                dp[i][j][k+1]%=mod;
            }
}

int n,m,g;
//次dp求len长度的不同格子，用k种颜色图的方案数，每种颜色至少用一次
lld p[205][maxn];//DP[i][j]表示长度为i用了j种颜色的方案数

lld Gao(int tot,int len){
    int i,j,k;
    memset(p,0,sizeof(p));
    p[0][0]=1;
    for(i=0;i<len;i++)
		for(j=0;j<=i && j<=tot ;j++){
			p[i+1][j]=(p[i+1][j]+p[i][j]*j)%mod;
			if(j<tot)
			p[i+1][j+1]=(p[i+1][j+1]+p[i][j]*(tot-j))%mod;
		}

    return p[len][tot];
}

lld J[205][maxn];

void Kao(){
	for(int i=1;i<=200;i++){
		for(int j=1;j<maxn;j++)
			J[i][j]=Gao(j,i);
	}
}

int main(){
    int T;
    int i,j;
    int even,odd;
    lld ans;
    init();
	Kao();
    scanf("%d",&T);
    for(int cas=1;cas<=T;cas++){
        scanf("%d%d%d",&n,&m,&g);
        if(n+m==0){
            printf("Case %d: %d\n",cas,g);
            continue;
        }
        ans=0;
        n++;m++;
        even=odd=0;
        for(i=1;i<=n;i++)
            for(j=1;j<=m;j++)
                if((i+j)%2)odd++;
                else even++;
        for(i=1;i<=g;i++)
            for(j=1;j+i<=g;j++){
                lld tp=J[odd][i]*J[even][j]%mod;
                ans=(ans+ (dp[g][i][j]*tp)%mod)%mod;
            }
        printf("Case %d: %lld\n",cas,ans);
    }
    return 0;
}