NKOJ 2040 （CQOI 2011）放棋子（递推+容斥原理+组合数）

P2040【CQOI2011】放棋子

问题描述

在一个n行m列的棋盘里放一些彩色的棋子，使得每个格子最多放一个棋子，且不同颜色的棋子不能在同一行或者同一列。有多少种方法？ 例如，n=m=3，有两个白棋子和一个灰棋子，下面左边两种方法都是合法的，但右边两种都是非法的。

输入格式

输入第一行为两个整数n, m, c，即行数、列数和棋子的颜色数。第二行包含c个正整数，即每个颜色的棋子数。所有颜色的棋子总数保证不超过nm。

输出格式

输出仅一行，即方案总数除以 1,000,000,009的余数。

样例输入1：

5 2 3
1 1 1

样例输入2：

4 2 2
3 1

样例输入3：

8 8 8
1 1 1 1 1 1 1 1

样例输出1：

0

样例输出2：

8

样例输出3：

625702391

数据范围

编号 1-2 3-5 6-7 8-10
n, m <=4 <=10 <=30 <=30
c <=2 <=5 <=2 <=10
总棋子数 <=5 <=20 <=900 <=250

---

此题显然考虑递推，关键是如何定状态，关键是要注意到不同颜色的棋子既不在同一行，也不在同一列。

那么对于单一颜色，令$G[k][x][y]$表示将颜色为k的棋子，恰好放在$x$行，$y$列中，保证每一行，每一列至少有一个棋子的方案数
那么考虑用容斥原理求解，用$A[k]$表示第$k$种棋子的棋子数，那么有，
$$
G[k][x][y]=C_{x\times y}^{A[k]}-\sum_{i=0}^{x}\sum_{j=0}^{y}(C_{x}^{x-i}\times C_{y}^{y-j}\times G[k][x-i][y-j])，其中i，j不同时为0
$$
那么先求出$G[k][x][y]$
然后考虑多种颜色，用$F[k][x][y]$表示将前$k$种颜色的棋子放在恰好$x$行，$y$列中，保证每一行，每一列至少有一个棋子的方案数

考虑第$k$种颜色的棋子占了$i$行，$j$列，有
$$
F[k][x][y]=\sum_{i=1}^{x} \sum_{j=1}^{y}(C_{n+i-x}^{i}\times C_{m+j-y}^{j}\times F[k-1][x-i][y-j]\times G[k][i][j])
$$
最后统计答案，有
$$
ans=\sum_{i=1}^{n} \sum_{j=1}^{m}F[c][i][j]
$$

---

代码：

#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<cstring>
#define ll long long
using namespace std;
ll ans,n,m,c,A[15],C[1005][1005],G[15][33][33],F[15][33][33],mod=1000000009;
int main()
{
	ll i,j,k,x,y;
	scanf("%lld%lld%lld",&n,&m,&c);
	for(i=1;i<=c;i++)scanf("%lld",&A[i]);
	for(i=0;i<=1000;i++)C[i][0]=1;
	for(i=1;i<=1000;i++)
	for(j=1;j<=1000;j++)C[i][j]=(C[i-1][j-1]+C[i-1][j])%mod;
	
	for(k=1;k<=c;k++)
	for(i=1;i<=min(n,A[k]);i++)
	for(j=1;j<=min(m,A[k]);j++)
	{
		G[k][i][j]=C[i*j][A[k]];
		for(x=0;x<i;x++)
		for(y=0;y<j;y++)
		if(x||y)G[k][i][j]=(G[k][i][j]-C[i][i-x]*C[j][j-y]%mod*G[k][i-x][j-y])%mod;
	}
	
	F[0][0][0]=1;
	for(k=1;k<=c;k++)
	for(i=1;i<=n;i++)
	for(j=1;j<=m;j++)
	for(x=1;x<=min(i,A[k]);x++)
	for(y=1;y<=min(j,A[k]);y++)
	F[k][i][j]=(F[k][i][j]+C[n+x-i][x]*C[m+y-j][y]%mod*F[k-1][i-x][j-y]%mod*G[k][x][y]%mod)%mod;
	
	for(i=1;i<=n;i++)
	for(j=1;j<=m;j++)ans=(ans+F[c][i][j])%mod;
	printf("%lld",(ans+mod)%mod);
}