题目传送门
https://lydsy.com/JudgeOnline/problem.php?id=2669
题解
可以发现一个 \(4\times 7\) 的矩阵中，有局部最小值的点最多有 \(2\times 4 = 8\) 个，所以我们可以状压一下每个局部最小值的位置有没有被选。
从小到大填入每一个格子，那么如果一个点的周围有没有被填上的局部最小值，那么这个格子不可以被填。所以预处理一下每种状态下可以*填多少格子，然后如果状态保持不变的话，就可以这样转移。
如果状态变化，就是说填了一个局部最小值的话，那么久直接加上当前状态的答案就可以了。
但是这样会有问题：被*填的位置，可能会出现多余的局部最小值，也就说不该是局部最小值的地方出现了局部最小值——那么就直接容斥一下就好了，直接搜索一个各种合法状态，都 DP 一下。
这个 DP 的复杂度很显然是 \(O(nm \cdot 8 \cdot 2^8)\)，但是搜索我就不太会算了。总之可以轻松的过掉。
#include<bits/stdc++.h>
#define fec(i, x, y) (int i = head[x], y = g[i].to; i; i = g[i].ne, y = g[i].to)
#define dbg(...) fprintf(stderr, __VA_ARGS__)
#define File(x) freopen(#x".in", "r", stdin), freopen(#x".out", "w", stdout)
#define fi first
#define se second
#define pb push_back
template<typename A, typename B> inline char smax(A &a, const B &b) {return a < b ? a = b, 1 : 0;}
template<typename A, typename B> inline char smin(A &a, const B &b) {return b < a ? a = b, 1 : 0;}
typedef long long ll; typedef unsigned long long ull; typedef std::pair<int, int> pii;
template<typename I> inline void read(I &x) {
int f = 0, c;
while (!isdigit(c = getchar())) c == '-' ? f = 1 : 0;
x = c & 15;
while (isdigit(c = getchar())) x = (x << 1) + (x << 3) + (c & 15);
f ? x = -x : 0;
}
const int N = 4 * 7 + 7;
const int M = (1 << 8) + 7;
const int dx[] = {0, 1, 1, 1, 0, -1, -1, -1}, dy[] = {1, 1, 0, -1, -1, -1, 0, 1};
const int P = 12345678;
int n, m, pcnt, cnt, S, ans;
pii p[N];
int wy[M], dp[N][M];
char a[N][N], b[N][N], mk[5][8];
inline int smod(int x) { return x >= P ? x - P : x; }
inline void sadd(int &x, const int &y) { x += y; x >= P ? x -= P : x; }
inline int fpow(int x, int y) {
int ans = 1;
for (; y; y >>= 1, x = (ll)x * x % P) if (y & 1) ans = (ll)ans * x % P;
return ans;
}
inline void ycl() {
S = (1 << cnt) - 1;
memset(wy, 0, sizeof(wy));
for (int s = 0; s <= S; ++s) {
int &ans = wy[s];
memset(mk, 0, sizeof(mk));
for (int i = 1; i <= cnt; ++i) if (!((s >> (i - 1)) & 1)) {
int x = p[i].fi, y = p[i].se;
mk[x][y] = 1;
for (int i = 0; i < 9; ++i) {
int px = x + dx[i], py = y + dy[i];
if (px < 1 || px > n || py < 1 || py > m) continue;
mk[px][py] = 1;
}
}
for (int i = 1; i <= n; ++i) for (int j = 1; j <= m; ++j) if (!mk[i][j]) ++ans;
}
}
inline void DP() {
memset(dp, 0, sizeof(dp));
dp[0][0] = 1;
for (int i = 0; i < n * m; ++i) {
for (int s = 0; s <= S; ++s) {
sadd(dp[i + 1][s], (ll)dp[i][s] * (wy[s] - i) % P);
for (int j = 1; j <= cnt; ++j) if (!((s >> (j - 1)) & 1))
sadd(dp[i + 1][s ^ (1 << (j - 1))], dp[i][s]);
}
}
}
inline void calc() {
cnt = 0;
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= m; ++j) if (b[i][j]) p[++cnt] = pii(i, j);
ycl();
DP();
if ((cnt - pcnt) & 1) sadd(ans, P - dp[n * m][S]);
else sadd(ans, dp[n * m][S]);
}
inline void dfs(int x, int y) {
if (x == n + 1) return calc();
if (y == m) dfs(x + 1, 1); else dfs(x, y + 1);
int flag = 1;
for (int i = 0; i < 9; ++i) {
int px = x + dx[i], py = y + dy[i];
if (px < 1 || px > n || py < 1 || py > m) continue;
if (b[px][py]) { flag = 0; break; }
}
if (a[x][y] || !flag) return;
b[x][y] = 1;
if (y == m) dfs(x + 1, 1); else dfs(x, y + 1);
b[x][y] = 0;
}
inline void work() {
for (int i = 1; i <= n; ++i) for (int j = 1; j <= m; ++j) if (a[i][j])
for (int k = 1; k <= n; ++k) for (int l = 1; l <= n; ++l) if (a[k][l])
if (abs(i - k) <= 1 && abs(j - l) <= 1 && (i != k || j != l)) return (void)puts("0");
memcpy(b, a, sizeof(a));
dfs(1, 1);
printf("%d\n", ans);
}
inline void init() {
read(n), read(m);
for (int i = 1; i <= n; ++i) {
scanf("%s", a[i] + 1);
for (int j = 1; j <= m; ++j) a[i][j] = a[i][j] == 'X', pcnt += a[i][j];
}
}
int main() {
#ifdef hzhkk
freopen("hkk.in", "r", stdin);
#endif
init();
work();
fclose(stdin), fclose(stdout);
return 0;
}