山谷

GitHub跳转原题关系图返回列表

先证山谷集合必是八连通独立集,再用容斥把“恰好为 X”化成“含 X 的独立超集全为山谷”,每个超集在 2^{|T|} 个前缀状态上做子集 DP 求偏序线性扩张数。

OJ: roj

题目 ID: 1784

难度:提高+/省选-

标签:动态规划容斥原理状压DP子集和变换python

创建: 2026-10-08 02:26

更新: 2026-10-08 02:26

形式化题目

在一个 n×mn \times m 的网格里填入 1∼nm1 \sim nm 的一个排列 AA,每个格子恰好填一个数、每个数恰好用一次。 定义格子 vv 是山谷,当且仅当

Av<Au(∀ u∈N(v)),A_v < A_u \quad (\forall\, u \in N(v)),

其中 N(v)N(v) 是 vv 的八连通邻居集合(上、下、左、右与 4 条对角线,共最多 8 个格子)。 给定一个由 . 与 X 组成的字符矩阵 GG,记 V={ v:Gv=X }V = \{\,v : G_v = \texttt{X}\,\}。要求统计满足

{ v:v 是山谷 }=V\{\,v : v \text{ 是山谷}\,\} = V

的排列 AA 的个数,答案对 998244353998244353 取模。输入为多组数据(读到文件结束), 每组先给 n,mn, m,再给 nn 行长度为 mm 的字符串;每组输出一行答案。

数据规模:1⩽n⩽41 \leqslant n \leqslant 4,1⩽m⩽71 \leqslant m \leqslant 7(故 N=nm⩽28N = nm \leqslant 28),数据不超过 5 组。 两个样例分别是 1 3 / X.X 答案为 2、2 2 / X. .. 答案为 6。

正解

思路

朴素做法与瓶颈。 直接爆搜 (nm)!(nm)! 个排列显然不可行;按数字 1∼nm1 \sim nm 的顺序填格子、 用 2nm2^{nm} 状压记录已占用集合,状态数也有 228≈2.7×1082^{28} \approx 2.7 \times 10^8,何况还有多组数据。 更麻烦的是题面要求的是双向条件:X 的位置必须是山谷,. 的位置必须不是山谷。 在 DP 过程中同时照顾“必须”和“必须不是”,很难直接做。

观察一:山谷集合必是八连通独立集。 若 u,vu, v 八连通相邻且都是山谷,则 Au<AvA_u < A_v 与 Av<AuA_v < A_u 同时成立,矛盾。所以合法的山谷集合在八连通图上必然两两不相邻。 两个直接推论:

  1. 输入的 X 中一旦出现相邻两格,答案立刻为 00;同样,山谷集合不可能为空—— 全局最小值所在的格子必然小于它所有邻居,无邻居时(n=m=1n = m = 1)也恒为山谷。
  2. 规模极小。4×74 \times 7 的国王图最大独立集大小为 ⌈4/2⌉×⌈7/2⌉=8\lceil 4/2 \rceil \times \lceil 7/2 \rceil = 8, 所以任何合法山谷集合最多 8 个格子。

观察二:用容斥把“恰好”换成“至少”。 设 g(T)g(T) 为“TT 中每一格都是山谷、其余格子不作要求” 的排列数(TT 非独立集时 g(T)=0g(T) = 0)。于是恰好以 VV 为山谷集合的答案就是

Ans=∑T⊇VT 为八连通独立集(−1)∣T∣−∣V∣ g(T).\mathrm{Ans} = \sum_{\substack{T \supseteq V \\ T \text{ 为八连通独立集}}} (-1)^{|T| - |V|}\, g(T).

这一步把“. 必须不是山谷”从约束变成了容斥系数,是整道题的枢纽。 由于 VV 已被固定、能继续加进去的格子又必须与 VV 及其已选格都不相邻, 合法的超集 TT 数量很少(4×74 \times 7 中 XX 为单角格时也只有 4749 个), 完全可以逐个枚举、逐个求 gg。

