一、问题分析

1.1 问题描述

给定一个 $n$ 个节点、$m$ 条边的有向图，对于每种可能的边方向翻转方案，如果翻转后的图无环，则该方案合法。求所有合法方案中翻转边数的总和，答案模 $998244353$。

1.2 核心观察

观察1：无环有向图与拓扑序

一个有向图无环（DAG）当且仅当存在拓扑序，即可以给节点编号 $1, 2, \ldots, n$，使得所有边都从小编号指向大编号。

观察2：边的翻转与拓扑序

对于原图中的一条有向边 $(u, v)$：

• 如果在某个拓扑序中 $u$ 的编号小于 $v$，则边 $(u, v)$ 不需要翻转
• 如果在某个拓扑序中 $u$ 的编号大于 $v$，则需要翻转成 $(v, u)$

观察3：对称性

将输入的有向边看作无向边 $\{u, v\}$，对于任意拓扑序：

• 恰好有一半的拓扑序中 $u$ 在 $v$ 前面（不需要翻转）
• 另一半的拓扑序中 $v$ 在 $u$ 前面（需要翻转）

关键结论：

设图的底图（将有向边看作无向边）对应的无向图为 $G$，$P(n)$ 为用 $n$ 种"颜色"（即编号）对 $G$ 进行有序染色的方案数（每个节点一种颜色，颜色互不相同），则：

$$\text{答案} = P(n) \times \frac{m}{2}$$

证明：

• $P(n)$ 等价于 $G$ 作为无向图的合法拓扑排序数
• 每个拓扑序对应一种合法方案
• 对于每条边，在 $P(n)$ 个拓扑序中，恰有 $\frac{P(n)}{2}$ 个需要翻转
• 总翻转边数 = $m \times \frac{P(n)}{2}$

1.3 色多项式

定义：对于无向图 $G$，色多项式 $P_G(k)$ 表示用 $k$ 种颜色对图进行正常染色（相邻节点颜色不同）的方案数。

本题需要计算的是有序染色（节点编号不同），它等于：

$$P_G(n) = \text{图 } G \text{ 的色多项式在 } k=n \text{ 处的值} $$

对于无向图的色多项式，可以使用容斥原理计算。

二、数学推导

2.1 色多项式的容斥计算

定理1（色多项式的容斥公式）：

对于无向图 $G=(V, E)$，色多项式为：

$$P_G(k) = \sum_{S \subseteq V} (-1)^{|S| - |I(S)|} k^{|I(S)|} $$

其中 $I(S)$ 表示 $S$ 的极大独立子集（$S$ 中没有边相连的节点构成的极大子集）。

简化形式：

$$P_G(k) = \sum_{\text{独立集 } I} (-1)^{|V| - |I|} k^{|I|} $$

关键观察：我们需要枚举所有独立集 $I$（图中两两不相邻的节点集合）。

对于每个独立集 $I$：

• 贡献系数为 $(-1)^{n - |I|}$
• 贡献项为 $k^{|I|}$

2.2 独立集判断

算法：对于节点子集 $S$，判断 $S$ 是否为独立集。

方法：检查 $S$ 中任意两个节点之间是否有边。如果没有任何边，则 $S$ 是独立集。

实现：对于集合 $S$（用二进制表示）：

bool is_independent = true;
for (int i in S) {
    for (int j in S, j > i) {
        if (g[i][j]) {  // 存在边
            is_independent = false;
        }
    }
}

2.3 色多项式的计算

步骤1：枚举所有独立集，记录容斥系数

对于每个独立集 $I$，设 $|I| = c$，则：

• 贡献到色多项式的 $k^c$ 项
• 系数为 $(-1)^{n-c}$

步骤2：使用子集和 DP 计算多项式

设 $f[S][c]$ 表示考虑节点集 $S$，$k^c$ 项的系数。

通过子集枚举，将所有独立集的贡献累加。

步骤3：计算 $P_G(n)$

通过组合多项式的各项系数，计算在 $k=n$ 处的值。

使用指数生成函数的思想，设：

