bzoj 4487/ jsoi 2015 染色问题（容斥原理

Description

棋盘是一个n×m的矩形，分成n行m列共n*m个小方格。
现在萌萌和南南有C种不同颜色的颜料，他们希望把棋盘用这些颜料染色，并满足以下规定：
1.棋盘的每一个小方格既可以染色（染成C种颜色中的一种），也可以不染色。
2.棋盘的每一行至少有一个小方格被染色。
3.棋盘的每一列至少有一个小方格被染色。
4.种颜色都在棋盘上出现至少一次。
以下是一些将3×3棋盘染成C=3种颜色（红、黄、蓝）的例子：

请你求出满足要求的不同的染色方案总数。只要存在一个位置的颜色不同，
即认为两个染色方案是不同的

Input

输入只有一行 3 个整数n,m,c。1 < = n,m,c < = 400

Output

输出一个整数，为不同染色方案总数。
因为总数可能很大，只需输出总数mod 1,000,000,007的值。

Sample Input

2 2 3

Sample Output

60

分析

这道题有三个限制条件：每行要涂，每列要涂，每种颜色要用上。考虑它的反面：有行没涂，有列没涂，有颜色没用，利用这一点来容斥。记 $f(i,j,k)$f(i,j,k) 表示特定的 $i$i 行没涂， $j$j 列没涂， $k$k 种颜色没用的方案数。显然 $f(i,j,k)=(c-k{)}^{(n-i)\ast (m-j)}$f(i,j,k)=(c−k)(n−i)∗(m−j)
于是 $ans=\sum _{i=0}^n\sum _{j=0}^n\sum _{k=0}^c(-1{)}^{i+j+k}{C}_n^i{C}_m^j{C}_c^{k}f(i,j,k)=\sum _{i=0}^n\sum _{j=0}^n\sum _{k=0}^c(-1{)}^{i+j+k}{C}_n^i{C}_m^j{C}_c^k(c-k{)}^{(n-i)\ast (m-j)}$ans=i=0∑n​j=0∑n​k=0∑c​(−1)i+j+kCni​Cmj​Cck​f(i,j,k)=i=0∑n​j=0∑n​k=0∑c​(−1)i+j+kCni​Cmj​Cck​(c−k)(n−i)∗(m−j)

代码如下

#include <bits/stdc++.h>
#define mod 1000000007
#define LL long long
using namespace std;
int c[405][405], P[160005];
LL z = 1, ans;
int ksm(int a, int b, int p){
	int s = 1;
	if(!a) return 1;
	while(b){
		if(b & 1) s = z * s * a % p;
		a = z * a * a % p;
		b >>= 1;
	}
	return s;
}
int main(){
	int i, j, n, m, k, t;
	for(i = 0; i <= 400; i++){
		c[i][0] = 1;
		for(j = 1; j <= i; j++) c[i][j] = (c[i-1][j] + c[i-1][j-1]) % mod;
	}
	scanf("%d%d%d", &n, &m, &k);
	for(t = 0; t <= k; t++){
		for(P[0] = i = 1; i <= n * m; i++) P[i] = z * P[i-1] * (k - t + 1) % mod;
		for(i = 0; i <= n; i++){
			for(j = 0; j <= m; j++){
				if((i + j + t) % 2) ans = (ans - z * c[n][i] * c[m][j] % mod * c[k][t] % mod * P[(n - i) * (m - j)]) % mod;
				else ans = (ans + z * c[n][i] * c[m][j] % mod * c[k][t] % mod * P[(n - i) * (m - j)]) % mod;
				
			}
		}
	}
	printf("%lld", (ans % mod + mod) % mod);
	return 0;
}