观察三:g(T)g(T) 是偏序的线性扩张计数,可在 2∣T∣2^{|T|} 上做子集 DP。 把排列看成格子的一个全序(第 ii 个位置填 ii),“t∈Tt \in T 是山谷”就等价于 “tt 排在自身与它全部邻居之前”。于是计数对象是:tt 先于 N(t)N(t) 中每一格。

固定 TT 的内部先后顺序 σ=(t1,t2,…,tk)\sigma = (t_1, t_2, \dots, t_k),再把 kk 个山谷格之外的 N−kN - k 个格子插进这个序列。格子 u∉Tu \notin T 唯一的约束是“排在它在 TT 中最后一个邻居之后”, 设这个位置为 h(u)h(u)(无 TT-邻居则无约束)。按 h(u)h(u) 从大到小依次插入时, 插第 jj 个有约束格子时,序列中已有的全部元素都排在 th(uj)t_{h(u_j)} 之后, 可用位置数恰为 k−h(uj)+jk - h(u_j) + j,连乘起来就是那一组的方案数。用 C(Y)=#{ u∉T:N(u)∩T⊆Y }C(Y) = \#\{\,u \notin T : N(u) \cap T \subseteq Y\,\}(YY 是山谷内部顺序的前缀集合)表示, hh 相同的格子归为一组、每组有 Ch−Ch−1C_h - C_{h-1} 个,于是 σ\sigma 这一支的贡献为

∏h=1k(N−h−Ch−1)!(N−h−Ch)!.\prod_{h=1}^{k} \frac{(N - h - C_{h-1})!}{(N - h - C_h)!}.

对 σ\sigma 求和就可以用前缀集合 YY 作状态:

dp[Y∪{s}]+=dp[Y]⋅(N−∣Y∣−1−C(Y))!(N−∣Y∣−1−C(Y∪{s}))!,dp[Y \cup \{s\}] \mathrel{+}= dp[Y] \cdot \frac{(N - |Y| - 1 - C(Y))!}{(N - |Y| - 1 - C(Y \cup \{s\}))!},

初始 dp[∅]=1dp[\varnothing] = 1,最终 g(T)=dp[T]⋅N!(N−F)!g(T) = dp[T] \cdot \dfrac{N!}{(N - F)!}, 其中 F=C(∅)F = C(\varnothing) 是在 TT 中完全没有邻居的格子数(它们随处可插)。

转移系数的直观解释。 设已填好山谷前缀 YY、当前网格里“允许被填”的格子共 C(Y)+∣Y∣C(Y) + |Y| 个 (∣T∣=k|T| = k 里的 ∣Y∣|Y| 个已填山谷,外加所有 TT-邻居已全在 YY 内的非 TT 格子)。 要从 YY 走到 Y∪{s}Y \cup \{s\},新解锁 C(Y∪{s})−C(Y)C(Y \cup \{s\}) - C(Y) 个格子,其中 ss 本身必须排在 最前,于是可选的相对排法数正是 (N−∣Y∣−1−C(Y))!(N−∣Y∣−1−C(Y∪{s}))!\dfrac{(N - |Y| - 1 - C(Y))!}{(N - |Y| - 1 - C(Y \cup \{s\}))!}—— 与上面的式子完全一致,只是换了个说法。C(⋅)C(\cdot) 用子集和(zeta)变换在 O(2kk)O(2^k k) 内一次求出。

枚举超集 TT。 只有“不在 X 上、且与 X 中任何格子都不相邻”的格子才可能被加进 TT; 在它们上面做一次选/不选的 DFS,选中一格就把它在候选集内的邻居封掉,产出的每个后缀都自动 与 XX 拼成独立集,按 ∣T∣−∣X∣|T| - |X| 的奇偶带上正负号累加即可。 样例 1 3 / X.X 得到 2、2 2 / X. .. 得到 6,与题面一致。

代码

Python 版:

python
#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-08 02:26
# update_at: 2026-10-08 02:26

import sys
from functools import cache
from itertools import accumulate
from collections.abc import Iterator

MOD = 998244353
MAX_CELLS = 32                    # 格子数上限 4*7 = 28,阶乘表开到 32!
X_BYTE = ord('X')                 # 网格按 bytes 读入,下标取出来的就是它的字节值

