LightOJ 1246 Colorful Board (DP+组合数)

小鱼儿 2023-01-04 13:14 102阅读 0赞

题目连接：http://lightoj.com/volume\_showproblem.php?problem=1246

题意：有(M+1)\*(N+1)的棋盘，可以用k种油漆给它们染色。要求曼哈顿距离为奇数的格子不能染同一颜色(显然相邻格子的曼哈顿距离为1)，问总的染色方案数。

思路：问题可转化为：每个格子（x，y），x+y奇偶性不同的格子的颜色不能相同。于是棋盘被分成两部分，类似于国际象棋黑白相间的分法。

一种颜色要么不出现，要么只在一个部分出现。dp\[i\]\[j\]表示用j种颜色染i个格子且每种颜色都出现过的方案数，则dp\[i\]\[j\]=dp\[i\]\[j-1\]\*j+dp\[i-1\]\[j-1\]\*j

然后再乘以对应的组合数即可。

由组合数性质可以快速递推处理出所有需要的值，c\[i\]\[j\]表示从i中选出j个的选法数：c\[i\]\[j\]=c\[i-1\]\[j\]+c\[i-1\]\[j-1\]

#include <cstdio>
    
    const __int64 mod=1000000007;
    
    __int64 c[51][51],dp[210][51];
    //dp[i][j]表示用j种颜色染i个格子且每种颜色都出现过的方案数，则dp[i][j]=dp[i][j-1]*j+dp[i-1][j-1]*j
    
    void Init ()
    {
    	int i,j;
    	for (i=1;i<=50;i++)
    		c[i][1]=i,c[i][i]=1;
    	for (i=1;i<=50;i++) for (j=2;j<i;j++)
    		c[i][j]=(c[i-1][j]+c[i-1][j-1])%mod;
    	for (i=1;i<=205;i++)
    		for (j=1;j<=50;j++)
    		{
    			if (j==1) dp[i][j]=1;
    			else dp[i][j]=dp[i-1][j]*j+dp[i-1][j-1]*j;
    			dp[i][j]%=mod;
    		}
    }
    
    int main ()
    {
    	int T,n,m,k;
    	scanf("%d",&T);
    	Init ();
    	for (int Cas=1;Cas<=T;Cas++)
    	{
    		scanf("%d%d%d",&n,&m,&k);
    		if (n==0 && m==0)
    		{
    			printf("Case %d: %d\n",Cas,k);
    			continue;
    		}
    		n++,m++;
    		__int64 ans=0;
    		int x=(n+1)/2*((m+1)/2)+n/2*(m/2);//坐标为偶的个数
    		int y=n*m-x;
    		for (int i=1;i<k;i++)
    			for (int j=1;i+j<=k;j++)
    				ans=(ans+ (c[k][i]*c[k-i][j])%mod*((dp[x][i]*dp[y][j])%mod) )%mod;
    		printf("Case %d: %lld\n",Cas,ans);
    	}
    	return 0;
    }
    
    /*
    5
    19 19 50
    18 18 49
    17 16 45
    15 4 12
    10 2 50
    
    Case 1: 764066247
    Case 2: 858252451
    Case 3: 106772690
    Case 4: 863343629
    Case 5: 335018981
    */