先证山谷集合必是八连通独立集,再用容斥把“恰好为 X”化成“含 X 的独立超集全为山谷”,每个超集在 2^{|T|} 个前缀状态上做子集 DP 求偏序线性扩张数。
OJ: roj
题目 ID: 1784
难度:提高+/省选-
标签:动态规划容斥原理状压DP子集和变换python
创建: 2026-10-08 02:26
更新: 2026-10-08 02:26
形式化题目
在一个
其中 . 与 X 组成的字符矩阵
的排列
数据规模:1 3 / X.X 答案为 2、2 2 / X. .. 答案为 6。
正解
思路
朴素做法与瓶颈。 直接爆搜 X 的位置必须是山谷,. 的位置必须不是山谷。
在 DP 过程中同时照顾“必须”和“必须不是”,很难直接做。
观察一:山谷集合必是八连通独立集。 若
- 输入的
X中一旦出现相邻两格,答案立刻为;同样,山谷集合不可能为空—— 全局最小值所在的格子必然小于它所有邻居,无邻居时( )也恒为山谷。 - 规模极小。
的国王图最大独立集大小为 , 所以任何合法山谷集合最多 8 个格子。
观察二:用容斥把“恰好”换成“至少”。 设
这一步把“. 必须不是山谷”从约束变成了容斥系数,是整道题的枢纽。
由于
观察三:
固定
对
初始
转移系数的直观解释。 设已填好山谷前缀
枚举超集 X 上、且与 X 中任何格子都不相邻”的格子才可能被加进 1 3 / X.X 得到 2、2 2 / X. .. 得到 6,与题面一致。
代码
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++ 版(同一算法):
/**
* 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;
}复杂度
- 时间:枚举合法超集
的次数为 ( 中最多约 ), 每个 的代价是 , 、 。 单组数据总代价约 次基本运算,配合预处理好的阶乘表, C++ 实测毫秒级,Python 版也在限时内(限时 1000 ms)。 - 空间:阶乘表
,每个 的 DP 数组只有 项,总占用不到 1 MB (限时 256 MB)。 - 与 C++ 版的关系:
main.py与main.cpp算法完全同阶,只是 Python 用@cache缓存邻接表、用生成器枚举超集后缀;两者都靠同一容斥公式与同一子集 DP。
总结
- 先看约束的互斥性:两个相邻格子不可能同时是山谷,这一句就把“合法集合是独立集、
规模
”两件事一起定下来,是后面一切枚举能够成立的前提。 - “恰好”难写就换“至少”:把“
.必须不是山谷”交给容斥,的约束只剩单向下界 约束,立刻变成偏序计数,这是本题最值得记住的一步。 - 偏序计数按“最后一个前驱”插入:把
的内部顺序固定后,其余格子只需记住自己 最后一个 -邻居的位置;按该位置从大到小插入,可用位置数就是闭式的 ,于是求和可以折叠成前缀集合上的子集 DP。 用子集和变换一次算完: 是“按子集累加” 的标准形式, 预处理后就只剩查表。
补充说明
本题素材来自信息学奥赛一本通·高手训练篇(五、动态规划)。该题的素材源目录中带有数据生成脚本
(data.py,用 std.cpp 产出 .out),说明随仓测试数据是自造重建的,题面也可能为网络重建版本,
与官方原题在细节上可能有偏差。上面给出的算法与 main.cpp / main.py 均为独立实现,
已用该数据集的 10 个测试点逐点核对通过;但这只说明它与随仓数据一致,
不等价于官方数据的正确性保证。
图示解析
样例 2 2 / X. .. 的完整展开
网格按行优先编号:
0 1
2 3X 上、且与 X 中任何格都不八连通”:
格子
| 山谷集合 | 排列个数 |
|---|---|
| 6 | |
| 6 | |
| 6 | |
| 6 |
四类各 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 的完整展开
网格编号 X 相距 2 格、不相邻,独立性检查通过。
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"]
枚举树的分支因子很小:候选格的每一个选择都会把它周围的邻居封掉,