# 阶乘与阶乘逆元:g(T) 的转移里要算 a!/b!,一次预处理到 32!
FACT = list(accumulate(range(1, MAX_CELLS + 1), lambda acc, i: acc * i % MOD, initial=1))
INVFACT = [pow(f, MOD - 2, MOD) for f in FACT]

# 类型别名(Python 3.12+ 的 type 语句),相当于 C++ 的 using / typedef
type Mask = int                    # 格子集合掩码:第 v 位为 1 表示格子 v 属于该集合
type Adj = tuple[int, ...]         # adj[v] = 与格子 v 八连通的格子集合(掩码)
type Grid = list[bytes]            # 一组数据的 n 行网格,每行是等长 bytes
type Frame = tuple[int, int, Mask]  # 迭代式枚举的栈帧:候选下标 / 已选掩码 / 被禁掩码


@cache
def adj_of(n: int, m: int) -> Adj:
    """八连通邻接掩码:adj[v] 的第 u 位为 1 表示格子 v 与 u 八连通(含斜向 4 方向)。"""
    return tuple(
        sum(1 << ((i + di) * m + j + dj)
            for di in (-1, 0, 1) for dj in (-1, 0, 1)
            if (di or dj) and 0 <= i + di < n and 0 <= j + dj < m)
        for i in range(n) for j in range(m)
    )


def extras_of(cands: list[int], adj: Adj, cmask: Mask) -> Iterator[Mask]:
    """产出候选格里所有两两不八连通的子集:逐个候选格做“选 / 不选”的决定。

    选了一个格子就把它在候选集内的邻居禁掉,所以产出的每个掩码都能与 X 拼成独立集。
    """
    stack: list[Frame] = [(0, 0, 0)]
    while stack:
        pos, chosen, banned = stack.pop()
        if pos == len(cands):                    # 每个候选格都做完决定,得到一个合法后缀
            yield chosen
            continue
        stack.append((pos + 1, chosen, banned))  # 不选这个候选格
        c = cands[pos]
        if not banned >> c & 1:                  # 没被已选格封掉才允许选
            stack.append((pos + 1, chosen | 1 << c, banned | (adj[c] & cmask)))


def ways_all_valleys(T: Mask, N: int, adj: Adj) -> int:
    """g(T):只要求集合 T 中每一格都是山谷(T 必须是八连通独立集)的填数方案数。

    把 T 的内部先后顺序固定成 (t_1..t_k),再把 T 之外的格子插进去:格子 u 必须排在它
    在 T 里最后一个邻居之后。按“最后一个邻居的位置”从大到小插入时,插第 j 个的可选
    位置数是 k-h(u)+j,于是对全部顺序求和就变成前缀集合上的子集 DP:dp[Y] = 山谷先后
    顺序的前缀恰为 Y(|Y| = h)时,已插入格子产生的系数和;在 T 中没有任何邻居的
    freeCnt 个格子另行连乘 N!/(N-freeCnt)!。
    """
    members = [v for v in range(N) if T >> v & 1]  # 压缩 T 中格子的下标,掩码宽度降到 k
    k = len(members)
    size = 1 << k
    rank = [0] * N                               # rank[v] 是格子 v 在 T 中的压缩下标
    for i, v in enumerate(members):
        rank[v] = i
    celCnt = [0] * size                          # celCnt[Y] = T 中邻居全落在 Y 内的非 T 格数
    for u in range(N):
        if T >> u & 1:
            continue
        sub, nb = 0, adj[u] & T
        while nb:
            low = nb & -nb
            nb ^= low
            sub |= 1 << rank[low.bit_length() - 1]
        celCnt[sub] += 1
    for b in range(k):                           # 子集和(zeta)变换:celCnt[Y] 变成前缀计数
        step, block = 1 << b, 2 << b
        for base in range(0, size, block):
            for Y in range(base + step, base + block):
                celCnt[Y] += celCnt[Y - step]
    freeCnt = celCnt[0]
    dp = [0] * size
    dp[0] = 1
    for Y in range(size):
        cur = dp[Y]
        if not cur:
            continue
        head = (size - 1) ^ Y                    # 还没排进山谷内部顺序的格子
        h = Y.bit_count()
        a = N - h - 1 - celCnt[Y]                # 相邻两个前缀之间补入的格子数是 a!/b!
        base = N - h - 1
        fa = FACT[a] * cur % MOD
        while head:
            low = head & -head
            head ^= low
            nxtY = Y | low
            dp[nxtY] = (dp[nxtY] + fa * INVFACT[base - celCnt[nxtY]]) % MOD
    return dp[size - 1] * FACT[N] % MOD * INVFACT[N - freeCnt] % MOD


