题目大意：有一个$n imes m$的网格图，若一个人的同一行或同一列有人，他就必须面向那个人，若都无人，就可以任意一个方向。若一个人无法确定方向，则方案不合法，问不同的方案数。$n,mleqslant3000$
题解：令$f_{n,m}$表示$n imes m$的网格图的答案。$f_{0,i}=f_{i,0}=1$，考虑在原来基础上加一列
1. 这一列是空的。$f_{n,m}+=f_{n,m-1}$
2. 这一列放一个人，且他所在的一行无人，那么他可以放在这一列的任意一个位置，并且可以向$4$个方向。$f_{n,m}+=4 imes nf_{n-1,m-1}$
3. 当$ngeqslant2$时，这一列放两个人，所以这两行都不能有人，这一列选取两个位置的方案数为$inom n2$。$f_{n,m}+=inom n2 f_{n-2,m-1}$
4. 当$mgeqslant2$时这一列放一个人，并且看向前面的一个人，这个人可以放在这一列的任意位置，并且前面一个人可以选择其中任意一列。$f_{n,m}+=n imes(m-1)f_{n-1,m-2}$
卡点：无
C++ Code：
#include <cstdio>
#include <algorithm>
#include <iostream>
#define mul(a, b) (static_cast<long long> (a) * (b) % mod)
const int maxn = 3010, mod = 1e9 + 7;
inline void reduce(int &x) { x += x >> 31 & mod; }
int n, m;
int f[maxn][maxn];
int main() {
std::ios::sync_with_stdio(false), std::cin.tie(0), std::cout.tie(0);
std::cin >> n >> m;
for (int i = 0; i <= n; ++i) {
for (int j = 0; j <= m; ++j) {
if (!i || !j) {
f[i][j] = 1;
continue;
}
f[i][j] = f[i][j - 1];
reduce(f[i][j] += mul(4, f[i - 1][j - 1]) * i % mod - mod);
if (i > 1)
reduce(f[i][j] += 1ll * i * (i - 1) / 2 % mod * f[i - 2][j - 1] % mod - mod);
if (j > 1)
reduce(f[i][j] += mul(i, j - 1) * f[i - 1][j - 2] % mod - mod);
}
}
reduce(--f[n][m]);
std::cout << f[n][m] << '
';
return 0;
}