自动搬运

查看原文

来自洛谷，原作者为

	BJpers2 **

搬运于2025-08-24 22:09:35，当前版本为作者最后更新于2020-07-02 16:01:36，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

本题有两种主流做法，一种是生成函数，一种是异或卷积。

但惊人的是这两个做法最终能够得到完全相同的结果。

一、 生成函数

把$p_i$转为概率，则第$i$步达成目标的概率的EGF为

$$f_e(x)=\prod \frac {e^{p_ix}+(-1)^{s_i}e^{-p_ix}} 2 $$

代入$s_i=0$可得第$i$步恰好回到原点概率的EGF为

$$g_e(x)=\prod \frac {e^{p_ix}+e^{-p_ix}} 2$$

稍微解释一下，求积中那个$(-1)^{s_i}$无非限定了$i$这个开关需要被拨动奇数次还是偶数次，如果$s_i=0$则为双曲余弦函数，表示必须拨动偶数次；反之为双曲正弦函数，表示必须拨动奇数次。

假如把上述两个生成函数分别转为OGF（即把$x^i$的系数乘一个$i!$）$f$和$g$。再设第$i$步恰好第一次达成目标的概率生成函数为$h$。

那么有$hg=f$（考虑通过枚举第一次达成目标的时刻求$f$）。于是问题变为求$(f/g)'|_{x=1}$。

设$\phi_{1-k}=2^n[e^{kx}]f_e(x)=[x^k]\prod (x^{p_i}+(-1)^{s_i}x^{-p_i})=[x^{1-k}]\prod (1+(-1)^{s_i}x^{2p_i})$（注意这里$k$是$[-1,1]$的实数，所以用$[]$这个记号有些不严谨）。最后一步推导用到了$\sum p_i=1$的性质。

同理定义$\gamma_i$。

根据$e^{ix}$转OGF之后恰为$\frac1{1-ix}$（它们都对应数列$1,i,i^2,\dots$）。我们有

$$h(x)=\frac {\sum \frac{\phi_{1-i}}{2^n}\frac 1 {1-ix}}{\sum \frac{\gamma_{1-i}}{2^n}\frac 1 {1-ix}}=\frac {\phi_0+\sum_{i\ne1} \phi_{1-i}\frac {1-x} {1-ix}}{\gamma_0+\sum_{i\ne1} \gamma_{1-i}\frac {1-x} {1-ix}} $$

以上推导和大部分题解是一致的，但是很多题解里都出现了很不清真的式子。实际上这里有一个很优美的推导

设分子为$u(x)$，分母为$v(x)$。注意到$u(1)=\phi_0=1,v(1)=\gamma_0=1$，且$(\frac {1-x}{1-ix})'|_{x=1}=\frac{1}{i-1}(i\ne 1)$。

那么

$$h'(1)=\frac{u'(1)v(1)-v'(1)u(1)}{v^2(1)}=u'(1)-v'(1)=\sum_{i\ne 1}\frac{\phi_{1-i}-\gamma_{1-i}}{i-1}=\sum_{i>0}\frac {\gamma_i-\phi_i} i $$

其实做到这一步已经很好，直接背包求$\phi$和$\gamma$即可，但是为了凸显它和下面一种方法的联系，我需要进一步用$\phi,\gamma$的定义展开这个式子。

$$\begin{aligned} h'(1)& = \sum_{i>0} \frac{\gamma_i-\phi_i}{i}\\ & = \sum_T \frac{1}{\sum_{i\in T}2p_i}(1-(-1)^{\sum_{i\in T}s_i})\\ & = \sum_{T} \frac{[|S\cap T|\equiv 1 \bmod 2]}{\sum_{i\in T} p_i} \end{aligned} $$

这个式子有无比清晰的组合意义：

对所有与目标集合$S$的交大小为奇数的集合$T$，求第一次拨动$T$中的某个开关需要的期望步数之和。

---

二、异或卷积

设$f_i$表示第一次把开关拨成集合$i$的状态所需的期望步数，目标是求$f_S$。

可列出方程：

$$f_S= \begin{cases} 0 & S=\varnothing \\ 1+\sum_{S\oplus\{j\}} f_Sp_j & S\ne \varnothing \end{cases} $$

注意到方程类似于异或卷积，那么另设

$$g_S= \begin{cases} -1 & S=\varnothing \\ p_{i} & S = \{i\} \\ 0 & |S|>1 \end{cases} $$$$h_S= \begin{cases} 2^n-1 & S=\varnothing \\ -1 & S \ne \varnothing \end{cases} $$

容易知道$f*g=h$（$h_{\varnothing}$可以通过把$f$的另外$2^n-1$个方程相加，结合$\sum g_S=0$导出）。

通过简单计算，我们可以求出$g,h$经过沃尔什变换（也就是$n$维DFT）的结果$\tilde g,\tilde h$

$$\tilde g_S=\sum_{i}(-1)^{[i\in S]}p_i-1$$ $$\tilde h_S=\begin{cases} 0 & S=\varnothing \\ 2^n & S\ne \varnothing \end{cases} $$

