题目链接：HDOJ - 5155
题目大意
有一个 n * m 的棋盘，已知每行每列都至少有一个棋子，求可能有多少种不同的棋子分布情况。答案对一个大素数取模。
题目分析
算法1：
使用容斥原理与递推。
首先，一个 n * m 的棋盘不考虑任何限制时，可能的分布情况为 2^(n*m) ，除去没有棋子的情况，为 2^(n*m) - 1 。
然后，因为所有的 n 行，m 列都有棋子，所以枚举 ii (1 <= ii <= i) ， jj (1 <= jj <= j) 。对于枚举的一组 (ii, jj) ，若 (ii, jj) != (i, j) ，f[i][j] 就是恰好有 i 行 j 列都有棋子的情况数，再乘上在 i 行中选 ii 行 ( C[i][ii] ) ，在 j 列中选 jj 列的情况数( C[j][jj] )，就是在 i * j 的棋盘中，恰好有 ii 行， jj 列有棋子的情况数。(i, j) 的答案 f[i][j] 要减去这个值。
这样就递推出了所有的 f[i][j] 。时间复杂度 O(n^4) 。
注意的问题：组合数用递推来求。 C[i][0] = 1, C[i][j] = C[i-1][j-1] + C[i-1][j]; 进行递推时注意取模之后的数相乘会爆 Int 。
算法2：
考虑一种 DP ，使用 f[i][j] 表示前 i 行都有棋子，然而只有 j 列有棋子的方案数。
那么我们考虑第 i + 1 行的棋子放置情况，我们枚举第 i + 1 行棋子放置的个数 k ，再枚举这 k 个棋子中有 t 个放在之前没有棋子的列中。
那么就有一个状态转移 ： f[i+1][j+t] += f[i][j] * C[j][k-t] * C[m-j][t] 。
时间复杂度同样是 O(n^4) 。
代码
算法1
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm> using namespace std; const int MaxN = 50 + 5, Mod = 1000000007; int n, m;
int C[MaxN][MaxN], f[MaxN][MaxN], Pow2[MaxN * MaxN]; void Init_C() {
C[0][0] = 1;
for (int i = 1; i <= 50; ++i) {
C[i][0] = 1;
for (int j = 1; j <= i; ++j) {
C[i][j] = C[i - 1][j - 1] + C[i - 1][j];
C[i][j] %= Mod;
}
}
Pow2[0] = 1;
for (int i = 1; i <= 2500; ++i) {
Pow2[i] = Pow2[i - 1] << 1;
Pow2[i] %= Mod;
}
} typedef long long LL; int main()
{
Init_C();
for (int i = 1; i <= 50; ++i) {
for (int j = 1; j <= 50; ++j) {
f[i][j] = Pow2[i * j] - 1;
for (int ii = 1; ii <= i; ++ii) {
for (int jj = 1; jj <= j; ++jj) {
if (ii == i && jj == j) continue;
f[i][j] -= (LL)f[ii][jj] % Mod * (LL)C[i][ii] % Mod * (LL)C[j][jj] % Mod;
f[i][j] %= Mod;
}
}
f[i][j] = (f[i][j] + Mod) % Mod;
}
}
while (scanf("%d%d", &n, &m) != EOF) {
if (n == 0 || m == 0) {
printf("1\n"); continue;
}
printf("%d\n", f[n][m]);
}
return 0;
}
算法2就不写代码了。