集合幂级数

· · 个人记录

不知道有没有人来看，放个东西免得这个博客啥都没有

集合幂级数入门与奇怪的杂题

FWT

FWT(A)_i=\sum_{i|j=i}A_j\\ FWT(A)_i=\sum_{i\&j=i}A_j\\ FWT(A)_i=\sum_{j}(-1)^{popcount(i\&j)}A_j\\

子集卷积

乘法

\begin{aligned} & f_Sg_T[S\ \& \ T=\varnothing]\rightarrow h_{S|T}\\ &\sum_{S}f_Sx^S\rarr\sum_{S}f_Sz^{|S|}x^S\\ &fz^ax^S \cdot gz^bx^T \rarr fg\ z^{a+b}x^{S|T}\\ &|S|+|T|=|S\ |\ T|+|S\ \&\ T| \end{aligned}

乘法逆

考虑一集合幂级数 f​​ 的乘法逆 f^{-1}​​，满足 fg=h\Leftrightarrow g=hf^{-1}​ 与 f*f^{-1}=\epsilon​（其中 \epsilon​ 是集合幂级数的元函数，有 \epsilon=x^\varnothing​​​​​），这里的乘定义为子集卷积。考虑我们做乘法的过程：先 FWT 过去，然后把每一位的形式幂级数做卷积，最后再 IWFT 回来。于是我们可以先把 f​​ 转成子集卷积的形式，然后再把每一位的形式幂级数求逆，最后 IFWT 回去。做的过程中这里要 FWT/IFWT 各 n​​ 遍，时间复杂度下界已经是 O(2^nn^2)​ 了，所以我们这里可以直接使用 n^2 的暴力多项式求逆。

至于如何 n^2 暴力求逆：我们只需要让 \sum_j\hat f_jf_{i-j}=[i=0] 即可，于是 \hat f_0=f_0^{-1}，\hat f_nf_0=-\sum_{i<n}\hat f_if_{n-i}。

ln 和 exp

这里要求 f_\varnothing=0，以避免不收敛的情况。

\ln(F+1)=\sum_{i\ge1}(-1)^{i+1}\frac{F^i}{i}=\sum_{i=1}^{n}(-1)^{i+1}\frac{F^i}{i}\

CF1034E

给定两个长度为 2^n 的数组 a_0,\cdots,a_{2^n-1},b_0,\cdots, b_{2^n-1},

求出 c_i=\sum_{j|k=i,j\&k=0}a_jb_k​，对 4 取模。

n=21,TL=1s,ML=64MB

首先发现这就是子集卷积，但是暴力做是 O(2^nn^2)​ 的，过不了。

考虑集合占位幂级数的形式 \sum_S(f_Sz^{|S|}x^S+\sum_{i>|S|}\sigma_{i,S}z^ix^S)​​，我们不妨取 z=4，c_i 则可以用卷出来的 x^{|S|} 项系数对 4^{|S|+1} 取模，再除以一个 4^{|S|} 得到。

不知道是哪里的题

给定 n 个点的无向图 G，求连通生成子图个数对 10^9+7 取模。

不妨令 $F=f_Sx^S$ 是生成子图的集合幂级数，$G = g_Sx^S$ 是联通生成子图的集合幂级数，则有 $F=\sum_{i=1}\frac{G^i}{i!}=e^G$，$G=\ln(F+1)$。 把 $F$ 先转成集合占位幂级数，做个 fwt，然后对每一位分别考虑其上的形式幂级数。 尝试求导，则有 $$ G'=\frac{F'}{F+1}\\ G'(F+1)=F'\\ g'_n+\sum_ig'_if_{n-i}=f'_{n}\\ g_{n+1}(n+1)+\sum_i(i+1)g_{i+1}f_{n-i}=f_{n+1}(n+1)\\ \because f_0=0,\therefore g_{n+1}=f_{n+1}-\frac{\sum_{0\le i<n}(i+1)g_{i+1}f_{n-i}}{n+1} $$ 最后考虑 $f_S$ 咋算，发现 $f_S=2^{e}$，其中 $e$ 等于点集 $S$ 内部的边数。 ### LOJ154 给定一个集合 $S=\{x_1,x_2,\cdots,x_n\}$ 与一个集合的集合 $T=\{S_0,S_1,\cdots,S_{m-1}\}$，其中 $S_i\subseteq S$。 定义一个集合 $S'$ 的划分是 $T$ 的一个子集，满足其中所有子集两两不交且所有集合的并为 $S’$。 求集合 $S$ 的大小不大于 $k$ 的划分数量 $\bmod 998244353$。 两划分不同，当且仅当某个子集在其中一个划分中出现且没在另一个划分中出现。 $1\le k\le n\le21,1\le m\le 2^{18},TL=7s

