这道题目是容斥原理的典型例题，主要体现了一种逆向思维。
如果我们试图直接考虑在某种情况下，每一行和每一列都“不完全为空”，会发现相对比较难以计算。此时可以反其道而行之，先把所有的情况算出来，然后再减去不合法的情况，会更好办些，这里就体现了容斥原理的思想。
使用容斥原理解决本题，大体上可以分为两种解决思路：
一、直接对整个棋盘进行容斥。
不考虑任何限制，每个格子就有黑和白两种状态，因此整个棋盘共有 2RC 种可能的状态。
接下来，我们考虑一个 3*3 的棋盘，不妨把第一行完全为空的状态集合记为 A ，则显然还剩下 6 个格子，对它们没有什么限制，每个都有黑与白两种可能，因此有 |A|=2(R−1)C。不难理解，第二行完全为白（ B ）、第三行完全为白（C）的方案数都和 A 是一样的。类似地，第一列完全为白（D）、第二列完全为白（ E ）和第三列完全为白（F）的方案数都为 2R(C−1) 。上面提到，合法方案数=总方案数-非法方案数，即
ans=2RC−(|A∪B∪C∪D∪E∪F|)注意到后面括号的部分很显然就是直接套用容斥原理，只需解决如何计算若干集合的并集即可。
在本题中，如果一个 R 行 C 列的棋盘中有 n 行 m 列完全为白，则剩余未被限制的格子个数为 (R−n)(C−m)=RC−nC−Rm+nm ，这种情况的状态数为 2未被限制格子个数 。（自己画一下草图很好理解，而且细心的话可以发现其实这个小式子里也有点容斥原理的味道）
但是直接这样分开枚举 A 和 B 之类的方法肯定是有问题的，时间复杂度达到 O(2RC) 级别，只能通过 30% 的测试数据。
不难发现发现，对于都有 n 行和 m 列同时为空的交集 S1 和 S2 ，它们的元素个数其实是一样的（如 |A∩D|=|A∩E| ），而 n 行 m 列为白的情况显然有 CnRCmC 种，也就是对于一定的 n 和 m，需要加上或减去的是
2RC−nC−Rm+nmCnRCmC更具体一点，当 n+m 为奇数时要减，为偶数时要加（结合具体例子并不难理解）。这样只需要枚举 n 和 m 就可以计算了，时间复杂度直接降到了 O(RC) 。
cdc 老师的 std：
#include <cstdio> #include <cstring> typedef long long LL; #define Mod 1000000007 LL C[2050][2050], pow2[4000050]; int main() { int N, M; scanf("%d%d", &N, &M); C[0][0] = 1; for (int i = 1; i <= N || i <= M; ++ i) { C[i][0] = 1; for (int j = 1; j <= i; ++ j) C[i][j] = (C[i-1][j-1] + C[i-1][j]) % Mod; } pow2[0] = 1; for (int i = 1; i <= N*M; ++ i) pow2[i] = pow2[i-1] * 2 % Mod; LL Ans = 0; for (int i = 0; i <= N; ++ i) for (int j = 0; j <= M; ++ j) Ans = (Ans + (((i+j)&1)*(-2)+1) * pow2[(N-i)*(M-j)] % Mod * C[N][i] % Mod * C[M][j] % Mod) % Mod; printf("%d\n", int( (Ans + Mod) % Mod )); return 0; }二、只对行进行容斥。
现在假设我们先忽略对列的限制。
在一行中，要求不完全为空，则要任意选 k 个格子涂黑（其中 1≤k≤C)，总共有
∑k=1CCkC 种方案，注意这个结果其实等于 2C−1 。对于 R 行，每一行都满足上面的式子。因此总的方案数为 (2C−1)R，这些是已经满足了行的限制，而没有考虑列的限制的情况。
接下来要做的就是再减去列的不合法情况。类似地，在每一行都不全为白色的前提下， i 列全为白的方案数为 (2C−i−1)R，再乘上 i 列全为白的可能情况 CiC 种，并跟上面同理，根据 i 的奇偶性，奇数减去，偶数加上即可。
虽然只需要枚举 i，看上去是 O(C) 的，但不要忘了组合数的预计算都需要 O(RC) ，因此实际上总的时间复杂度和第一种方法是一样的。
参考代码（写得这么丑当然是我的啦）：
#include <algorithm> #include <cstdio> #include <cstdlib> #include <cstring> #include <iostream> using namespace std; #define sign(x) (x&1?-1:1) const long long MOD = 1000000007LL; long long C[3000][3000]; /* long long C(int a, int b) { if (a < b) return 0LL; if (a - b < b) b = a - b; long long ret = 1LL; for (int i = a; i + b > a; i--) (ret *= i) %= MOD; return ret; } */ long long pow(int k, int p) { if (k == 0) return 1LL; else if (k == 1) return p; else { long long t = pow(k >> 1, p); if (k & 1) return t * t % MOD * p % MOD; else return t * t % MOD; } } long long g(int n, int m) { return pow(n, pow(m, 2) - 1); } long long f(int n, int m) { long long ret = g(n, m); for (int i = 1; i <= m; i++) { // printf("%lld %lld %lld\n", ); (ret += C[m][i] * g(n, m - i) % MOD * sign(i) + MOD) %= MOD; } return ret; } int main(void) { freopen("2161.in", "r", stdin); freopen("2161.out", "w", stdout); int n, m; scanf("%d%d", &n, &m); C[0][0] = 1; for (int i = 1; i <= max(n, m); i++) { C[i][0] = C[i][i] = 1LL; for (int j = 1; j < i; j++) C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % MOD; } printf("%I64d\n", f(n, m)); return 0; }