哈集幂难被掳夺

· · 算法·理论

第二次更新于：2026.2.27。

黎明前的巧克力

题意

原题链接。

选出长度为 n 的序列 a 中的两个可空不交子序列，使得这两个子序列的异或和相等。0\le a_i<2^V。

做法

考虑集合幂级数。我们要选出一个子序列，这个子序列的异或和为 0，子序列内部的数可以选择选入第一个子序列或者第二个子序列。

不难发现这是在求 \displaystyle [x^0]\prod_{i=1}^n(1+2x^{a_i})。

由于 FWT 的性质不足，考虑一种暴力也就是做 n 次 FWT 后点乘再 IFWT。

考虑 FWT 的定义式：\displaystyle \hat{F}_i=\sum_{j=0}^{2^V-1}F_j(-1)^{i\cap j}。

容易发现对 1+2x^{a_i} 做 FWT 后只有两种数也就是 -1 和 3。

考虑点乘后的，IFWT 前的序列中，每一项的贡献为 (-1)^{z}3^{n-z}。

考虑算出 z。我们把所有 a_i 放到一个序列 b 中做 FWT，根据 \hat{b}_i 的值算出 z_i 即可。

总结

这个做法还可以用到 Triple 上。

稍微拓展一下就是 goods。

我的 XOR 卷积人生

题意

原题链接。

你要在两个长度为 2^n 的矩阵序列上做 xor 卷积，没有任何手段获取乘法逆元。

要求为 O(n^22^n)。

Part 1

考虑 n=1 怎么做。

对于序列 [a_0,a_1] 与 [b_0,b_1] 做异或卷积可以得到 [a_0b_0+a_1b_1,a_0b_1+a_1b_0]。

考虑如何把这个过程拆分成点乘。

设计一个形式元 x，计算 (a_0+a_1x)(b_0+b_1x)。

得到的结果是 a_0b_0+a_1b_0x+a_0b_1x+a_1b_1x^2。

我们想要的结果是 f(x)=a_0b_0+a_1b_0x+a_0b_1x+a_1b_1。

朴素的做法是设计 x^2=1，然后让 x=1,-1。这两个根为 \alpha,\beta。

求出 f(\alpha),f(\beta) 后再插值还原 f。

Part 2

对于 n 为任意的情况。我们设计 x^{S} 表示 \displaystyle \prod_{i\in S}x_i。所以 x 其实是一个长度为 n 的向量 [x_0,x_1,...,x_{n-1}]。

设计集合幂级数 f(x)=\displaystyle \sum_{i=0}^{2^n-1} A_ix^i。

我们再设计 2^n 个根 X_p。定义 X_p=\displaystyle \prod_{i=0}^{n-1}[p_i=0]\alpha+[p_i=1]\beta。

代入这些根后得到 2^n 个结果 Y_p=f(X_p)。代入根的过程容易用分治加速。

得到 Y 后，插值的过程也容易用分治加速。

对于 xor 卷积，要解方程 x^2=1，根是 \alpha=1,\beta=-1。

对于 or 卷积，要解方程 x^2=x，根是 \alpha=0,\beta=1。

Part 3

考虑子集卷积。

要解的方程是 x^2=0，这是重根，无法插值。

设根为 \alpha=0,\beta=\epsilon。维护含有 \epsilon 的多项式即可。

插值时可以求逆。具体的，我们让 Y_0=f(0),Y_1=f(\epsilon)。

拉格朗日插值得到 Y_0\dfrac{x-X_1}{X_0-X_1}+Y_1\dfrac{x-X_0}{X_1-X_0}。容易求解。

最后得到答案后再让 \epsilon\leftarrow 0 即可。

Part 4

我们让原题的 \alpha=1,\beta=\epsilon-1。

此时要做多项式操作，复杂度变为 O(n^32^n)。

Part 4.5

