题解 P5326 【[ZJOI2019]开关】

方便起见，令 $p_i$ 为 $\frac{p_i}{\sum_{i=1}^n p_i}$。 对于 $i \in [1,n]$，由于先后按 $i$ 需要被算多次，即**有标号**计数，因此考虑 EGF。 令 $F_i(x) = \sum_{n \ge 0} [n \bmod 2 = s_i] \frac{p_i^n}{n!} x^n$，$F(x) = \prod_{i=1}^n F_i(x)$，则 $k![x^k]F(k)$ 就是 $k$ 次达到目标的概率，我们写成 OGF $f(x) = \sum_{k \ge 0} \left(k! \cdot [x^k]F(x)\right) x^k$。 由于我们要求的是第一次达到目标的期望次数，因此要扣掉第一次达到目标后再次返回到目标状态的情况。于是再做一遍上述的过程，求出在 $s_i = 0$，即 $k$ 次状态不变的概率的 OGF $g(x)$。 假设答案的 OGF 为 $h(x)$，则有 $f(x) = g(x) \cdot h(x)$，因此 $h(x) = \frac {f(x)}{g(x)}$。 又由于 $h^\prime(x) = \sum_{n\ge 0} (h_n x^n)^\prime = \sum_{n \ge 0} (h_nn)x^{n-1}$，所以 $h^\prime(1)$ 就是我们要的期望次数。 然后考虑如何计算，我们有： $$ \begin{aligned} F_i(x) &= \sum_{n \ge 0} [n \bmod 2 = s_i] \frac{p_i^n}{n!} x^n = \frac{e^{p_ix} + (-1)^{s_i}e^{-p_ix}}{2} \\\\ G_i(x) &= \sum_{n \ge 0} [n \bmod 2 = 0] \frac{p_i^n}{n!} x^n = \frac{e^{p_ix} + e^{-p_ix}}{2} \\\\ \end{aligned} $$ 于是： $$ \begin{aligned} F(x) &= \prod_{i=1}^n \frac{e^{p_ix} + (-1)^{s_i}e^{-p_ix}}{2} \\\\ G(x) &= \prod_{i=1}^n \frac{e^{p_ix} + e^{-p_ix}}{2} \\\\ \end{aligned} $$ 考虑将 $F(x)$ 写成 $\sum_{i} c_ie^{ix}$，则： $$ \begin{aligned} f(x) &= \sum_{k \ge 0} \left(k! \cdot [x^k]F(x)\right) x^k \\\\ &= \sum_{k \ge 0} \left(k! \cdot [x^k]\left(\sum_{i} c_ie^{ix}\right)\right) x^k \\\\ &= \sum_{k \ge 0} \left(k! \cdot [x^k]\left(\sum_{i} c_i\cdot\left(\sum_{j \ge 0} \frac1{j!}(ix)^j\right)\right)\right) x^k \\\\ &= \sum_{k \ge 0} \left(k! \left(\sum_{i} c_i\cdot \frac1{k!}i^k \right)\right) x^k \\\\ &= \sum_{k \ge 0} \left(\sum_{i} c_ii^k \right) x^k \\\\ &= \sum_{i} c_i\left(\sum_{k \ge 0} i^k x^k \right) \\\\ &= \sum_{i} \frac{c_i}{1-ix} \\\\ \end{aligned} $$ 同理可以将 $g(x)$ 写成 $\sum_{i} \frac{d_i}{1-ix}$，其中 $c_i,d_i$ 都可以 $\mathcal O(nw)$ 背包出来。 最后求 $h^\prime(x)$，由于： $$ h^\prime(x) = \left(\frac{f(x)}{g(x)}\right)^\prime = \frac{f^\prime(x)g(x) - f(x)g^\prime(x)}{g(x)^2} $$ 因此只用计算出 $f(1),f^\prime(1),g(1),g^\prime(1)$ 就可以算出答案了。 但不能直接带入 $x = 1$，因为不收敛。由于是除法，我们可以将 $f(x),g(x)$ 同时乘上 $(1-x)$ 解决这个问题： $$ \begin{aligned} f(x) &= \sum_{i} \frac{c_i(1-x)}{1-ix} \\\\ &= c_1 + \sum_{i \ne 1} \frac{c_i(1-x)}{1-ix} \\\\ f(1) &= c_1 \\\\ \end{aligned} $$ --- $$ \begin{aligned}f^\prime(x) &= \left(\sum_{i} \frac{c_i(1-x)}{1-ix}\right)^\prime \\\\&= \sum_{i} \left(\frac{c_i-c_ix}{1-ix}\right)^\prime \\\\&= \sum_{i \ne 1} \frac{-c_i(1-ix)-(c_i - c_ix)(-i)}{(1-ix)^2} \\\\&= \sum_{i \ne 1} \frac{(i-1)c_i}{(1-ix)^2} \\\\f^\prime(1) &= \sum_{i \ne 1} \frac{(i-1)c_i}{(1-i)^2} \\\\&= \sum_{i \ne 1} \frac{c_i}{i-1} \\\\\end{aligned} $$ 同理 $g(1) = d_1$，$g^\prime(1) = \sum_{i \ne 1} \frac{d_i}{i-1}$，则： $$ \begin{aligned}h^\prime(1) &= \frac{f^\prime(1)g(1) - f(1)g^\prime(1)}{g(1)^2} \\\\&= \frac{d_1\sum_{i \ne 1} \frac{c_i}{i-1} - c_1\sum_{i \ne 1} \frac{d_i}{i-1}}{d_1^2} \\\\&= \sum_{i \ne 1} \frac{c_id_1 -c_1d_i}{(i-1)d_1^2}\\\\\end{aligned} $$