题解 P5326 【[ZJOI2019]开关】
BJpers2
·
·
题解
本题有两种主流做法，一种是生成函数，一种是异或卷积。
但惊人的是这两个做法最终能够得到完全相同的结果。
一、 生成函数
把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}
最后手动做一次沃尔什逆变换（也就是$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)$的代码：
```cpp
#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';
}
```