[ZJOI2019] 开关 (一种扩展性较高的做法)

题意：

有n个开关，一开始状态都为关闭。每次随机选出一个开关将其状态改变，选出第i个开关的概率为${ p_i over sum_{i=1}^n p_i} $,求状态第一次变为s的操作步数。

题解：

考虑先从组合方法入手。
最基本的思路就是枚举一种必定结束的状态，但是这样的状态不一定合法，因为这个状态的前缀可能已经结束了，所以我们可以容斥若干个前缀，强制这些前缀已经结束，来算出这个状态中没有一个前缀能够结束的方案数。
当然，在枚举的过程中，"一种状态"可以通过枚举每一个开关的操作次数(x_i)，再将这些操作次数排列起来，我们枚举前缀的时候，同样枚举每个开关的操作次数，那么我们可以写出答案的式子：

[sum_{x_i} prod [2|x_i-s_i] prod q_i^{x_i} sum_{i=1}^nx_i sum_{m=0}^{infty} sum_{y_{1i};exists i,y_{1i}>0 } sum_{y_{2i};exists i,y_{2i}>0 }... sum_{y_{mi};exists i, y_{mi}>0 } sum_{{z_i};exists i,z_i>0 }\ prod [2|y_{ij}] prod_{j}[sum_{i=1}^m y_{ij} +z_i = x_i] (-1)^m {(sum_{i=1}^m z_i)! over prod_{i=1}^n z_i!}prod_{i=1}^m {(sum_{j=1}^n y_{ij})! over prod_{j=1}^n y_{ij}} ]

(q_i)为(p_i over sum p_i)

看起来十分复杂，其实有很多可以化简的地方，为了保证题解的简洁性，这里不一一赘述。上述式子最难化简的莫过于是(sum x_i),这个其实是一个带权方案数，在算的时候我们可以认为是计算$[y^1]prod_{i=1}^n (1+x_iy) $,所以只需要记常数项与一次项系数。

用指数型生成函数来表示，可以方便的得到答案式子：

[F(x)=prod (e^{q_ix} + q_ixye^{q_ix} +(-1)^{s_i} e^{-q_ix} - (-1)^{s_i} q_i xye^{-q_ix}) \ =sum_{i=0}^{infty} {f_{0i} over i!}x^i + {f_{1i} over i!}x^iy ]

[G(x)=prod (e^{q_ix} + q_ixye^{q_ix} + e^{-q_ix} - q_i xye^{-q_ix}) \ =sum_{i=0}^{infty}{g_{0i} over i!}x^i + {g_{1i} over i!}x^iy]

记(f_0(x)=sum_{i=0}^{infty}f_{0i}x^i,f_1(x)=sum_{i=0}^{infty}f_{1i}x^i,f(x)=f_0(x)+f_1(x)y)
(g_0(x)=sum_{i=0}^{infty}g_{0i} x^i,g_1(x)=sum_{i=0}^{infty}g_{1i}x^i,g(x)=g_0(x)+g_1(x)y)
以(F(x))为例,(F(x)=sum_{i=- infty}^{infty} a_i e^{ix} + b_i xy e^{ix})
可以得到(f(x)=sum_{i=- infty}^{infty} {a_i over 1-ix}+{b_i xover (1-ix)^2})
答案为

[lim_{x o 1 }[y^1]f(x)sum_{m=0}^{infty}(-g(x)+1)^m=lim_{x o 1}[y^1]{f(x) over g(x)}\ ={f_2(x)g_1(x) -g_2(x)f_1(x) over g_1^2(x)}]

我们发现在(g_1(x))中有(frac {1} {1-x})的项,在(f_2(x),g_2(x))有(frac {1} {(1-x)^2})的项，所以我们发现，答案的分子有三阶无穷大的项，分母有二阶无穷大的项。
那么是否意味着答案发散呢？恰恰相反，因为感性理解答案肯定是收敛的，所以我们有理由认为分子上三阶无穷大的系数为0，而事实也确实如此，因为(f_2(x)与g_2(x))的(1 over (1-x)^2)项系数相同，(f_1(x)与g_1(x))的(1 over 1-x)项的系数也相同，我们计算答案，只需要计算分子的二阶无穷大的值除以分母的二阶无穷大的值即可，又因为两个无穷大都为({1over (1-x)^2})，所以是可以约去的。

这种做法与网上的大致相同，但是在处理(sum x_i)项的时候不太一样，网上题解大多是用的求导来解决第i项对答案的贡献为i的问题，而本文观察到了(sum x_i = [y^1]prod (1+x_iy))的性质。这种做法无疑具有比较高的扩展性，例如操作开关i需要(a_i)的代价，求代价的期望，求导方法便显得十分无力，而这个方法只需要将原式稍稍更改成(sum a_i x_i = [y^1]prod (1+a_ix_iy))即可。
code