特别地，$g_0=0$，除此之外任意$g_i<0$。

根据$\tilde f \circ \tilde g=\tilde h$，我们可以求出

$$\tilde f_S=\begin{cases} \sum_{T} \frac{2^n}{1-\sum_{i}(-1)^{[i\in T]}p_i}& S=\varnothing \\ -\frac{2^n}{1-\sum_{i}(-1)^{[i\in T]}p_i} & S\ne \varnothing \end{cases} $$

$\tilde f_{\varnothing}$的表达式可利用$f_{\varnothing}=\frac 1{2^n}\sum_{T} \tilde f_T=0$导出。

最后手动做一次沃尔什逆变换（也就是$n$维IDFT）得出$f_S$的表达式。（以下默认$T$非空）

$$\begin{aligned} f_S & =\frac 1 {2^n}(\tilde f_{\varnothing}+\sum_{T\ne \varnothing} (-1)^{|S\cap T|}\tilde f_T) \\ & = \sum_{T} \frac1{1-\sum_{i}(-1)^{[i\in T]}p_i}+\sum_T(-1)^{|S\cap T|}-\frac1{1-\sum_{i}(-1)^{[i\in T]}p_i} \\ & = \sum_{T} \frac{1-(-1)^{S\cap T}}{\sum_{i}p_i-\sum_{i}(-1)^{[i\in T]}p_i} \\ & = \sum_{T} \frac{2[|S\cap T|\equiv 1 \bmod 2]}{2\sum_{i\in T}p_i}\\ & = \sum_{T} \frac{[|S\cap T|\equiv 1 \bmod 2]}{\sum_{i\in T} p_i} \end{aligned} $$

这很明显跟方法一的结论一致。

---

三、遗留的问题

在给出上述两种方法之后，这道题当中仍然存在一个很大的谜团。那就是，如何从实际角度解答：为什么「第一次抵达状态$S$的期望时间」恰好等于「所有与$S$交大小为奇数的集合的首次被操作期望时间之和」。

$$f(S)=\sum_T [|S\cap T|\equiv 1 \bmod 2]g(T)$$

这个等式的两端都有着无比清晰的实际意义，但是奈何本人才疏学浅，不知如何构建它们之间的实际联系。如果有高手看出了其中的奥妙，还望不吝赐教。

---

四、一些拓展思考

为了解决上一节中的问题，本人尝试对每个开关有$k$种状态的状态寻找普遍的规律，得到了如下表达式

$$f(S)=\sum_{T}\frac {1-\omega^{-\sum S_iT_i}}{\sum(1-\omega^{Ti})p_i} $$

其中$S,T$是重数为$[0,k)$的多重集，$S_i$表示$i$这一维的重数。$w=e^{\frac{2\pi i}{k}}$，也即$k$次单位根。可以代入$w=-1$验证其正确性。

这个式子不再有清晰的组合意义，而且从各种角度来看都很奇怪。因为分子分母都是复数，很难想象以$\frac {3+\sqrt 3i} 2$的概率拨动第$i$个开关会有什么现实的意义。

---

五、 本题做法

根据方法一给出的如下表达式：

$$\sum_{i>0}\frac {\gamma_i-\phi_i} i$$

我们只需求得$\gamma$和$\phi$，设$m=\sum p$，不难发现本质不同的$i$只有$O(m)$个。那么做$n$个物品体积分别为$2p_1,2p_2,\dots,2p_n$的01背包即可。时间复杂度$O(nm)$。

当然这里有一个优化。我们本质上是求$\prod 1+x^{p_i}$的各项系数，所以可以先对每个二项式求$\ln$，求和之后在$\exp$回去。

这看起来是$O(m^2)$，但注意到$\ln (1+x^k)=\int\frac{1}{1+x^k}$，只在$x^k,x^{2k},...$等$\frac m k$个位置有值。那么把所有$p_i$相同的一起处理则可以获得调和级数的复杂度，也就是经典的$O(m\log m)$。（最劣情况应该是前$O(\sqrt m)$个数每个来一个，这时候算出来是$O(m\ln \sqrt m)$）。

然后再做$O(m\log m)$的多项式$\exp$就可以了。

放一下$O(nm)$的代码：

#include<iostream>
#include<cstdio>
#define FOR(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
const int M=50050,P=998244353;
int n,m,x,A,j,iv[M],b[M],f[M],g[M];
int main(){
	scanf("%d",&n);
	FOR(i,1,n) scanf("%d",&b[i]);
	f[0]=g[0]=iv[1]=1;
	FOR(i,1,n)for(scanf("%d",&x),j=m,m+=x;~j;j--)
		(f[j+x]+=b[i]?P-f[j]:f[j])%=P,(g[j+x]+=g[j])%=P;
	FOR(i,2,m) iv[i]=1ll*iv[P%i]*(P-P/i)%P;
	FOR(i,1,m) (A+=1ll*(g[i]-f[i]+P)*iv[i]%P*iv[2]%P*m%P)%=P;
	cout<<A<<'\n';
}