不妨把 x 平移一位，也就是 a_0+a_1(x+1-1)。我们让 a_0\leftarrow a_0+a_1，这样变成 a_0+a_1(x-1)。

这个时候我们让 (x-1)^{2}=1，解得 \alpha=0,\beta=2。

我们设 \beta=\epsilon，跑一遍子集卷积，最后再让 \epsilon\leftarrow 2 即可。最后再还原真正的 c_0,c_1。

时间复杂度可以复用子集卷积的实现得到 O(n^22^n)。

总结

这个题把 FWT 看成了一种多项式多点求值方法，把 IFWT 看成了一种多项式插值方法。是一道不可多得的好题。

3^N Minesweeper

题意

原题链接。

做法

我们来考虑用矩阵表示 FWT。

一般来讲，FWT 可以看成 \displaystyle \hat{F}_i=\sum_{j=0}^{3^n-1} c(j,i) F_j。

然后我们要对这个矩阵 c 求逆来得到逆变换（IFWT）。

考虑拆出一个 3\times 3 的矩阵 c_0 表示 n=1 时的矩阵。c_1 表示 c_0 的逆矩阵。

那么我们把 c(j,i) 表示成 \displaystyle \prod_{v=0}^{n-1} c_0(j_v,i_v)。

接下来证明 \displaystyle c^{-1}(j,i)=\prod_{v=0}^{n-1} c_1(j_v,i_v)：

F_i=\sum_{j=0}^{3^n-1}c^{-1}(j,i)\sum_{k=0}^{3^n-1} c(k,j) F_k\\ F_i=\sum_{j=0}^{3^n-1}\left(\prod_{v=0}^{n-1} c_1(j_v,i_v)\right)\sum_{k=0}^{3^n-1} \left( \prod_{v=0}^{n-1} c_0(k_v,j_v)\right) F_k\\ F_i=\sum_{k=0}^{3^n-1} \sum_{j=0}^{3^n-1}\left(\prod_{v=0}^{n-1} c_1(j_v,i_v)\right)\left( \prod_{v=0}^{n-1} c_0(k_v,j_v)\right) F_k\\ F_i=\sum_{k=0}^{3^n-1} \sum_{j=0}^{3^n-1}I(k,j)I(j,i) F_k\\

这个显然成立。由于逆矩阵如果存在就唯一所以得解。

考虑快速计算。接下来我们引入 FWT 的矩阵形式。

\hat{F}_i=\sum_{j=0}^{3^n-1} c(j,i)F_j\\ \hat{F}_i=\sum_{j=0}^{3^n-1} \left( \prod_{v=0}^{n-1} c_0(j_v,i_v)\right)F_j\\ \hat{F}_i=\sum_{j=0}^{3^{n-1}-1} c_0(0,i_{n-1})\left( \prod_{v=0}^{n-2} c_0(j_v,i_v)\right)F_j +\sum_{j=3^{n-1}}^{2\times 3^{n-1}-1} c_0(1,i_{n-1})\left( \prod_{v=0}^{n-2} c_0(j_v,i_v)\right)F_j+\sum_{j=2\times 3^{n-1} }^{3^n-1} c_0(2,i_{n-1})\left( \prod_{v=0}^{n-2} c_0(j_v,i_v)\right)F_j \\

考虑预处理 \displaystyle F'_i=\sum_{j=0}^{3^n-1} \left( \prod_{v=0}^{n-2} c_0(j_v,i_v)\right)[j_{n-1}=i_{n-1}]F_j。

这样可以得到 \hat{F}_i=c_0(0,i_v)F'_a+c_0(1,i_v)F'_b+c_0(2,i_v)F'_c。其中 a,b,c 为改变 i 的位 n-1 变为 0/1/2 后得到的三进制数。这就是 FWT。

总结

矩阵形式的 FWT 可以用来描述一些更一般的问题。

欧伊昔说了任意运算表的情况，但我不会。其实大概意思就是把每一维拆成更多矩阵但是先不写了。

