取反层间连边等价于把邻接矩阵转置,只关心源点到各点路径条数的奇偶性,用 2^k 个奇偶向量作状态做状压 DP 计数方案。
OJ: roj
题目 ID: 1782
难度:提高+/省选-
标签:动态规划状态压缩位运算python
创建: 2026-10-08 02:20
更新: 2026-10-08 02:20
形式化题目
有一张分层有向无环图,共
输入用
- 第
行给出 个 ,表示源点到 是否有边; - 第
行( )给出 个 ,第 个数表示 是否有边; - 第
行给出 个 ,表示 到汇点是否有边。
对每个满足
求有多少种取反方案,使得从源点到汇点的路径条数为偶数,答案对
数据范围:
把第
正解
思路
朴素做法。 枚举
另一条看似自然的思路是"直接 DP 计数",但路径的真实条数随层数指数增长, 不可能精确保存;而且每一层后面是否取反会整体改变后续的组合方式, 按节点分开的"条数"不是无后效的状态。
关键观察一:只关心奇偶。 题目只看路径条数是不是偶数,那么整条链上的加法
全部可以在二元域
关键观察二:状态只有
关键观察三:无后效性。 设
无论前面各层怎么取反,只要到达第
= 走到第 层(即第 层各点奇偶向量为 )的取反前缀方案数,模 ; - 初始
,其中 由第 行的源点边直接给出(第 层到第 层的边 不允许取反); - 第
层到第 层( )转移时,每个状态 分裂成两个后继 与 ,各把 累加进去——这正是"这个层间取反 / 不取反" 两种决策; - 第
层到汇点的边也不允许取反,末态 贡献的有效路径数是 ,其中 是末行给出的汇点边掩码。 答案就是所有 为偶数的 之和。
把
其中 main.py 里写的是与它等价的"逐位倍增"版本:第
为什么两种掩码不能搞混。
代码
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:20
# update_at: 2026-10-08 02:20
import sys
from itertools import islice
MOD = 998244353 # 方案数模数;与奇偶性所在的 GF(2) 运算互不干涉
def step_layer(dp: list[int], rows: list[int], cols: list[int]) -> list[int]:
"""把本层的奇偶向量 DP 推到下一层:每个状态沿"不取反(乘 A)/取反(乘 A^T)"分两路。
rows[j] 是第 i 层到第 i+1 层邻接矩阵 A 的第 j 行掩码,cols[j] 是它的第 j 列掩码
(即 A^T 的第 j 行掩码)。遍历位向量 v 时 v*A = XOR_{j∈v} rows[j],
v*A^T = XOR_{j∈v} cols[j],两张表用逐位倍增在 O(2^k) 内建好,此后每个状态 O(1)。
"""
size = len(dp)
go_no, go_yes = [0], [0]
for j in range(len(rows)):
go_no += [x ^ rows[j] for x in go_no] # 低 j 位的旧表复制一份再异或第 j 行
go_yes += [x ^ cols[j] for x in go_yes]
nxt = [0] * size
for v in range(size):
ways = dp[v]
if ways: # 不取反与取反是两种决策,两条后继都要累加,出循环后统一取模
nxt[go_no[v]] += ways
nxt[go_yes[v]] += ways
return [x % MOD for x in nxt]
def solve() -> None:
data = iter(map(int, sys.stdin.buffer.read().split()))
m, k = next(data), next(data)
size = 1 << k # 奇偶向量状态数:k<=10 时最多 1024
# 首行:源点到第 2 层各点的边,直接给出第 2 层的奇偶向量
start = sum(bit << t for t, bit in enumerate(islice(data, k)))
order = k * k # 中段每行的边数:第 (j-1)*k+t 个数表示 (i,j)->(i+1,t)
dp = [0] * size
dp[start] = 1 # 尚未做任何取反决策,方案数 1
# 中段 (m-3) 个层间可以取反,逐层转移
for _ in range(m - 3):
bits = list(islice(data, order))
rows = [sum(bits[j * k + t] << t for t in range(k)) for j in range(k)]
cols = [sum(bits[j * k + t] << j for j in range(k)) for t in range(k)]
dp = step_layer(dp, rows, cols)
# 末行:第 m-1 层各点到汇点的边,这一段不允许取反
end = sum(bit << t for t, bit in enumerate(islice(data, k)))
# 路径总数 mod 2 = 末层奇偶向量与汇点边掩码交集的 popcount mod 2,为 0(偶数条)才算答案
print(sum(ways for s, ways in enumerate(dp) if (s & end).bit_count() % 2 == 0) % MOD)
if __name__ == "__main__":
solve()C++ 版(同一算法,加了 lowbit 预计算与滚动数组):
/**
* 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:20
* update_at: 2026-10-08 02:20
*/
// main.cpp:分层图,状压 DP。只关心"源点到本层每个点的路径条数"的奇偶性,
// 于是 k<=10 个节点的奇偶向量可压成 2^k 个状态;层间取反等价于把 k×k 邻接矩阵转置,
// 每个状态向下一层分裂出"不取反 / 取反"两条转移。与 main.py 同一算法。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MOD = 998244353; // 方案数的模数,与偶奇性所在的 GF(2) 无关
const int MAXK = 10; // 题面 k<=10
const int MAXS = 1 << MAXK; // 奇偶向量状态数上界 1024
int m, k;
int dp[MAXS], ndp[MAXS]; // 滚动数组:走到本层、奇偶向量恰为 mask 的取反前缀方案数
int rowBit[MAXK], colBit[MAXK]; // 本层邻接矩阵的行/列掩码(列掩码即转置矩阵的行掩码)
int goNo[MAXS], goYes[MAXS]; // goNo[v] = v*M,goYes[v] = v*M^T,均在 GF(2) 上
// 快读:输入规模最大约 m*k^2 = 10^6 个 0/1,scanf 亦可,这里统一成手写读入
int readInt() {
int c = getchar_unlocked();
while (c != EOF && (c < '0' || c > '9')) c = getchar_unlocked();
int x = 0;
while (c >= '0' && c <= '9') {
x = x * 10 + (c - '0');
c = getchar_unlocked();
}
return x;
}
int main() {
m = readInt();
k = readInt();
int N = 1 << k; // 奇偶向量的状态数
// 第一行:源点到第 2 层各点的边,直接给出第 2 层的初始奇偶向量
int startMask = 0;
for (int t = 0; t < k; t++)
if (readInt()) startMask |= 1 << t;
fill(dp, dp + N, 0);
dp[startMask] = 1; // 尚未做任何取反决策,方案数 1
// 第 2..m-2 行:中间相邻两层的 k×k 邻接矩阵,这里可以取反(转置)
for (int i = 2; i <= m - 2; i++) {
fill(rowBit, rowBit + k, 0);
fill(colBit, colBit + k, 0);
for (int j = 0; j < k; j++)
for (int t = 0; t < k; t++)
if (readInt()) {
rowBit[j] |= 1 << t; // (i,j) -> (i+1,t)
colBit[t] |= 1 << j; // 取反后 (i,t) -> (i+1,j):矩阵被转置
}
// go[s] = XOR_{j 在 s 中} (M 的第 j 行 / 第 j 列),用 lowbit 按 2^k 递推出来
goNo[0] = goYes[0] = 0;
for (int s = 1; s < N; s++) {
int low = s & -s;
int j = __builtin_ctz(s);
goNo[s] = goNo[s ^ low] ^ rowBit[j];
goYes[s] = goYes[s ^ low] ^ colBit[j];
}
fill(ndp, ndp + N, 0);
for (int v = 0; v < N; v++) {
if (!dp[v]) continue; // 到不了的状态不贡献方案
int a = goNo[v], b = goYes[v]; // 不取反 / 取反,一次位运算得出,O(1)
ndp[a] = (ndp[a] + dp[v]) % MOD;
ndp[b] = (ndp[b] + dp[v]) % MOD;
}
copy(ndp, ndp + N, dp);
}
// 最后一行:第 m-1 层各点到汇点的边,这一段的取反是禁止的
int endMask = 0;
for (int t = 0; t < k; t++)
if (readInt()) endMask |= 1 << t;
// 路径总数 mod 2 = popcount(末层奇偶向量 & 汇点边掩码) mod 2,
// 为 0(偶数条)的那些末态,其全部取反前缀方案都要计入答案
ll ans = 0;
for (int s = 0; s < N; s++)
if (__builtin_popcount(s & endMask) % 2 == 0) ans += dp[s];
printf("%lld\n", ans % MOD);
return 0;
}复杂度
- 时间:每层转移
,共 层,总计 。 代入 、 约 次位运算与加法,限时 1000 ms 下余量充足。 - 空间:只保留相邻两层的 DP 数组与
的转移表 , 时不过几个长度 1024 的数组,远低于 256 MB。 两个版本都边读边算,不把整张图存下来,所以 时额外内存也只是单层的 个数。 - 与 C++ 解法的关系:
main.py与main.cpp是同一算法的两个版本, Python 靠整型位掩码 + 逐位倍增建表把常数压平,单层是 1024 次迭代。 最坏点()在 CPython 下需约 秒(实测 problem8), 存在 TLE 风险,但按 skill 规定这里不降级算法——C++ 版正是同一算法的落地。
总结
- 模 2 的加性结构:只问奇偶就把路径计数从"精确整数"降到
, 加法变异或、乘法变与,整条链变成纯位运算。 - 状态只需前一层的信息:奇偶向量
决定一切后续,这正是状压 DP 成立的前提; 把状态数锁死在 。 - 取反 = 转置:把几何操作"边端点互换"翻译成矩阵转置,是本题从图论落到线性代数的一步, 也让两个转移分支只差一个掩码数组。
- 位并行预处理:
可以写成"把 中置位的行掩码异或起来", 于是"向量乘矩阵"的 被逐位倍增的 建表摊成均摊 , 这是状压题里最常用的省常数套路。 - 两种模数不要混:奇偶性在
(异或)里算,方案数在 里算, 两者互不相干,混淆会同时算错两者。 - 数据来源说明:本题素材源目录中带有数据生成脚本
data.py,测试数据由该脚本自造, 并非官方原始数据;题面是按公开题面重建的,出题意图可能与原题(JZOJ 5398 / NOIP2017 提高组模拟的 Adore)存在细微偏差。本解法的正确性以自造数据全过为准, 不声称等价于官方 AC。