def answer_of(n: int, m: int, rows: Grid) -> int:
    """一组数据的答案:X 非独立直接 0,否则对所有含 X 的独立超集做容斥求和。"""
    N = n * m
    adj = adj_of(n, m)
    xmask = sum(1 << (i * m + j)
                for i in range(n) for j in range(m) if rows[i][j] == X_BYTE)
    # 山谷集合不可能为空:全局最小值那一格必是山谷(无邻居时也恒为山谷,N=1 答案为 1);
    # X 内部八连通相邻时两个“自己最小”的约束互相矛盾,答案为 0。
    x_adjacent = any(xmask >> v & 1 and adj[v] & xmask for v in range(N))
    if xmask == 0 or x_adjacent:
        return 0
    cands = [v for v in range(N) if not xmask >> v & 1 and not adj[v] & xmask]
    cmask = sum(1 << v for v in cands)
    ans = 0
    for extra in extras_of(cands, adj, cmask):
        ways = ways_all_valleys(xmask | extra, N, adj)
        sign = -1 if extra.bit_count() & 1 else 1   # 容斥系数 (-1)^(|T|-|X|)
        ans += sign * ways
    return ans % MOD


def groups_of(tokens: Iterator[bytes]) -> Iterator[tuple[int, int, Grid]]:
    """把 token 流按“n m + 后续 n 行网格”分组(组数不固定,读到 EOF 为止)。"""
    for first in tokens:
        n, m = int(first), int(next(tokens))
        yield n, m, [next(tokens) for _ in range(n)]


def solve() -> None:
    tokens = iter(sys.stdin.buffer.read().split())
    out = [str(answer_of(n, m, rows)) for n, m, rows in groups_of(tokens)]
    print('\n'.join(out))


if __name__ == "__main__":
    solve()

C++ 版(同一算法):

cpp
/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-08 02:26
 * update_at: 2026-10-08 02:26
 */

// 一本通 1784《山谷》
// 多组数据(读到 EOF):每组给 n,m 与 '.'/'X' 网格,求“山谷集合恰好等于 X”的
// 1..nm 排列数 mod 998244353。1<=n<=4,1<=m<=7,组数<=5。
//
// 核心不变量:容斥 ans = Σ_{T ⊇ X,T 为八连通独立集} (-1)^{|T|-|X|} * g(T),
// 其中 g(T) 只要求“T 中每一格都是山谷”,用 |T| 个格子内部排列顺序的子集 DP 求出。
// 复杂度:O(#独立超集 * 2^{|T|} * |T|),N<=28、|T|<=8、组数<=5,毫秒级。

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const ll MOD = 998244353;
const int MAXN = 32;      // 格子数上限 4*7 = 28
const int MAXK = 9;       // 八连通独立集规模上限 8(4x7 国王图最大独立集)
const int MAXS = 1 << MAXK;

ll fact[MAXN + 1];        // fact[i] = i! mod MOD
ll invfact[MAXN + 1];     // invfact[i] = (i!)^{-1} mod MOD

int n, m;                 // 当前数据组的网格尺寸
int N;                    // 格子数 n*m
int adjMask[MAXN];        // adjMask[v] = 与格子 v 八连通的格子集合(编号 v = i*m+j)
int Xmask;                // 输入中字符 'X' 的格子集合

int candList[MAXN];       // 可加入山谷集合的候选格:不在 X 上、也不与 X 相邻
int candCnt;
int candBits;             // 候选格的集合掩码

