上课讲的一道题，感觉也挺厉害的~正解是容斥 + 状压dp。首先我们容易发现一共可能的局部最小值数量是十分有限的，最多也只有 (8) 个。所以我们可以考虑状压。
建立出状态 (f[i][j]) 表示我们从小到大往方格当中填数，填完前(i) 个数之后，局部最小值的填充状态为 (j) 的方案数。这样一共有两种转移 ：
(f[i][j] = f[i - 1][j] * (g[j] - ((i - 1) - |j|)) + sum f[i][j'])
分别表示加入了一个局部最小值 / 其他位置的值。其中的 (g[j]) 表示在 (j) 的状态下可以放入的非局部最小值的个数。但这样做出来还是不够的——我们虽然保证了要求的位置上一定是局部最小值，但是其余的位置上也有可能是局部最小值，而这是不符合要求的。我们考虑用容斥来处理，用全集 - 至少有一个非局部最小值成为了局部最小值的方案数，+至少两个，-至少三个……
每一个dfs出来的状态都用上面的方法dp加入到答案中去就可以了。
#include <bits/stdc++.h> using namespace std; #define maxn 400 #define maxm 500 #define int long long #define mod 12345678 int n, m, N, tot, cnt, ans; int Map[maxn][maxn], id[maxn][maxn]; int f[maxn][maxm], g[maxm], T; int dx[10] = {-1, 0, 1, -1, 1, -1, 0, 1}; int dy[10] = {-1, -1, -1, 0, 0, 1, 1, 1}; struct node { int x, y; }P[maxn]; void Up(int& x, int y) { x = (x + y) % mod; } int DP() { int K = (1 << tot) - 1; for(int k = 0; k <= K; k ++) { g[k] = 0; int tem = k, len = 0; while(tem) len += (tem & 1), tem >>= 1; for(int i = 1; i <= n; i ++) for(int j = 1; j <= m; j ++) { int flag = 0; if(Map[i][j]) continue; for(int l = 0; l < 8; l ++) { int x = i + dx[l], y = j + dy[l]; if(Map[x][y] && !((1 << (id[x][y] - 1)) & k)) { flag = 1; break; } } if(!flag) g[k] ++; } g[k] += len; } memset(f, 0, sizeof(f)); f[0][0] = 1; for(int i = 1; i <= N; i ++) for(int j = 0; j <= K; j ++) { Up(f[i][j], f[i - 1][j] * (g[j] - (i - 1))); int tem = j, len = 0; while(tem) len ++, tem >>= 1; for(int k = 0; k < len; k ++) if(j & (1 << k)) Up(f[i][j], f[i - 1][j ^ (1 << k)]); } return f[N][K]; } void DFS(int x, int y) { if(y > m) x += 1, y = 1; if(x > n) { if((tot - cnt) & 1) ans = (ans - DP() + mod) % mod; else ans = (ans + DP()) % mod; return; } DFS(x, y + 1); if(Map[x][y]) return; for(int i = 0; i < 8; i ++) if(Map[x + dx[i]][y + dy[i]]) return; Map[x][y] = 1, P[++ tot].x = x, P[tot].y = y; id[x][y] = tot; DFS(x, y + 1); tot --, Map[x][y] = 0, id[x][y] = 0; } signed main() { scanf("%lld%lld", &n, &m); N = n * m; for(int i = 1; i <= n; i ++) for(int j = 1; j <= m; j ++) { char c; cin >> c; if(c == 'X') { P[++ tot].x = i, P[tot].y = j; Map[i][j] = 1, id[i][j] = tot; } } cnt = tot; for(int i = 1; i <= tot; i ++) { T |= (1 << (i - 1)); for(int j = 0; j < 8; j ++) if(Map[P[i].x + dx[j]][P[i].y + dy[j]]) { printf("0"); return 0; } } DFS(1, 1); printf("%lld ", ans); return 0; }