题解

思路

把红边看作一张简单图 $G$，蓝边就是补图 $\overline G$。任意一张至少有两个顶点的图，如果不连通，则补图一定连通。因此题目的“恰好一个连通”等价于：对每个诱导子图，原图与补图不能同时连通。

这正是余图可分解图（cograph）的递归性质：单点是合法图；多个点的合法图要么是不连通合法图的并，要么是这种图的补图。两种情况由补图操作一一对应。

令 $d_x$ 表示 $x$ 个有标号顶点上“不连通合法图”的数量。规定 $d_1=d_2=1$，便于统一递推。对于真正不少于两个顶点的合法图，不连通与连通两类数量相等，所以合法图总数为 $2d_x$。

考虑不连通图中包含固定顶点 $1$ 的连通块，设它有 $i$ 个顶点：

• 选择其余 $i-1$ 个顶点有 $\binom{x-1}{i-1}$ 种；
• 该连通块是连通合法图，共 $d_i$ 种；
• 若剩下 $x-i\ge2$ 个顶点，其上任意合法图有 $2d_{x-i}$ 种；若只剩一个顶点则只有一种。

因此

$$d_x=\sum_{i=1}^{x-1}d_i\cdot \begin{cases} 1,&i=x-1,\\ 2d_{x-i},&i<x-1 \end{cases} \cdot\binom{x-1}{i-1}.$$

最终的 $2d_n$ 包含全红与全蓝两种单色方案，答案为 $2d_n-2$。

子任务 1

直接按上述递归式递归枚举分解，不保存已经算过的 $d_x$。每次重新枚举包含顶点 $1$ 的连通块大小，复杂度呈指数增长，但 $n\le12$ 时足够。证据中的独立定义暴力还会枚举 $n\le6$ 的全部边染色并逐个检查诱导子图。

子任务 2

自底向上计算 $d_x$，但每次转移都用乘法公式现场计算组合数 $\binom{x-1}{i-1}$，单次组合数查询为 $O(n)$，总复杂度 $O(n^3)$。

子任务 3

预处理阶乘与逆阶乘，使每个组合数查询变为 $O(1)$，递推总复杂度降为 $O(n^2)$。

做法

1. 预处理 $0$ 到 $n$ 的阶乘与逆阶乘。
2. 初始化 $d_1=d_2=1$。
3. 按 $x=3,4,\ldots,n$ 枚举包含固定顶点的连通块大小 $i$，应用递推式。
4. 输出 $(2d_n-2)\bmod998244353$。

正确性证明

若红色诱导图不连通，则任取两个不同连通块中的顶点，它们之间的边必为蓝色，所以蓝色诱导图连通。故题目条件等价于每个诱导子图不出现“原图与补图同时连通”，也就是余图可分解图的递归定义。对任一不连通合法图，包含顶点 $1$ 的连通块唯一；递推恰好选择这个块的顶点、其连通合法结构以及剩余顶点的任意合法结构，因此无重不漏。补图给出连通与不连通合法图之间的双射，故合法总数为 $2d_n$。最后删去两种单色方案即得答案。

复杂度

满分算法时间复杂度为 $O(n^2)$，空间复杂度为 $O(n)$。中档算法时间复杂度为 $O(n^3)$，小档递归为指数复杂度。