$$T(k) = \sum_{c=0}^{n} f[\text{all}][c] \cdot k^c$$

则 $P_G(n) = T(n)$。

但这里需要计算的是 $n$ 个不同元素的排列方式，需要乘以 Stirling 数。

实际上，代码中使用的是另一种方法：通过 DP 计算 $t[i]$ 表示用前 $i$ 个编号的方案数。

2.4 容斥原理的优化

子集和变换：

对于所有独立集的贡献，可以通过类似 FWT 的子集和变换优化。

设 $f[S][c]$ 初始只在独立集处有值，通过子集和变换，可以得到：

$$f[S][c] = \sum_{I \subseteq S, I \text{ 是独立集}} (-1)^{|I|-c} \cdot [|I| = c] $$

变换过程：对于每个二进制位，枚举是否包含该位，进行状态转移。

for (int i = 1; i < (1 << n); i <<= 1) {
    for (int j = 0; j < (1 << n); j++) {
        if (j & i) {
            f[j][k] += f[j ^ i][k];  // 从不包含位i的子集转移
        }
    }
}

三、代码模块详解

模块1：全局定义与常量

const int N = 25, N_ = (1 << 18) + 5;
int n, m, f[N_][N], t[N];
bool g[N][N];

constexpr int mod = 998244353, inv2 = (mod + 1) >> 1;

说明：

• n：节点数（最大18）
• m：边数
• f[S][c]：状态压缩DP，$S$ 表示节点集合，$c$ 表示独立集大小/颜色数
• g[i][j]：邻接矩阵，存储无向边
• inv2：2 在模 $998244353$ 意义下的逆元，用于计算 $\frac{m}{2}$

模块2：模运算辅助函数

int A(int x, int y) {
    return (x + y) >= mod ? (x + y - mod) : (x + y);
}
int S(int x, int y) {
    return (x - y) < 0 ? (x - y + mod) : (x - y);
}
int M(int x, int y) {
    return 1ll * x * y % mod;
}

int fastpow(int x, int y) {
    int ret = 1;
    for (; y; y >>= 1, x = M(x, x)) {
        if (y & 1)
            ret = M(ret, x);
    }
    return ret;
}

功能：

• A(x, y)：模意义下加法
• S(x, y)：模意义下减法
• M(x, y)：模意义下乘法
• fastpow(x, y)：快速幂

模块3：输入与建图

cin >> n >> m;

for (int i = 1, u, v; i <= m; i++)
    cin >> u >> v, g[u][v] = g[v][u] = 1;

关键点：将有向边 $(u, v)$ 作为无向边存储，因为我们关心的是两个节点之间是否有边，而不是边的方向。

模块4：枚举独立集并初始化

for (int k = 0; k < (1 << n); k++) {
    bool flag = 1;

    for (int i = 1; i <= n && flag; i++) {
        if (!((k >> (i - 1)) & 1))
            continue;

        for (int j = i; j <= n && flag; j++) {
            if (!((k >> (j - 1)) & 1))
                continue;

            if (g[i][j])
                flag = 0;
        }
    }

    if (flag && k)
        f[k][popcnt(k)] = popcnt(k) & 1 ? 1 : mod - 1;
}

算法流程：

步骤1：枚举所有节点子集 $k$（用二进制表示）

步骤2：判断 $k$ 是否为独立集

• 枚举 $k$ 中的所有节点对 $(i, j)$
• 如果存在边 $g[i][j]$，则 $k$ 不是独立集

步骤3：对于独立集 $k$（$k \neq 0$）

• 计算 $|k| = \text{popcnt}(k)$（集合大小）
• 设置容斥系数：$$f[k][\text{popcnt}(k)] = (-1)^{n - \text{popcnt}(k)} = \begin{cases} 1 & \text{popcnt}(k) \equiv n \pmod{2} \\ -1 & \text{popcnt}(k) \not\equiv n \pmod{2} \end{cases} $$

注意：空集 $k=0$ 不参与计算。

时间复杂度：$O(2^n \cdot n^2)$

模块5：子集和变换

