分层图

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

取反层间连边等价于把邻接矩阵转置,只关心源点到各点路径条数的奇偶性,用 2^k 个奇偶向量作状态做状压 DP 计数方案。

OJ: roj

题目 ID: 1782

难度:提高+/省选-

标签:动态规划状态压缩位运算python

创建: 2026-10-08 02:20

更新: 2026-10-08 02:20

形式化题目

有一张分层有向无环图,共 mm 层。第 11 层只有源点、第 mm 层只有汇点,中间第 22 到 m−1m-1 层每层有 kk 个点,第 ii 层第 jj 个点记作 (i,j)(i,j)。

输入用 m−1m-1 行描述相邻层之间的边:

  • 第 11 行给出 kk 个 0/10/1,表示源点到 (2,1),…,(2,k)(2,1),\dots,(2,k) 是否有边;
  • 第 ii 行(2≤i≤m−22 \le i \le m-2)给出 k2k^2 个 0/10/1,第 (j−1)k+t(j-1)k+t 个数表示 (i,j)→(i+1,t)(i,j) \to (i+1,t) 是否有边;
  • 第 m−1m-1 行给出 kk 个 0/10/1,表示 (m−1,1),…,(m−1,k)(m-1,1),\dots,(m-1,k) 到汇点是否有边。

对每个满足 1<i<m−11 < i < m-1 的 ii,可以取反第 ii 层与第 i+1i+1 层之间的所有连边: 把每条 (i,k1)→(i+1,k2)(i,k_1) \to (i+1,k_2) 改成 (i,k2)→(i+1,k1)(i,k_2) \to (i+1,k_1)。共 m−3m-3 个可选的层间, 每个可选也可不选,所以共有 2m−32^{m-3} 种取反方案。

求有多少种取反方案,使得从源点到汇点的路径条数为偶数,答案对 998244353998244353 取模。

数据范围:4≤m≤1044 \le m \le 10^4,k≤10k \le 10。

把第 ii 层到第 i+1i+1 层的边记成一个 k×kk \times k 的 0/10/1 矩阵 AiA_i(行是第 ii 层的点), 那么"取反"这件事在代数上就是把 AiA_i 换成它的转置 AiTA_i^{T}:起点下标与终点下标 互换,边的方向仍然是从第 ii 层指向第 i+1i+1 层。

正解

思路

朴素做法。 枚举 2m−32^{m-3} 种取反方案,对每种方案沿着层数做一次"到各点的路径条数" 的加法 DP,最后看汇点收到的条数是不是偶数。m=104m = 10^4 时 299972^{9997} 种方案, 指数级,直接出局。

另一条看似自然的思路是"直接 DP 计数",但路径的真实条数随层数指数增长, 不可能精确保存;而且每一层后面是否取反会整体改变后续的组合方式, 按节点分开的"条数"不是无后效的状态。

关键观察一:只关心奇偶。 题目只看路径条数是不是偶数,那么整条链上的加法 全部可以在二元域 F2\mathbb{F}_2 里做(加法 = 异或,乘法 = 与)。 到达第 ii 层时不需要知道每个点的真实条数,只需要知道"到每个点的条数 mod 2"—— 因为在 F2\mathbb{F}_2 上,后续的矩阵乘法完全由这个 0/10/1 向量决定。

关键观察二:状态只有 2k2^k 个。 第 ii 层的"奇偶性画像"就是一个长度为 kk 的 0/10/1 向量 viv_i,可以压成一个 [0,2k)[0, 2^k) 的掩码。k≤10k \le 10 时最多 10241024 种状态, 这就是破局点。

关键观察三:无后效性。 设 viv_i 是第 ii 层的奇偶向量,则该层到下一层的转移是