集合划分计数

题意

原题链接。

在长度为 m 的序列 a 中选至多 k 个 [0,2^n-1] 的二进制数使得他们两两的按位与为 0，按位或为 2^n-1。

做法

弱化问题是“不交并”集合幂级数的 \exp。这也是最常说是集合幂级数的运算。

先理解一下 O(n^22^n) 做 \exp 这件事情。

我们设计了一个新的元 y。这其实就是之前说的 \epsilon。

但是现在换个角度，我们先对 x 这一维做 or-FWT。

什么意思？就是每一维代入 0 和 1 做点求值就懂了。

这个时候我们 y 这一元一直没有变，所以我们就是做了 n 次 or-FWT，点求值出来其实 1 代表的是当前这个维度的 y^i。

这样子我们求完后就要求出 2^n 个点值的答案。这就是在 y 这一维上做一遍 \exp。

然后我们再 IFWT 回去就好了。

那么这个题就是把里面的那次操作改了一下。

总结

可以逐点牛顿迭代法，但我不会。

FWT + IFWT 是一种插值方法，这个东西是有用且直观的。

逐点牛顿迭代法

因为看到了 Exber 的文章会了，upd in 2026.2.27。

引入

给你一个形式幂级数 H(x) 和集合幂级数 F(x)。

现在你需要求出 H(F) 的结果。

具体的来说：

H(F)\\ =\sum_{i=0}^{\infty} [x^i]H(x) F^i

显然如果 [x^0]F(x)=0 那么 H 中超过 n 次的项没有用，不妨假设这一点，H 的项数就只有 n+1。

原题链接。

思想

我们设 G=H(F)。

首先根据之前写的东西，集合幂级数可以看成 n 元形式幂级数，运算对 x_0^2x_1^2...x_{n-1}^2 多项式取模。

然后那么我们可以对等式两边同时对 x_{n-1} 这一维做偏导。

如果不知道什么是偏导那就是把其他元看成常数求导。

G'=H'(F)\cdot F'

根据求导法则，G' 其实就是 \dfrac{[x_{n-1}^1]G}{x_{n-1}^1}，然后 F' 也类似。

那么 H'(F) 其实只有 [x^0_{n-1}]H'(F) 有用。

所以我们得到如下等式：[x^1_{n-1}]H(F)=[x_{n-1}^0]H'(F)\cdot [x^1_{n-1}]F。

流程

设 H_{i} 是 H 的 i 阶导。

处理 i=1\sim n 轮。

在第 i 轮，我们要处理出 H_{0}(F),H_1(F),...,H_{n-i}(F) 的前 2^i 项。

根据上面的等式，只需要对上一轮的 H_{j+1}(F) 和 F 新的 2^{i-1} 位做集合幂级数乘法就可以得到 H_j(F) 的新 2^{i-1} 位。

时间复杂度 O(\sum_{i=1}^{n}(n-i+1)i^22^i)。

可以说明这个复杂度是 O(n^22^n) 的。

应用

以上文的 k-exp 为例子，那么 [x^0]H_i(x)=[i\le k]。

这个东西很多时候还可以任意模数，所以这个是很牛的。

墓碑密码

题意

原题链接。

做法

考虑生成函数，x 这一维是集合幂级数，记为 x^{i}\cdot x^j =x^{i\oplus j}。y 这一维是普通乘法，记为 y^i \cdot y^j=y^{i+j}。

\sum_{j=1}^m [x^{b_j}y^n]\prod_{i=1}^{n}(1+x^{a_i}y+y^2+x^{a_i}y^3+...)\\ =\sum_{j=1}^m [x^{b_j}y^n]\prod_{i=1}^{n}\dfrac{1}{1-y^2}(1+x^{a_i}y)\\ =\sum_{j=1}^m [x^{b_j}y^n]\dfrac{1}{(1-y^2)^n}\prod_{i=1}^{n}(1+x^{a_i}y)