定义 G=\sum_{i=0}^mx^{S_i}​​，F=\sum_Tf_Tx^{T}​​，其中 f_T​​ 是集合 T​​ 的大小不大于 k​​ 的划分数。则答案为 f_S​​，且有 F=\sum_{i=0}^k\frac{G^i}{i!}（同上，乘法是子集卷积）​​。感觉好像不怎么推得动，于是先把 F,G 转集合占位幂级数，做 FWT，此时的乘法就从子集卷积变为了形式幂级数的乘法。然后考虑求导：

F'=\sum_{i=0}^k\frac{G^{i-1}G'i}{i!}=G'(F-\frac{G^k}{k!})\\

令 H=G^k，则有

F'=G'(F-\frac{H}{k!})\\ f'_n=\sum_{i=0}^ng'_i(f_{n-i}-\frac{h_{n-i}}{k!})\\ f_{n+1}(n+1)=\sum_{i=0}^ng_{i+1}(i+1)(f_{n-i}-\frac{h_{n-i}}{k!})\\

然后考虑求 h。可以直接利用定义 O(n\log n\log k) 求，也可以来推推递推式。

H'=(G^k)'=kG^{k-1}G'\\ H'G=kHG'\\ \sum_{0\le i\le n}g_ih'_{n-i}=k\sum_{0\le i\le n}g'_ih_{n-i}\\ \sum_{0\le i\le n}g_ih_{n-i+1}(n-i+1)=k\sum_{0\le i\le n}h_ig_{n-i+1}(n-i+1)\\ g_0h_{n+1}(n+1)=k\sum_{0\le i\le n}h_ig_{n-i+1}(n-i+1)-\sum_{1\le i\le n}g_ih_{n-i+1}(n-i+1)\\ h_{n+1}=\frac{k\sum_{0\le i\le n}h_ig_{n-i+1}(n-i+1)-\sum_{1\le i\le n}g_ih_{n-i+1}(n-i+1)}{g_0(n+1)}\\

这样就可以求出 H，然后再递推出 F 即可。

求一种 F(x)=\sqrt{A(x)} 的递推式也可以用类似的求导推导，这里就不展开讲了。

可以看看这篇博客：https://www.luogu.com.cn/blog/KingSann/yi-lei-tong-guo-sheng-cheng-han-shuo-qiu-xian-xing-di-tui-shi-di-fang-post

CF1326F2

给定一张 n 个点的无向图，无自环重边，对每个 1\sim n 的排列 p_1,p_2,\cdots,p_n，若 p_i 与 p_{i+1} 有边则 s_i=1，否则 s_i=0。对所有 2^{n-1} 种 s 序列，求满足条件的排列数。

n\le 18

首先我们观察到，若我们将所有路径长度写成一个可重集，则可重集相同的状态值也相同。

这启发我们算一算路径条数。设 f_{len,mask}​​​ 是长度为 len​​​​，经过且只经过 mask​​​ 中的点的路径条数。f​​​ 可以用一个形如 dp_{mask,last}​​​​ 的 dp 求出。我们先把 f​​​ 做一个 fwt，然后对可重集进行一个 dfs，dfs 过程中一边 dfs 一边维护一个集合幂级数的点值 g​​，每当我们要加入一段长度为 l​​ 的路径时就将所有 g_{msk}​​ 乘上 f_{l,msk}​​，最后 dfs 到底时再由 IFWT 定义用 O(2^n)​​ 的时间求出第 2^n-1​​ 项的系数，这样看起来就能求出每个 s​​ 对应的答案了。注意这里不需要子集卷积，直接或卷积即可，因为如果两集合有交则所有集合的并不可能是 2^n-1​​。

