把初始状态和目标状态交换，题目不变。
为了方便，设 \(p_i\) 为 \(i\) 被选的概率，对应到输入即 \(\frac{p_i}{\sum_{j=1}^n p_j}\) 。
设 \(f(S)\) 表示从 \(S\) 状态开始，期望走 \(f(S)\) 步到达全零状态。为了方便，我们定义 \(\varnothing\) 表示全零状态。
那么显然有 \(f(S)=\begin{cases}0&S=\varnothing\\1+\sum p_if_{S \text{ xor } i}&S\not=\varnothing\end{cases}\)。
如果把 \(f(S)\) 看做是集合幂级数 \(F=\sum_S f(S)x^S\)，下半部分的 \(\sum\) 可以看做是一个异或卷积（更多有关位运算的卷积，可以参考我的另一篇博客），那么我们设另一个集合幂级数 \(G=\sum_S g(S)x^S\)，其中 \(g(S)\) 在 \(S\) 中仅含一个元素 \(k\) 的时候为 \(p_k\)，否则为 \(0\)。那么下半部分的 \(\sum\) 就可以看做是 \(F*G\)。
不看 \(\varnothing\)，我们有 \(F*G+1=F\)，即 \(F*(G-1)=-1\)，为了方便，把 \(g(S)\) 做一个微调，即 \(g(S)=\begin{cases}-1&S=\varnothing\\p_i&|S|=1,S\text{ 中的元素为 }i\\0&|S|>1\end{cases}\)。这样在不考虑 \(\varnothing\) 的时候，\(F*G=-1\)。
考虑 \(F*G\) 的 \(\varnothing\) 项是什么，我们可以知道 \(\sum_i(F*G)(i)=\sum_{i,j} F(i)G(j)\)，因为 \(\sum_iG(i)=0\)，所以右边为 \(0\)，所以 \(\sum_i(F*G)(i)=0\)，所以可以推出 \((F*G)(\varnothing)=2^n-1\)。
设 \(H=F*G\)，那么就有 \(h(S)=\begin{cases}2^n-1&S=\varnothing\\-1&S\not=\varnothing\end{cases}\)。
\(G,H\) 我们都知道，考虑反推 \(F\)。
设 \(FWTX\) 为集合幂级数 \(X\) 在 \(FWT\) 之后的结果。根据异或卷积 \(FWT\) 的公式（在上面给出的博客有详细介绍）\(F(i)=\sum_j(-1)^{|i\text{ and }j|}F(j)\)，不难得到 \(FWTG(S)=\begin{cases}0&S=\varnothing\\\sum_{|T|=1}(-1)^{|S\text{ and T|}}p-1&S\not=\varnothing\end{cases}\)，\(FWTH(S)=\begin{cases}0&S=\varnothing\\2^n&S\not=\varnothing\end{cases}\)。对于前者，就是照搬式子，然后在 \(S=\varnothing\) 处特别展开一下。对于后者，\(S=\varnothing\) 的部分是 \(H(S)\) 全部相加显然为 \(0\)，而其它位置，对 \(FWTH(S)\) 贡献为正的 \(H(S)\) 和负的 \(H(S)\) 应该各占一半，而 \(H(\varnothing)\) 的贡献为正，那么剩下的部分相加就应该是 \((-1)\times(-1)\)，再加上 \(H(\varnothing)\) 就为 \(2^n\)。
那么我们可以很轻易的得到，在 \(S\not=\varnothing\) 时， \(FWTF(S)=\frac{2^n}{\sum_{|T|=1}(-1)^{|S\text{ and T|}}p-1}\)，而当 \(S=\varnothing\) 的时候，\(FWTF(S)\) 用除法求就 \(\text{nan}\) 了，所以需要特别处理。
考虑在 \(\sum_SFWTF(S)\) 中每个 \(F(S)\) 的贡献，假设 \(|S|=X\)，枚举 \(|S \text{ and } T|\)，那么就有 \(\sum_k(-1)^kC_X^k2^{n-X}=2^{n-X}[X=0]\)，其中 \(C_x^y\) 表示组合数（后同）。所以 \(\sum_S FWTF(S)=2^nF(\varnothing)\)，而上文有 \(F(\varnothing)=0\)，所以 \(\sum_S FWTF(S)=0\)。所以 \(FWTF(\varnothing)\) 就是 \(-\sum_{S\not=\varnothing}FWTF(S)\)。
根据上面推导，我们也可以知道 \(F(S)=\frac{1}{2^n}\sum_T(-1)^{|S\text{ and }T|}FWTF(T)\)。（原理也是 \(\sum_k(-1)^kC_X^k=[X=0]\)）。
把 \(\varnothing\) 单独考虑，那么就有 \(F(S)=\sum_{T\not=\varnothing}(\frac{1}{1-\sum_{|U|=1}(-1)^{|U\text{ and }T|}p}-(-1)^{|S\text{ and }T|}\frac{1}{1-\sum_{|U|=1}(-1)^{|U\text{ and }T|}p})\)。
把左右相抵的去掉，稍加整理，有 \(F(S)=\sum_{(-1)^{T\text{ and } S}=-1}\frac{2}{2\sum_{|U|=1}p[|U\text{ and }T|=1]}\)。
最后就是一个简单 DP 了（不会吧不会吧，推到这里还不会 DP？）。
设 \(dp_{i,j,0/1}\) 表示前 \(i\) 个开关，分子总和为 \(j\)，交的奇偶性为 \(0/1\) 的方案数。转移显然，总复杂度 \(O(n\sum p)\)。
贴个代码。
1 |
|