思路与算法

要求谷集合X必须非空且在八邻接下独立，否则0。容斥枚举独立集合S⊇X。固定S全部为谷的排列数用连续独立随机标签计算：按选中点标签从大到小排序积分，普通相邻格须大于其相邻谷中的最大标签。子集DP累加不同排序，加入最后一个选中点时除以|mask|+|邻居并集(mask)|，最终乘N!，再按|S-X|容斥。

正确性说明

任意排列等可能对应连续标签的相对次序。独立性排除相邻谷的矛盾。固定选中标签次序后，每个普通格只受最大邻谷限制；令y=1-x，逐层单项式积分给出上述前缀分母。子集DP枚举全部次序且互斥，得到包含S的精确计数。容斥去除X外的谷，剩下恰好X。

复杂度

N≤28，独立集合最多选8格。时间为枚举各独立S的Σ O(|S|2^|S|)加邻接预处理O(N²)，空间O(2^8+N²)，各组初始化计入；最多5组。

易错点

谷按八方向，不能只用四方向。全局最小值必为谷，因此空X答案0。分母≤N<998244353，模逆存在。独立答案使用整数偏序计数，不以同一模积分程序自证。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
const int MOD = 998244353;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    while (cin >> n >> m) {
        int N = n * m;
        vector<unsigned> adj(N);
        unsigned fixed = 0;
        for (int i = 0; i < n; i++) {
            string s;
            cin >> s;
            for (int j = 0; j < m; j++)
                if (s[j] == 'X')
                    fixed |= 1U << (i * m + j);
        }
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++)
                for (int x = max(0, i - 1); x <= min(n - 1, i + 1); x++)
                    for (int y = max(0, j - 1); y <= min(m - 1, j + 1); y++)
                        if (x != i || y != j)
                            adj[i * m + j] |= 1U << (x * m + y);
        bool valid = fixed != 0;
        unsigned block = fixed;
        for (int u = 0; u < N; u++)
            if (fixed >> u & 1) {
                if (adj[u] & fixed)
                    valid = false;
                block |= adj[u];
            }
        if (!valid) {
            cout << 0 << '\n';
            continue;
        }
        vector<long long> inv(N + 1), fac(N + 1, 1);
        auto power = [&](long long a, int e) {
            long long r = 1;
            while (e) {
                if (e & 1)
                    r = r * a % MOD;
                a = a * a % MOD;
                e >>= 1;
            }
            return r;
        };
        for (int i = 1; i <= N; i++) {
            inv[i] = power(i, MOD - 2);
            fac[i] = fac[i - 1] * i % MOD;
        }
        auto count = [&](unsigned S) {
            vector<int> pos;
            for (int u = 0; u < N; u++)
                if (S >> u & 1)
                    pos.push_back(u);
            int k = pos.size(), M = 1 << k;
            vector<unsigned> neigh(M);
            vector<long long> dp(M);
            dp[0] = 1;
            for (int mask = 1; mask < M; mask++) {
                int bit = __builtin_ctz((unsigned)mask), prev = mask & (mask - 1);
                neigh[mask] = neigh[prev] | adj[pos[bit]];
                long long ways = 0;
                for (int t = mask; t; t &= t - 1) {
                    int z = t & -t;
                    ways += dp[mask ^ z];
                    if (ways >= MOD)
                        ways -= MOD;
                }
                int denominator =
                    __builtin_popcount((unsigned)mask) + __builtin_popcount(neigh[mask]);
                dp[mask] = ways * inv[denominator] % MOD;
            }
            return (int)(dp[M - 1] * fac[N] % MOD);
        };
        long long ans = 0;
        function<void(int, unsigned, unsigned, int)> dfs = [&](int at, unsigned S, unsigned ban,
                                                               int sign) {
            while (at < N && (ban >> at & 1))
                at++;
            if (at == N) {
                ans = (ans + sign * 1LL * count(S) + MOD) % MOD;
                return;
            }
            dfs(at + 1, S, ban, sign);
            dfs(at + 1, S | (1U << at), ban | adj[at] | (1U << at), -sign);
        };
        dfs(0, fixed, block, 1);
        cout << ans << '\n';
    }
}