CQOI 2011 放棋子

题意

有一个 (w imes h) 的棋盘，有 (c) 种颜色的棋子，第 (i) 种棋子有 (a_i) 个。他想把棋子全部摆到棋盘上，使得每个格子上至多有 (1) 个棋子，并且同一行同一列不能有两个不同的棋子

请求出有多少种放旗子的方案取模 (10^9+7)

解法

好神的 DP 啊，给我一辈子我都想不出来

设第 (i) 种棋子分布在了 (x) 行，(y) 列，那么这些行列一定不会有其他颜色的棋子出现

我们把这 (x) 行，(y) 列移动到矩形的边界（相当于抽出来放到一边），新问题就是原问题的一个子问题：颜色种数减少了 (1)，行数减少了 (x)，列数减少了 (y)

设 (g_{i,j,k}) 为第 (i) 种颜色的棋子分布在 (j) 行，(k) 列的方案数，这个可以容斥求出

(g_{i,j,k}) 的初值为 (i imes j choose a_k)，也就是在交叉点随意选取的方案数。显然这样会有一些行和列为空，考虑把这一部分不合法的方案容斥掉，即 (g_{i,j,k}-sum g_{i,u,v} (uleq j,vleq k))

求出 (g) 之后就可以 DP 了，显然一种种添加某个颜色是 DP 的最好方式

设 (f_{i,j,k}) 为第 (i) 种颜色分布在 (j) 行，(k) 列的方案数，那么

[f_{i,j,k}=f_{i-1,j-u,k-v} imes g_{a_i,u,v} imes{jchoose u} imes {kchoose v} ]

时间复杂度 (O(N^5))

代码

#include <cstdio>

using namespace std;

const int MAX_N = 50;
const int mod = 1e9 + 7;

int N, M, K;

int a[MAX_N];
int f[MAX_N][MAX_N][MAX_N], g[MAX_N][MAX_N][MAX_N], C[MAX_N * MAX_N][MAX_N * MAX_N]; 

inline void inc(int& x, int y) { (x += y) >= mod ? x -= mod : 0; }

void get_C() {
	for (int i = 0; i <= N * M; ++i) {
		C[i][0] = 1;
		for (int j = 1; j <= i; ++j)  inc(C[i][j], C[i - 1][j] + C[i - 1][j - 1]);
	}
}

int main() {
	
	scanf("%d%d%d", &N, &M, &K);
	
	for (int i = 1; i <= K; ++i)  scanf("%d", a + i);
	
	get_C();
	
	for (int c = 1; c <= K; ++c)
		for (int i = 1; i <= N; ++i)
			for (int j = 1; j <= M; ++j) {
				g[c][i][j] = C[i * j][a[c]];
				for (int u = 0; u <= i; ++u)
					for (int v = 0; v <= j; ++v)
						if (u + v)  
							inc(g[c][i][j], mod - 1LL * C[i][u] * C[j][v] % mod * g[c][i - u][j - v] % mod);
			}
	
	for (int i = 0; i <= N; ++i)
		for (int j = 0; j <= M; ++j)  f[0][i][j] = 1;
	
	for (int c = 1; c <= K; ++c)
		for (int i = 1; i <= N; ++i)
			for (int j = 1; j <= M; ++j)
				for (int u = 0; u <= i; ++u)
					for (int v = 0; v <= j; ++v)
						if (u + v)
							inc(f[c][i][j], 1LL * f[c - 1][i - u][j - v] * C[i][u] % mod * C[j][v] % mod * g[c][u][v] % mod);
	
	printf("%d
", f[K][N][M]);
		
	return 0;
}