但是仍然存在问题：我们不能确定某一段路径的结尾和另一段路径的开始之间是否存在边。于是我们考虑做一个容斥：s_i=1​ 表示钦定有边，s_i=0​ 表示不确定有没有边，而我们通过上述算法求得的值是符合此定义的。而真正的答案也可以用这个值来求：设 ans_s​ 表示序列为 s​ 时的方案数，d_s​ 表示序列按照上述定义时为 s​ 时的方案数，则有 ans_s=\sum_{s\subseteq t}(-1)^{\\ppc(t)-ppc(s)}d_t​， 不难发现这就是与卷积的 IFWT 过程，可以 O(2^nn)​ 实现。

CF1336E

给定 n 个数 a_1,a_2,\cdots,a_n，每个数都在 [0,2^m) 内，对每个 i=0\sim m，求选出一个集合异或和的 \text{popcount}=i 的方案数，对 998244353 取模。

Easy version：m\le35,n\le2\cdot 10^5

Hard version：m\le53,n\le2\cdot 10^5

TL=3s

Easy version：

考虑对原来的 n​ 个数建立线性基，不难发现从原来的数中选出一个集合可以得到的异或和也可以从线性基中选出一个集合得到。假设建出来的线性基大小为 k，则我们只需要做这 k​ 的数的问题，做完之后再将答案乘上 2^{n-k}​​ 即可。我们对 k 的大小分别处理：