ll dp[MAXS];              // dp[Y]:山谷内部顺序的前缀恰为 Y 时,已填格子顺序的方案系数和
int celCnt[MAXS];         // celCnt[Y] = #{u ∉ T : N(u) ∩ T ⊆ Y},T 为当前枚举的独立超集
int posInT[MAXN];         // posInT[v] = 格子 v 在 T 里的压缩下标,v ∉ T 时为 -1

ll answer;                // 当前数据组的容斥累加结果

// 快速幂,用来求阶乘的逆元
ll pw(ll b, ll e) {
    ll r = 1;
    b %= MOD;
    while (e) {
        if (e & 1) r = r * b % MOD;
        b = b * b % MOD;
        e >>= 1;
    }
    return r;
}

// 预处理阶乘与阶乘逆元:g(T) 的转移里要算 a!/b!
void init_fact() {
    fact[0] = 1;
    for (int i = 1; i <= MAXN; i++) fact[i] = fact[i - 1] * i % MOD;
    invfact[MAXN] = pw(fact[MAXN], MOD - 2);
    for (int i = MAXN; i >= 1; i--) invfact[i - 1] = invfact[i] * i % MOD;
}

// g(T):只要求集合 T 中每一格都是山谷(T 必须是八连通独立集)的填数方案数。
//
// 把 T 的内部顺序固定为 (t_1..t_k),再把 T 之外的格子插进这个序列:格子 u 必须排在
// 它在 T 里的最后一个邻居之后。按“最后一个邻居的位置 h(u)”从大到小插入时,插第 j 个
// 的可选位置数是 k-h(u)+j,于是对全部顺序求和可写成子集 DP:dp[Y] = 已排好前缀 Y
// 的系数和;剩下的无约束格子(在 T 中没有任何邻居)另有 N!/(N-F)! 种插法。
ll gval(int T) {
    int k = 0;
    for (int v = 0; v < N; v++) posInT[v] = -1;
    for (int v = 0; v < N; v++) if (T >> v & 1) posInT[v] = k++;
    int sz = 1 << k;
    for (int Y = 0; Y < sz; Y++) celCnt[Y] = 0;
    for (int u = 0; u < N; u++) {
        if (T >> u & 1) continue;
        int nb = adjMask[u] & T;
        int sub = 0;                                  // u 在 T 中的邻居(压缩下标)
        while (nb) {
            int v = __builtin_ctz(nb);
            nb &= nb - 1;
            sub |= 1 << posInT[v];
        }
        celCnt[sub]++;
    }
    // 子集和(zeta)变换:celCnt[Y] 变成“T 中邻居全都落在 Y 内”的格子数
    for (int b = 0; b < k; b++)
        for (int Y = 0; Y < sz; Y++)
            if (Y >> b & 1) celCnt[Y] += celCnt[Y ^ (1 << b)];
    int freeCnt = celCnt[0];                          // 在 T 中没有任何邻居的格子数
    for (int Y = 0; Y < sz; Y++) dp[Y] = 0;
    dp[0] = 1;
    for (int Y = 0; Y < sz; Y++) {
        if (!dp[Y]) continue;
        int h = __builtin_popcount(Y);
        for (int s = 0; s < k; s++) {
            if (Y >> s & 1) continue;
            int nxtY = Y | 1 << s;
            int a = N - h - 1 - celCnt[Y];             // 加入 t_{h+1} 之前:a!/b! 的 a
            int b = N - h - 1 - celCnt[nxtY];          // 加入之后:a!/b! 的 b
            dp[nxtY] = (dp[nxtY] + dp[Y] * fact[a] % MOD * invfact[b]) % MOD;
        }
    }
    return dp[sz - 1] * fact[N] % MOD * invfact[N - freeCnt] % MOD;
}

// 枚举所有包含 X 的八连通独立集 T:逐个候选格决定选或不选,选了就封掉它的邻居。
void dfs_superset(int pos, int T, int forbidden) {
    if (pos == candCnt) {
        ll g = gval(T);
        int extra = __builtin_popcount(T & candBits);   // |T| - |X|
        if (extra & 1) answer = (answer - g + MOD) % MOD;
        else answer = (answer + g) % MOD;
        return;
    }
    dfs_superset(pos + 1, T, forbidden);              // 不选这个候选格
    int c = candList[pos];
    if (!(forbidden >> c & 1))                        // 没被已选格封掉才允许选
        dfs_superset(pos + 1, T | 1 << c, forbidden | (adjMask[c] & candBits));
}