不妨想办法预处理 [x^{b_j}]\displaystyle \prod_{i=1}^n(1+x^{a_i}y) 这个多项式的每一项，则后面乘上 \dfrac{1}{(1-y^2)^n} 是好做的。

由于“黎明前的巧克力”，考虑 FWT。先回顾一下 FWT 的本质。

定义 \hat F 是 F 的 FWT 后结果。有如下定义式：

\hat{F}_i=\sum_{j=0}^{2^V-1} (-1)^{|i\cap j|} F_j

接下来继续推式子：

\sum_{j=1}^m [x^{b_j}y^n]\dfrac{1}{(1-y^2)^n}\prod_{i=1}^{n}(1+x^{a_i}y)\\ =\dfrac{1}{2^V}\sum_{j=1}^m [y^n]\dfrac{1}{(1-y^2)^n}\sum_{I=0}^{2^V-1}(-1)^{I\cap b_j}(\prod_{i=1}^{n}(1+(-1)^{a_i\cap I}y))

显然需要先处理出每个 I 对应的 n 个 (-1)^{a_i\cap I}。只需要知道 a_i\cap I 是偶数的数量 c_{I}。不妨把 I\to I+1 时 I 改变的后缀位长度 L 对 (-1)^{a_i\cap I} 的影响预处理出来，把这 n 个 01 变量用一个 bitset 表示，只需要做 bitset 的异或后求 count 即可。

知道 c_{I} 后，后面的式子是容易的。

总结

好像这个题没什么特别的，先鸽了。

建造军营 II

题意

原题链接。

题意描述：

你有一个图，请你删去图中的若干条边，使得留下的图联通。

对于剩下的图，有 k 个限制，第 i 个限制要求限制中 p_i 到 q_i 的所有路径上都只有红边（表示驻守军队）。

问你方案数。1\le n\le 16。

变换

首先要解决这个问题：求一个图的边双连通子图个数。

给任意一个图做边双缩点，会得到一棵树。

我们给 \{1,2,...,n\} 划分成若干个不交的子集 S_1,S_2,...,S_k。每个子集代表一个连通图。这些子集之间用 k-1 条边连接并形成一个大连通图，容斥系数为 c^{k-1}。其中 c=-1。这是自然的。

我们称这 k-1 条边是割边。现在我们求出所有点集 S\subseteq \{1,2,...,n\}，且只加入两端编号都 \le i 的割边，S 上的子图形成一个连通图的方案数。记这对应了一个集合幂级数：f_i。注意这并不是只考虑了 \le i 的点。