$k$​ 较大时，将那些没有被消出来的列交换到右边后，线性基会长成这样： ![](https://cdn.fzoi.top/upload/user/c20200605/22011810543700.png) 左边是一堆 1，右边是 $[0,2^{m-k})$ 的数。于是我们可以写一个 dp：令 $f_{i,j,s}$ 表示考虑前 $i$ 个数，前面 $k$ 位取了 $j$ 位，后面 $m-k$ 位的异或和为 $s$ 的方案数，容易转移，时间复杂度 $O(k^22^{m-k})$。 平衡一下复杂度即可通过。 Hard version： $k$​ 小的做法的复杂度是我们可以接受的，但是另外一个做法我们不能接受。考虑分析一下性质。 设 $F=\sum_{i}f_ix^i$​，其中 $f_i=0/1$​ 为能否从线性基中选出一个集合，其异或和为 $i$；$G_k=\sum_i[\text{popcount}(i)=k]x^i$​；则有 $\text{popcount}=i$​ 的答案等于 $[x^0](F*G_i)$​，其中 $*$​​ 是异或卷积。​把这个式子重写一下，也就是 $[x^0]IFWT(FWT(F)\cdot FWT(G_i))$​。经过分析，我们可以得到几个引理： #### 引理 1 $FWT(F)$ 的每一项系数要么是 $2^k$，要么是 0。 证明：考虑 $F*F=2^k\cdot F$，于是有 $FWT(F)\cdot FWT(F)=2^k\cdot FWT(F)$。 #### 引理 2 $FWT(F)$ 中系数为 $2^k$ 的项满足其与该线性空间中的任意一个数的异或和的 popcount 的偶数。 证明：$[x^i]FWT(F)=\sum_j(-1)^{\text{popcount}(i\oplus j)}f_j$ + 引理 1。 #### 引理 3 $FWT(F)$ 中系数为 $2^k$​ 的数自成一个线性空间，且其大小为 $2^{m-k}$​。​ 证明：若两数 $i,j$​ 的系数都为 $2^k$​，则对任意线性空间中的数 $x$​，都有 $ppc(i\ \&\ x),ppc(j\ \&\ x)$​ 为偶数，于是 $ppc((i\oplus j)\ \&\ x)$​ 也是偶数，于是 $i\oplus j$​ 的系数也为 $2^k$​，所以其也是一个线性空间。考虑 $f_0=[x^0]IFWT(FWT(F))=\frac{1}{2^m}\sum_{i}(-1)^{ppc(i\&0)}f'_i=\frac{1}{2^m}\sum_{i}f'_i=1$​，所以 $\sum_{i}f'_i=2^m$​，又因为引理 1，所以满足 $f'_i=2^k$​ 的项有 $2^{m-k}$​​ 个。 有了这个线性空间之后，我们就可以反推 $FWT(F)$，从而计算答案。至于如何得到这个线性空间，可以考虑构造一下它的线性基。我们首先把原线性基没有被消出来的列交换到右边。我们发现原线性空间的大小与新线性空间的大小之积是 $2^m$，这提示新线性基可以将原线性基没消出来的元素消出来。构造出来的线性基如图所示： ![](https://cdn.fzoi.top/upload/user/c20200605/22011811218784.png) 容易证明其中右上部分和左下部分关于主对角线对称。 于是我们可以先把原线性基求出来，再用原线性基求出新线性基，得到新线性空间，从而得到 $FWT(F)$​。现在最后的问题是如何算 $FWT(G_k)$​ 和如何算答案。 #### 引理 4 $[x^i]FWT(G_k)$ 的值只与 $ppc(i)$ 有关。 证明：考虑 FWT 时的 $[x^i]FWT(G_k)=\sum_j(-1)^{ppc(i\&j)}[ppc(j)=k]$。前面那一坨系数相当于指定某 $ppc(i)$ 位，看当前枚举的数中这几位里面有多少个 1。又因为我们对所有 $ppc=k$​ 的数求和，所以值是一样的。 既然这样我们考虑求出这个值。设 $w_k^d=[x^{2^d-1}]FWT(G_k)=\sum_{i\le d}\binom{d}{i}\binom{m-d}{k-i}(-1)^i$，这个可以直接 $O(m)$ 算。 于是最后的答案就是 $[x^0]IFWT(FWT(F)\cdot FWT(G_i))$。假设要计算 $ppc=p$ 时的答案，记录一个桶 $b_i$ 表示新线性空间中 $ppc=i$ 的数的数量，计算的时候枚举每一个数 $i$，其贡献为 $(-1)^{ppc(0\&i)}b_i\cdot\frac 1{2^{m}}\cdot 2^k\cdot [x^{2^i-1}]FWT(G_p)=b_i\cdot\frac 1{2^{m-k}}\cdot w_p^i$，将这些贡献求和即可。时间复杂度 $O(2^{m-k}+m^3)$，将这个算法和前面一个算法拼起来即可。 这题还有个 Bonus 是 $n\le63$，技不如人所以不会。会的哥哥可以现场开麦讲讲 /se ### CF960G 求前缀最大值个数为 $a$，后缀最大值个数为 $b$ 的长度为 $n$ 的排列数，对 998244353 取模。 $n\le100000

考虑如果只有一边怎么做。设 S(n,k) 是有 k 个前缀最大值，长度为 n 的排列数。考虑最小元素放在哪里：若放在开头，则前缀最大值数 +1，反之不变，故有 S(n,k)=S(n - 1,k-1)+(n-1)S(n-1,k)。不难发现这就是第一类斯特林数：将 n 个元素放在 k 个圆排列中，对每个圆排列取其中最大的一个放在开头，后面的顺序接在其后面，即可一一对应一个有 k 个前缀最大值，长度为 n 的排列。

再考虑一下两边的答案是多少：首先最大值肯定既是前缀最大值也是后缀最大值，其他要么是一边要么不是，所以有 ans=\sum_kS(k,a-1)\cdot S(n-1-k,b-1)\cdot\binom{n-1}{k}。此时可以算出 a-1 列和 b-1 列的第一类斯特林数然后卷起来，不过可能我板子常数太大了没跑过去。

然而仔细思考会发现上式其实就等于 S(n-1,a+b-2)\binom{a+b-2}{a-1}，证明考虑组合意义。于是可以一个 log 算出来。

「JOISC 2019 Day3」穿越时空 Bitaro

有 n 个城市，第 i 个城市有一个时间段 [L_i,R_i]，可以在该时间段内花费 1 单位时间从 i 走到 i+1​，若不在该时间段内则不能通行。

有一个人掌握了时间魔法，可以花费一费让时间倒流 1 单位时间；也可以在一个城市停留任意时间，不耗费能量。

有 q 次操作，每次操作均为以下两种之一：

  1. 修改某城市的 [L,R]；
  2. 询问在时刻 x 从城市 s​ 出发，并在时刻 y 身处城市 t 所需的最少费用。
n,q\le300000

首先先把第 i 个城市的时间段变成 [L_i-i,R_i-i]​，这样就不用考虑走路的时间耗费了。

有一个很好看出来的走路策略：能走就走，当前时间 < 左端点就等，当前时间 > 右端点就倒流到右端点然后走。

考虑只有一个城市时所需的代价，发现是一个分段函数。

考虑如果多个城市的交非空，则走过这些城市的代价与只有一个城市，其时间段为这些城市的交所需的代价相同。

考虑如果两个城市的交为空，则对其位置进行分类讨论，发现最后也是一个分段函数，且走过这些城市后所处的时刻是固定的。

考虑两个分段函数合并，发现只需要加一个常数，走出时间取后者即可。

我们发现合并两个区间的城市是容易的，于是可以直接用线段树维护：若有交则维护交区间，否则维护一个三元组 (a,b,c)​​，表示平的一段值为 a​，从 t=b​ 开始上升，走出这段区间后处于时刻 c​。

luogu5163 WD与地图

给定一张 n 个点 m 条边的带点权的有向图，以及 q 个操作，操作有：

  1. 删除一条边。
  2. 单点修改点权。
  3. 询问某个点所在的强连通分量内前 k 大的点权和。
n\le 100000，m,q\le 200000

首先套路地倒着做，把删边变成加边。

我们考虑如果图是无向图，条件是联通，那我们可以方便的直接合并两个连通块，但是本题是有向图 + 强连通分量，因此我们不能在加边的时候直接合并。为了能够合并，我们希望知道每条边连接的两端什么时候会被缩成一个强连通分量。对于询问的维护，可以直接采用权值线段树的合并。

为了计算每条边被缩起来的时间，我们考虑对时间进行二分。假设当前二分到时刻 mid，则可以把加入时刻为 [0,mid] 的所有边加入图中然后跑 tarjan 来 check。单独对每条边计算方案不现实，于是我们考虑做整体二分。假设当前二分区间是 [L,R]，待判断的中点是 mid，则可以把加入时刻为 [0,mid] 的所有边加入图中然后跑 tarjan，被缩起来的点扔到左区间继续做，没被缩起来的扔到右区间继续做。

但是这样时间复杂度显然是假的，事实上在每次 check 的过程中我们都重复加入了很多边。考虑每次做当前区间要加的边在做右区间时也需加入，于是可以用可撤销并查集维护强连通分量，每次做完一个区间先走右区间，右区间做完了再撤销当前区间的修改，做左区间。做每一个区间的时候只加入当前待计算的边集中加入时间 \le mid 的边，也对当前新加的边做 tarjan。这样每一层需要加的边数与做 tarjan 的边数的和都是 O(m) 的，于是可以在 O((n+m)\log m\log n) 的时间内做完。

最后每次只加入那些边，且只对新加的边做 tarjan 不会存在问题的原因是：若某条边没被归到当前区间中，要么其在左边已经被合并了，此时并查集中已经缩好点了；要么其在右边才能合并，在当前区间中将其加入没有意义。也不会出现某条边用当前区间中新加的边不能缩点，用 [0,mid]​ 中所有边就可以缩点的情况：若存在该情况，则说明至少存在一条被缩起来的时间在该区间中的边没被算进该区间，这是不可能的。

「UER #6」逃跑

一个人在平面直角坐标系上从 (0,0) 开始随机游走，往四个方向走的权值是 w_1,w_2,w_3,w_4 且权值与概率成正比。求这个人走 n 次后走过的点数的方差。

n,w\le100 先考虑算 $E(X)$​：直接算好像不太好算，于是考虑枚举是哪个格子（假设是 $(x,y)$）以及它第一次被走到的时间。定义 $f(i,x,y)$​ 是 $i$​ 秒后第一次走到 $(x,y)$​ 的概率，定义 $g(i,x,y)$​ 是 $i$​ 秒后走到 $(x,y)$​ 的概率，我们可以写出这样的生成函数： $$ F(z)=\sum_if(i,x,y)z^i\\ G(z)=\sum_ig(i,x,y)z^i\\ H(z)=\sum_ig(i,0,0)z^i\\ $$ 我们可以发现这样的规律： $$ G=FH,\ F=G/H $$ 因为 $n$ 小，所以可以 $n^2$ 暴力多项式乘法、求逆，总复杂度 $O(n^4)$​。 至于如何 $n^2$ 暴力求逆：我们只需要让 $\sum_j\hat f_jf_{i-j}=[i=0]$ 即可，于是 $\hat f_0=f_0^{-1}$，$\hat f_nf_0=-\sum_{i<n}\hat f_if_{n-i}$。 再考虑算 $E(X^2)$​：也就是某一对点都被走到的概率。 考虑把这些点对分类成两点相同和两点不同，两点相同的贡献即是 $E(X)$，考虑算两点不同就行。换个说法其实就是 $E(X^2)=E(2\binom X2+X)=E(2\binom X2)+E(X)$。 考虑两点不同的贡献，也就是 $E(2\binom X2)$ 怎么算。直接枚举点对就 $n^4$ 了，不可取，但是我们发现某些相对位置一样的点对好像很相似，于是考虑枚举第一次经过的点与第二次经过的点的相对位置，也就是枚举 $a,b$，对所有 $(x,y),(x+a,y+b)$​ 算贡献。 设 $h(i,a,b)$ 表示之前已经经过了 $(x,y)$，在第 $i$ 秒时第一次经过 $(x+a,y+b)$ 的概率对所有 $x,y$ 求和的值，则答案就是对所有 $h$ 求和。考虑枚举第一次经过 $(x,y)$ 的时间： $$ h(i,a,b)=\sum_{t<i,x,y}f(t,x,y)f(i-t,a,b)-\sum_{t<i}h(t,-a,-b)f(i-t,a,b) $$ $\sum_{x,y}f(t,x,y)$​ 可以事先求好，于是时间复杂度 $O(n^4)$​。 ### CF1349D Slime and biscuits 有 $n$ 个人，$s$​ 块饼干，初始时第 $i$ 个人有 $a_i$​ 块饼干，每次操作会先等概率随机出一块饼干，再等概率随机出一个除了原饼干拥有者以外的人把饼干给他，当 $s$ 块饼干都到了一个人手上的时候游戏结束，问要使游戏结束的期望操作次数。 $n\le100000,s\le300000

奇怪的势能法，这方法好像是 dls 原创的？orz

略微分析一下可以发现我们并不在乎某个特定的人拿了几块饼干，即人和人是不区分的，于是我们考虑对饼干数量列势能函数。假设某一次操作前第 i​ 个人有 a_i​ 块饼干，我们设的势能函数为 f()​，则操作前的总势能为 \sum_{i=1}^{n}f(a_i)​​，我们算一下操作后的总势能

\begin{aligned} &\sum_{i=1}^n \frac{a_i}{s}(f(a_i-1)+\sum_{j\neq i}(\frac{n-2}{n-1}f(a_j)+\frac1{n-1}f(a_j+1)))\\ &=\sum_{i=1}^n \frac{a_i}{s}f(a_i-1)+\frac{s-a_i}{s}\cdot\frac{n-2}{n-1}f(a_i)+\frac{s-a_i}{s}\cdot\frac{1}{n-1}f(a_i+1)\\ \end{aligned}

那么为了方便计算，需要让 操作前总势能 = 操作后总势能 + 1：

\sum_{i=1}^{n}f(a_i)=1+\sum_{i=1}^n \frac{a_i}{s}f(a_i-1)+\frac{s-a_i}{s}\cdot\frac{n-2}{n-1}f(a_i)+\frac{s-a_i}{s}\cdot\frac{1}{n-1}f(a_i+1)\\ \Leftarrow f(a_i)=\frac{a_i}{s}(f(a_i-1)+1)+\frac{s-a_i}{s}\cdot\frac{n-2}{n-1}f(a_i)+\frac{s-a_i}{s}\cdot\frac{1}{n-1}f(a_i+1)\\ (s(n-1)-(s-a_i)(n-2))f(a_i)=a_i(n-1)(f(a_i-1)+1)+(s-a_i)f(a_i+1)\\ (a_in+s-2a_i)f(a_i)=(a_in-a_i)(f(a_i-1)+1)+(s-a_i)f(a_i+1)\\ 0=(a_in-a_i)(f(a_i-1)+1-f(a_i))+(s-a_i)(f(a_i+1)-f(a_i))\\

其实我们发现化出来的这几坨式子都是齐次的，因为一般势能法的题的转移写出来都会是齐次的形式。

设 d(i)=f(i)-f(i-1)​，则

(a_in-a_i)(-d(a_i)+1)+(s-a_i)d(a_i+1)=0\\ d(a_i+1)=\frac{a_in-a_i}{s-a_i}(d(a_i)-1)\\

于是可以对 d 进行递推，然后求出 f，最后我们只需要算一算 初态的势能 - 终态的势能 就是期望步数了。

势能法所用的推导有一些前后不是等价的，但势能法本质是个构造的过程，所以只要满足条件就可，不一定需要等价。

好像与“鞅与停时定理”有关。https://www.cnblogs.com/p-b-p-b/p/13297098.html