for (int i = 1; i < (1 << n); i <<= 1) {
    for (int j = 0; j < (1 << n); j++) {
        if (!(j & i))
            continue;

        for (int k = 0; k <= n; k++)
            f[j][k] = A(f[j][k], f[j ^ i][k]);
    }
}

算法逻辑：

这是一个子集和DP（类似高维前缀和）。

对于每个二进制位 $i$（从低到高）：

• 枚举所有集合 $j$
• 如果 $j$ 包含位 $i$（即 $j \& i \neq 0$）
• 则从 $j \oplus i$（$j$ 去掉位 $i$）转移到 $j$
• 对于所有 $k$，累加：$f[j][k] \mathrel{+}= f[j \oplus i][k]$

数学含义：

转换后，$f[S][c]$ 表示所有大小为 $c$ 的独立集 $I \subseteq S$ 的容斥系数之和。

时间复杂度：$O(2^n \cdot n^2)$

模块6：计算色多项式在 $k=n$ 处的值

int ans = 0;

for (int k = 0; k < (1 << n); k++) {
    t[0] = 1;

    for (int i = 1; i <= n; i++) {
        t[i] = 0;

        for (int j = 1; j <= i; j++)
            t[i] = A(t[i], M(f[k][j], t[i - j]));
    }

    if ((n - popcnt(k)) & 1)
        ans = S(ans, t[n]);
    else
        ans = A(ans, t[n]);
}

算法流程：

外层循环：枚举所有节点子集 $k$

内层DP：计算 $t[i]$

$t[i]$ 的含义：使用集合 $k$ 中的独立集，对 $i$ 个编号进行分配的方案数。

递推公式：

$$t[i] = \sum_{j=1}^{i} f[k][j] \cdot t[i-j]$$

数学解释：

这里使用的是第一类 Stirling 数的思想：

• $f[k][j]$ 表示从 $k$ 中选 $j$ 个节点形成独立集的带符号方案数
• $t[i-j]$ 表示剩余 $i-j$ 个编号的方案数
• 乘积表示选择 $j$ 个节点作为一组，剩余 $i-j$ 个的方案数

容斥累加：

对于每个 $k$：

• 如果 $n - |k|$ 为奇数，减去 $t[n]$
• 否则，加上 $t[n]$

这对应容斥原理的最终计算。

时间复杂度：$O(2^n \cdot n^2)$

模块7：输出答案

cout << M(ans, M(m, inv2)) << '\n';

计算：

$$\text{答案} = \text{ans} \times m \times \frac{1}{2} \pmod{998244353} $$

其中：

• ans：$P_G(n)$，色多项式的值（合法拓扑序数量）
• m：边数
• inv2：2 的模逆元

数学依据：

每条边在 $P_G(n)$ 个拓扑序中，恰有一半需要翻转，因此总翻转边数为：

$$\sum_{\text{所有拓扑序 } \sigma} \sum_{\text{边 } (u,v)} [\sigma(u) > \sigma(v)] = m \times \frac{P_G(n)}{2} $$

四、复杂度分析

4.1 时间复杂度

独立集枚举：$O(2^n \cdot n^2)$

子集和变换：$O(2^n \cdot n^2)$

色多项式计算：$O(2^n \cdot n^2)$

总时间复杂度：$O(2^n \cdot n^2)$

对于 $n = 18$，约 $2^{18} \times 18^2 \approx 8.5 \times 10^7$ 次操作，可以接受。

4.2 空间复杂度

DP数组：

• f[N_][N]：$O(2^n \cdot n) \approx 2^{18} \times 18 \approx 4.7 \times 10^6$
• g[N][N]：$O(n^2)$
• t[N]：$O(n)$

总空间复杂度：$O(2^n \cdot n)$

六、总结

6.1 核心思想

本题采用的色多项式 + 容斥原理的核心思想：

1. 问题转化：翻转边计数 → 拓扑序计数 → 色多项式求值
2. 容斥原理：枚举独立集，使用容斥计算色多项式
3. 子集和优化：通过子集DP加速容斥系数的计算
4. 对称性利用：每条边在所有拓扑序中恰有一半需要翻转