[题解] [JSOI2015] 染色问题

题面

题解

这类问题似乎都会跟容斥扯上一点关系??? 或许是我题做的比较少吧

设 (f[i][j][k]) 代表至少还有 (i) 行. (j) 列没有一个格子被染色, 至少还有 (k) 种颜色未用到

则有

[displaystyle\f[i][j][k] = inom{n}{i}inom{m}{j}inom{c}{k}(c- k+1)^{(n - i) * (m - j)} ]

代表从 (n) 行中选 (i) 行不染, (m) 列中选 (j) 列不染, (c) 种中选 (k) 种不用, 其余的格子不染或染这 (c - k) 中的各种颜色均可的方案数

总方案数就是

[displaystyle\sum_{i=0}^{n}sum_{j=0}^{m}sum_{k=0}^{c}(-1)^{i+j+k}f[i][j][k] ]

Code

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
const int N = 405;
const int mod = 1e9 + 7; 
using namespace std;

int n, m, K, c[N][N], pw[N * N], ans; 

template < typename T >
inline T read()
{
	T x = 0, w = 1; char c = getchar();
	while(c < '0' || c > '9') { if(c == '-') w = -1; c = getchar(); }
	while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
	return x * w; 
}

int main()
{
	n = read <int> (), m = read <int> (), K = read <int> ();
	for(int i = 0; i <= 400; i++)
		for(int j = 0; j <= i; j++)
			c[i][j] = (!j ? 1 : (c[i - 1][j - 1] + c[i - 1][j]) % mod); 
	for(int k = 0; k <= K; k++)
	{
		for(int i = (pw[0] = 1); i <= n * m; i++) pw[i] = 1ll * pw[i - 1] * (K - k + 1) % mod; 
		for(int i = 0; i <= n; i++)
			for(int j = 0; j <= m; j++)
				ans = (ans + 1ll * ((i + j + k) & 1 ? mod - 1 : 1) * c[n][i] % mod * c[m][j] % mod * c[K][k] % mod * pw[(n - i) * (m - j)] % mod) % mod; 
	}
	printf("%d
", ans); 
	return 0; 
}