vi+1={vi⋅Ai(mod2),不取反,vi⋅AiT(mod2),取反. v_{i+1} = \begin{cases} v_i \cdot A_i \pmod 2, & \text{不取反},\\[2pt] v_i \cdot A_i^{T} \pmod 2, & \text{取反}. \end{cases}

无论前面各层怎么取反,只要到达第 ii 层时 viv_i 相同,往后能走出的结果就完全相同。 于是把 2k2^k 个向量当成状态,做一层一层的状压 DP 计数即可:

  • fi[v]f_i[v] = 走到第 ii 层(即第 ii 层各点奇偶向量为 vv)的取反前缀方案数,模 998244353998244353;
  • 初始 f2[v0]=1f_2[v_0] = 1,其中 v0v_0 由第 11 行的源点边直接给出(第 11 层到第 22 层的边 不允许取反);
  • 第 ii 层到第 i+1i+1 层(2≤i≤m−22 \le i \le m-2)转移时,每个状态 vv 分裂成两个后继 v⋅Aiv \cdot A_i 与 v⋅AiTv \cdot A_i^{T},各把 fi[v]f_i[v] 累加进去——这正是"这个层间取反 / 不取反" 两种决策;
  • 第 m−1m-1 层到汇点的边也不允许取反,末态 vv 贡献的有效路径数是 ⨁j(vj∧wj)\bigoplus_j (v_j \wedge w_j),其中 ww 是末行给出的汇点边掩码。 答案就是所有 popcount(v∧w)\mathrm{popcount}(v \wedge w) 为偶数的 fm−1[v]f_{m-1}[v] 之和。

把 O(2k⋅k)O(2^k \cdot k) 的转移压成 O(2k)O(2^k)。 逐个状态现算向量乘矩阵要 O(k)O(k), 但注意到 v \cdot A = \bigoplus_{j \in v} (\text{A$ 的第 } j \text{ 行})$—— 把每一行压成一个 kk 位掩码 rjr_j,那么 v⋅Av \cdot A 就是 vv 中置位那些行的异或和。 用 lowbit 递推:

X[s]=X[s⊕lowbit(s)]⊕rctz(s),Y[s]=Y[s⊕lowbit(s)]⊕cctz(s), X[s] = X[s \oplus \mathrm{lowbit}(s)] \oplus r_{\mathrm{ctz}(s)}, \qquad Y[s] = Y[s \oplus \mathrm{lowbit}(s)] \oplus c_{\mathrm{ctz}(s)},

其中 cjc_j 是 AA 第 jj 列的掩码,即 ATA^{T} 的第 jj 行。 两层各花 O(2k)O(2^k) 预处理,之后每个状态的转移只是取一次数组、两次加法。 而 main.py 里写的是与它等价的"逐位倍增"版本:第 jj 轮把已有的 2j2^j 项表复制一份、 整体再异或第 jj 个行(列)掩码,kk 轮后得到同一张表,但省掉了每项一次求 lowbit 的开销。 总复杂度 O(m⋅2k)O(m \cdot 2^k),m=104,k=10m = 10^4, k = 10 时约 10710^7 次运算。

为什么两种掩码不能搞混。 v⋅Av \cdot A 的第 tt 位是 ⨁j(vj∧A[j][t])\bigoplus_j (v_j \wedge A[j][t]), 也就是把 vv 中置位的那些行整行异或起来,所以它由 AA 的行掩码 rjr_j 生成。 而 v⋅ATv \cdot A^{T} 的第 tt 位是 ⨁j(vj∧A[t][j])\bigoplus_j (v_j \wedge A[t][j]),等价于把 vv 中置位的那些 列整列异或起来,所以它由列掩码 cjc_j 生成(cjc_j 的第 tt 位是 A[t][j]A[t][j])。 写反了会得到"转置与不转置互换"的错误答案,这也是本题最容易出错的一行。

代码

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: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 预计算与滚动数组):

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: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;
}

复杂度

  • 时间:每层转移 O(2k)O(2^k),共 m−3m-3 层,总计 O(m⋅2k)O(m \cdot 2^k)。 代入 m=104m = 10^4、k=10k = 10 约 10710^7 次位运算与加法,限时 1000 ms 下余量充足。
  • 空间:只保留相邻两层的 DP 数组与 2k2^k 的转移表 O(2k)O(2^k),k=10k=10 时不过几个长度 1024 的数组,远低于 256 MB。 两个版本都边读边算,不把整张图存下来,所以 m=104m = 10^4 时额外内存也只是单层的 k2k^2 个数。
  • 与 C++ 解法的关系:main.py 与 main.cpp 是同一算法的两个版本, Python 靠整型位掩码 + 逐位倍增建表把常数压平,单层是 1024 次迭代。 最坏点(m=104,k=10m = 10^4, k = 10)在 CPython 下需约 1.51.5 秒(实测 problem8), 存在 TLE 风险,但按 skill 规定这里不降级算法——C++ 版正是同一算法的落地。

总结

  • 模 2 的加性结构:只问奇偶就把路径计数从"精确整数"降到 F2\mathbb{F}_2, 加法变异或、乘法变与,整条链变成纯位运算。
  • 状态只需前一层的信息:奇偶向量 viv_i 决定一切后续,这正是状压 DP 成立的前提; k≤10k \le 10 把状态数锁死在 210=10242^{10} = 1024。
  • 取反 = 转置:把几何操作"边端点互换"翻译成矩阵转置,是本题从图论落到线性代数的一步, 也让两个转移分支只差一个掩码数组。
  • 位并行预处理:v⋅Av \cdot A 可以写成"把 vv 中置位的行掩码异或起来", 于是"向量乘矩阵"的 O(k)O(k) 被逐位倍增的 O(2k)O(2^k) 建表摊成均摊 O(1)O(1), 这是状压题里最常用的省常数套路。
  • 两种模数不要混:奇偶性在 F2\mathbb{F}_2(异或)里算,方案数在 998244353998244353 里算, 两者互不相干,混淆会同时算错两者。
  • 数据来源说明:本题素材源目录中带有数据生成脚本 data.py,测试数据由该脚本自造, 并非官方原始数据;题面是按公开题面重建的,出题意图可能与原题(JZOJ 5398 / NOIP2017 提高组模拟的 Adore)存在细微偏差。本解法的正确性以自造数据全过为准, 不声称等价于官方 AC。