+ $T_1,T_2,T_3,...,T_l$。这些连通块**不包含**点 $i$。 + $P$。这个连通块**包含**点 $i$。 接下来设计集合幂级数操作。 设计辅助集合幂级数 $g_i$。我们定义：$g_{i,S}=[i\notin S] f_{i-1,S}\cdot coef(S,i) \cdot c$。 其中 $coef(S,i)$ 表示点集 $S$ 中，$< i$ 的点与 $i$ 的连边数。这个定义给出了 $S$ 这个连通块与 $i$ 连出割边的方案数。 我们有：$f_{i,S}=(f_{i-1} \cdot \exp(g_i))_S$。 若 $i\notin S$，则 $f_{i,S}=f_{i-1,S}$。边界条件为 $f_0=F$。 这里是理由：$P$ 代表 $f_{i-1}$，$\exp$ 也就是自由划分。 定义上面一个问题为 $G=\mathrm{ans}(F,c)$。 ## 做法 限制对应的操作：将所有 $p_i$ 所在边双到 $q_i$ 边双所在边双经过的所有边标记为**红色**。 我们找出所有**红边涉及到的点**，记为红点，显然对于每个 $(p_i,q_i)$，$p_i$ 和 $q_i$ 都会被找出来。 这些红点，在**缩点后的树**上可以构成若干个红色连通块。 我们尝试计算一个点集 $S\subseteq \{1,2,...,n\}$ 的导出子图，通过删边，**构成了一个红色连通块**的方案数。 计算方式考虑使用上面的问题。我们构造一个辅助的集合幂级数 $F$，表示删边后 $S$ 的导出子图是一个连通图，并且对于一对限制 $(p_i,q_i)$，这两个点要么都在 $S$ 中，要么都不在 $S$ 中。 Hint：考虑 $F'=\mathrm{ans}(F,-1)$ 的意义。 选出一组划分，相当于删去缩点后树上的若干条边，这样剩下了若干个连通块，这些连通块内，“对于一对限制 $(p_i,q_i)$，这两个点要么都在 $S$ 中，要么都不在 $S$ 中。” 由于这样，红边实际上不会经过删掉的这条边。所以删掉的边一定是不合法的，那么因为删掉的边的权值为 $1+(-1)$，所以我们用这种方式容斥掉了。 所以 $F'$ 就是上面说的，一个点集 $S\subseteq \{1,2,...,n\}$ 的导出子图，通过删边，**构成了一个红色连通块**的方案数。 --- 接下来统计黑色点和黑色边的情况。 先算黑色连通图的集合幂级数。**此时每条边还可以选择驻守军队**。 我们设 $G_0=3^{coef(S)}$，对其作 $\ln$ 就可以求出 $G$ 也就是连通图的方案。 然后算 $G'=\mathrm{ans}(G,-2)$，这也是自然推广。$G'$ 就是黑色边双的方案。 --- 接下来统计红点连通块（注意这里的红点是缩点后树上的意义）与黑色边双的组合。 因为把这些东西组合起来的是可以驻守军队的边。所以最终的集合幂级数就是 $\mathrm{ans}(F'+G',2)$。 ## 总结 好像抄其他题解的东西比较多，我比较笨 /ll 往这里放这个题，大概是因为边双连通 - 连通变换。 # 主旋律 ## 题意 [原题链接](https://www.luogu.com.cn/problem/P11714)。 给有向图删边使得其强连通，求方案数。 ## 第一个问题 给无向图定向使得其是一个 DAG，求方案数。 设 $dp_S$ 是 $S$ 的导出子图为 DAG 的方案数。 计算 $S$ 时，钦定一个点集 $T\subseteq S$，令这个点集是入度为 $0$ 的。 那么我们有结论： $$ dp_S=\sum_{T\subseteq S,T\neq \varnothing} 2^{coef(T,S/T)} dp_{S/T} (-1)^{|T|+1} $$ 考虑怎么证明。 先假设所有 $S$ 的真子集 $S'$ 的 $dp_{S'}$ 都能算对。 考虑**先行枚举**一种可行的 DAG。记这个 DAG **实际上**入度为 $0$ 的点集为 $T_0$。 由于 $dp_{S/T}$ 都算对了，对这种可行的 DAG 的贡献是 $1$，那么会产生贡献的 $T\subseteq T_0,T\neq \varnothing$。 可以说明，所有会产生贡献的 $T$ 的容斥系数之和为 $[T_0\neq \empty]$。 总结：DAG 容斥其实是**集合划分容斥**的思路，也就是对于每种**确定的方案**都要算对贡献。 我目前还有一个坑是集合划分容斥，不知道省选前能不能写完。 ## 做法 考虑本题的做法。 计算 $dp_{S}$ 表示点集 $S$ 的导出子图是强连通图的方案数。 有如下公式： $$ dp_{S}=2^{coef(S,S)}-\sum_{T\subseteq S,T\neq \varnothing} g_{T}2^{coef(T,S/T)+coef(S/T,S/T)} $$ 定义 $g_{S}$ 是点集 $S$ 里划分成若干个强连通分量，并且互相没有连边。若强连通分量有 $x$ 个，则容斥系数为 $(-1)^{x+1}$，容斥系数的和。 $$ g_{S}=(-1)\sum_{T\subseteq S,\min(S)\in T} dp_{T}g_{S/T} $$ 令 $g_0=-1$。转移的时候，先求出 $g_{S}$ 除了 $dp_{S}$ 那一项以外的答案，然后转移 $dp_{S}$，然后求出 $g_S$ 的实际值。 然后算 $coef(T,S/T)$ 在每个 $S$ 处重新算就好了。具体的，我们给每个点 $x$ 记一个二进制数 $b_x$ 表示 $x$ 的出点，只需要求 $\mathrm{ppc}(b_x\& (S/T))$ 就可以把 $x$ 到 $S/T$ 的边数求出，算 $coef(T,S/T)$ 也类似。 ## 总结 这个题应该是 $3^n$ 题入门题？ # 岁月 ## 题意 [原题链接](https://www.luogu.com.cn/problem/P11834)。 一个无向图，每条无向边看成两条有向边，独立决定是否保留共四种情况。 边有边权，问你原图最小生成树和新图最小外向生成树权值相同的概率。 ## C 性质 C 性质：边权全部是 $1$。这等价于存在一个点可以到所有点。 Hint：考虑怎么判定点 $1$ 可以到所有点。 设 $f_{S}$ 为点集 $S$ 被点 $1$ 可达的概率。 考虑算 $1$ 不能到达整个点集 $S$ 的概率，可以得到： $$ f_S=1-\sum_{1\in T,T\subsetneq S} f_{T}2^{-coef(T,S/T)} $$ Hint：可以到达所有点的点集 $R$ 有什么性质？ 显然这个点集 $R$ 强连通，现在有三种概率： + 点集 $R$ 外的点不可以到达点 $R$ 内的概率。 + 点集 $R$ 的导出子图强连通的概率。 + 点集 $R$ 可以到达所有点的概率。 这三部分在概率上独立，分别计算。 第一部分：显然是 $2^{-coef(R,U/R)}$。 第二部分：使用上一个题“主旋律”可以求得 $R$ 强连通的概率。 第三部分：再做一次上面的 dp，复杂度为 $O(4^n)$。 考虑优化，注意到我们进行 dp 后，只需要知道 $f_{U}$ 就好了。 我们尝试对这个 dp 进行转置。上面那个 dp 可以转置成这样： $$ h_{U}=1\\ h_{S}=-\sum_{S\subsetneq T} 2^{-coef(T,S/T)}h_T\\ f_S=\sum_{S\subseteq T} h_T $$ 这样我们可以在 $O(3^n)$ 的时间复杂度内解决 C 性质。 结合 A,B 性质可以获得 $64$ 分。 ## 做法 考虑刻画最小外向生成树。 考虑 $w_i\le 2$。 类似 Kruskal，我们加入所有 $=1$ 的边，假设这样会形成 $k$ 个连通块，那么显然原图的最小生成树里有 $n-k$ 条边权为 $1$ 的边。 考虑删去一些边后的最小外向生成树。显然此时每个连通块都要出现一棵最小外向生成树。不然最后边权为 $1$ 的边权数量就不对。 类比上面的思考，我们得到如下的判定方法： + 将**原图**所有 $\le w$ 的边保留，此时每个连通块都满足“原图最小生成树等于新图最小外向生成树”。 考虑转移 $w\to w+1$。我们将原图中 $\le w$ 边构成的连通块找出来，新增若干条边权为 $w+1$ 的边，这会导致若干个小连通块被合并成一个大连通块。此时每个大连通块可以认为是独立的。 接下来明确上述定义。我们对于一个小连通块的点集 $S$，记一个 $S$ 的子集 $R$，表示 $R$ 中的点都可以作为合法的最小外向生成树的根，记这些点为**根点**。 继续明确。对于每条边权为 $w+1$ 的边，如果这条边在小连通块内部，则可以忽视这条边。只观察那些沟通两个小连通块的边。 对于小连通块 $S$，可以想象，如果到达了 $R$ 中的点，那么可以立刻到达整个连通块内的点。如果到达了 $S/R$ 中的点，那么无法立刻到达整个连通块。那么可能会有如下问题：可不可以通过到达 $S/R$ 中的点来间接的到达整个连通块？ 看起来是可以的，但是实际上不行，我们是为了构建外向树而到达这些点的，那么如果一个点可以再次到达自身，这样是构造不出树的，所以我们断言：所有单向边 $(u,v)$，如果 $v\in S/R$，则 $v$ 无用。可以自己手玩一下。 可以发现对于一条边，点 $u$ 关键的点在于 $u$ 所在的连通块，对于点 $v$，其一定也代表那个连通块的 $R$。 继续前进，先拆分概率，这里有如下两个定义。 + $S'$ 为新产生的大联通块的点集。定义 $R'$ 为新产生的大连通块的根点集合，其来源为部分小连通块根点的并集，形如 $R_1\cup R_2\cup R_3\cup ...\cup R_l$。 + 有概率 $F_{S,R}$，表示此时小连通块 $S$ 的根点集合是 $R$ 的概率。 + $R'$ 强连通的概率。 + $R'$ 可以到达 $S'$ 中所有点的概率。 + $R'$ 不被到达 $S'/R'$ 内点到达的概率。 于是我们又要重新改写之前的所有式子，我们一步步来。 先规划 $F_{S,R}$ 在系数里的出现时间，算第一种概率时顺便统计 $R'$ 相关的 $F_{S,R}$ 是合理的，同样的算第三种概率时就可以算剩下的系数。 定义 $c_i$ 是点 $i$ 所属的小连通块颜色。注意我们转移时其实只知道这个。再定义 $G(S)$ 为通过 $S$ 中点反推出这些点所属的若干个连通块。 第一步是重写主旋律。这部分相对没那么难。 别管那个 $F_{S,R}$ 先，我们最后再加上都没问题。先写出根点集 $S$ 的导出子图是强连通的概率 $dp_S$，和将根点集 $S$ 拆成若干个互相独立的强连通分量的概率 $g_S$。 $$ dp_S=1-\sum_{T\subseteq S}[\forall i\in T,j\in S/T,c_i\neq c_j]g_T2^{-coef(T,G(S/T))}\\ g_S=(-1)\sum_{T\subseteq S,\min(S)\in T}[\forall i\in T,j\in S/T,c_i\neq c_j]dp_Tg_{S/T}2^{-coef(T,G(S/T))-coef(G(T),S/T)} $$ 转移方法之前说过了，可以去看前面的主旋律题解。 第二步是 $R'$ 可以到达 $S'$ 中所有点的概率。仍然设计出普通 dp 后再转置。注意此时需要考虑 $F_{S,R}$。 $$ f_S=F(G(S),S)-\sum_{R'\subseteq T,T\subsetneq S} F(G(S/T),S/T)f_{T}2^{-coef(G(T),S/T)} $$ 转置长成这样： $$ h_{U}=1\\ h_{S}=-\sum_{S\subsetneq T} 2^{-coef(G(S),T/S)}F(G(T/S),T/S)h_T\\ f_S=\sum_{S\subseteq T} F(G(S),S)h_T $$ 差不多吧。最后是 $R'$ 不被 $S'/R'$ 内点到达的概率。只算一下 $2^{-coef(G(S'/R'),R')}$ 就好了。 然后还有看起来很恶心的 $coef$ 问题。但是这不是主旋律，所以 $coef$ 可以容斥，算不算是出题人的一点心意？ 可以分析出时间复杂度为 $O(3^n)$。 ## 总结 我已急哭。