int main() {
    init_fact();
    char row[16];
    while (scanf("%d %d", &n, &m) == 2) {             // 多组数据,读到 EOF
        N = n * m;
        Xmask = 0;
        for (int i = 0; i < n; i++) {
            if (scanf("%s", row) != 1) return 0;
            for (int j = 0; j < m; j++)
                if (row[j] == 'X') Xmask |= 1 << (i * m + j);
        }
        // 八连通邻接关系:格子编号 v = i*m+j,邻居掩码含斜向的 4 个方向
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++) {
                int v = i * m + j, mask = 0;
                for (int di = -1; di <= 1; di++)
                    for (int dj = -1; dj <= 1; dj++) {
                        if (!di && !dj) continue;
                        int x = i + di, y = j + dj;
                        if (x < 0 || x >= n || y < 0 || y >= m) continue;
                        mask |= 1 << (x * m + y);
                    }
                adjMask[v] = mask;
            }
        // 山谷集合不可能为空:全局最小值所在格必是山谷(无邻居时也恒为山谷,N=1 得 1)
        bool valid = (Xmask != 0);
        for (int v = 0; v < N && valid; v++)
            if ((Xmask >> v & 1) && (adjMask[v] & Xmask))
                valid = false;                        // X 内部八连通相邻,两个约束矛盾
        if (!valid) { printf("0\n"); continue; }
        candCnt = 0;
        candBits = 0;
        for (int v = 0; v < N; v++)
            if (!(Xmask >> v & 1) && !(adjMask[v] & Xmask)) {
                candList[candCnt++] = v;
                candBits |= 1 << v;
            }
        answer = 0;
        dfs_superset(0, Xmask, 0);
        printf("%lld\n", answer % MOD);
    }
    return 0;
}

复杂度

  • 时间:枚举合法超集 TT 的次数为 SS(4×74 \times 7 中最多约 5×1035 \times 10^3), 每个 TT 的代价是 O(2∣T∣⋅∣T∣+N⋅2∣T∣)O(2^{|T|} \cdot |T| + N \cdot 2^{|T|}),∣T∣⩽8|T| \leqslant 8、N⩽28N \leqslant 28。 单组数据总代价约 105∼10610^5 \sim 10^6 次基本运算,配合预处理好的阶乘表, C++ 实测毫秒级,Python 版也在限时内(限时 1000 ms)。
  • 空间:阶乘表 O(N)O(N),每个 TT 的 DP 数组只有 2∣T∣⩽2562^{|T|} \leqslant 256 项,总占用不到 1 MB (限时 256 MB)。
  • 与 C++ 版的关系:main.py 与 main.cpp 算法完全同阶,只是 Python 用 @cache 缓存邻接表、用生成器枚举超集后缀;两者都靠同一容斥公式与同一子集 DP。

总结

  • 先看约束的互斥性:两个相邻格子不可能同时是山谷,这一句就把“合法集合是独立集、 规模 ⩽8\leqslant 8”两件事一起定下来,是后面一切枚举能够成立的前提。
  • “恰好”难写就换“至少”:把“. 必须不是山谷”交给容斥,g(T)g(T) 的约束只剩单向下界 约束,立刻变成偏序计数,这是本题最值得记住的一步。
  • 偏序计数按“最后一个前驱”插入:把 TT 的内部顺序固定后,其余格子只需记住自己 最后一个 TT-邻居的位置;按该位置从大到小插入,可用位置数就是闭式的 k−h+jk - h + j,于是求和可以折叠成前缀集合上的子集 DP。
  • C(Y)C(Y) 用子集和变换一次算完:C(Y)=#{u:N(u)∩T⊆Y}C(Y) = \#\{u : N(u) \cap T \subseteq Y\} 是“按子集累加” 的标准形式,O(2kk)O(2^k k) 预处理后就只剩查表。

补充说明

