TopCoder13444 CountTables

题意：问在 $n\times m$ 的网格上染 $c$ 种颜色，问满足任意两行都不相同、任意两列都不相同的方案数。$n, m\leq 4000$，对 $10 ^ 9 + 7$ 取模。

首先如果我们只满足任意两列都不相同是容易做的，答案就是从 $c ^ n$ 种染法中依次选择 $m$ 种不相同的染色方案了，答案显然为 $\displaystyle \binom{c ^ n}m m!$。

对于任意两行都不相同，这个是不好做的，我们考虑容斥。设 $f_i$ 表示只考虑 $i\times m$ 网格的答案。假设最后有 $j$ 个互不相同的，那么这个的贡献就是 $f_j$。另外，我们需要把 $i$ 个行划分为 $j$ 个不相同的数，这个其实就是 $\displaystyle i\brace j$。

这样预处理第二类斯特林数即可，时间复杂度 $O(nm + n ^ 2)$。

class CountTables {
private:
	int f[N];
	void init()
	{
		for (int i = s[0][0] = 1; i < N; ++ i)
			for (int j = 1; j <= i; ++ j)
				s[i][j] = (s[i - 1][j - 1] + (LL) j * s[i - 1][j]) % Mod;
	}
	
	int A(int n, int m)
	{
		if (n < m) return 0;
		int cur = 1;
		for (int i = n; i > n - m; -- i) cur = (LL) cur * i % Mod;
		return cur;
	}
public:
	int howMany(int n, int m, int c) {
		init();
		for (int i = 1; i <= n; ++ i)
		{
			f[i] = A(qpow(c, i), m);
			for (int j = 1; j < i; ++ j)
				f[i] = (f[i] + (LL) (Mod - f[j]) * s[i][j]) % Mod;
		}
		return f[n];
	}
};