题解 P5326 【[ZJOI2019]开关】
xht
·
·
题解
方便起见，令 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}