本题素材来自信息学奥赛一本通·高手训练篇(五、动态规划)。该题的素材源目录中带有数据生成脚本 (data.py,用 std.cpp 产出 .out),说明随仓测试数据是自造重建的,题面也可能为网络重建版本, 与官方原题在细节上可能有偏差。上面给出的算法与 main.cpp / main.py 均为独立实现, 已用该数据集的 10 个测试点逐点核对通过;但这只说明它与随仓数据一致, 不等价于官方数据的正确性保证。

图示解析

样例 2 2 / X. .. 的完整展开

网格按行优先编号:

text
0 1
2 3

X={0}X = \{0\},所以 V={0}V = \{0\}。候选格必须满足“不在 X 上、且与 X 中任何格都不八连通”: 格子 11、22 与 00 边相邻,格子 33 与 00 对角相邻,三个格子全被排除,候选集为空。 于是枚举出的合法超集只有 T={0}T = \{0\} 一个,容斥只剩一项 g({0})g(\{0\})。

g({0})g(\{0\}) 的数法:要求格子 00 严格小于它的邻居 1,2,31, 2, 3,即 00 必须是四格中的最小值。 最小值在排列里是唯一的,00 的位置由排列本身决定,剩下的 1,2,31, 2, 3 在三格上自由排列, 共 3!=63! = 6 种。把 44 个格子 1∼41 \sim 4 的排列按“山谷集合”分类可以验证这一点:

山谷集合 排列个数
{0}\{0\} 6
{1}\{1\} 6
{2}\{2\} 6
{3}\{3\} 6

四类各 6 种、合计 24=4!24 = 4!,没有“两个山谷”的类(相邻格不可能同时为山谷), 所以 Ans=6\mathrm{Ans} = 6,与题面样例一致。

flowchart LR
  V["V = {0}"] --> C{"候选格:与 X 不相邻"}
  C --> C1["格子 1:与 0 边相邻,排除"]
  C --> C2["格子 2:与 0 边相邻,排除"]
  C --> C3["格子 3:与 0 对角相邻,排除"]
  C1 --> T["候选集为空 → 唯一合法超集 T = {0}"]
  C2 --> T
  C3 --> T
  T --> G["g({0}) = 3! = 6"]

样例 1 3 / X.X 的完整展开

网格编号 0,1,20, 1, 2,X={0,2}X = \{0, 2\}。两个 X 相距 2 格、不相邻,独立性检查通过。 00 的邻居只有 11,22 的邻居也只有 11,所以候选格列表为空,合法超集也只有 T={0,2}T = \{0, 2\}。

g({0,2})g(\{0,2\}) 要求“00 是山谷”且“22 是山谷”:两个条件都只要求自己小于格子 11, 即格子 11 填的数最大,00 与 22 分掉剩下的两个数,共 22 种, 与题面输出 2 一致。这里可以看清 g(T)g(T) 与“恰好”的区别:gg 只管 TT 内每一格是山谷, 不禁止别的格子也当山谷;本题候选格为空,两类恰好重合,所以 gg 就是答案。

flowchart LR
  X["X = {0,2}"] --> CHK["0 与 2 不相邻 → 合法性通过"]
  CHK --> CD["候选格为空(唯一的非 X 格 1 与 0、2 都相邻)"]
  CD --> T["唯一合法超集 T = {0,2}"]
  T --> G["g({0,2}) = 2:格子 1 最大,0/2 互换"]

整体流程

flowchart TD
  R["读入一组 n, m, 网格"] --> IND{"X 非空 且 X 内部两两不八连通?"}
  IND -->|否| Z["输出 0"]
  IND -->|是| ENUM["在候选格上枚举含 X 的独立超集 T"]
  ENUM --> DP["对每个 T 求 g(T):压缩 |T| 位后做子集 DP"]
  DP --> SUM["按 (-1)^(|T|-|X|) 容斥累加"]
  SUM --> OUT["输出 mod 998244353"]

枚举树的分支因子很小:候选格的每一个选择都会把它周围的邻居封掉, 4×74 \times 7 中 XX 取单角格时合法超集最多约 47494749 个,再加上 ∣T∣⩽8|T| \leqslant 8 的位数上限,整棵树的总代价被压在 10610^6 以内。