LOJ3045 「ZJOI2019」开关

• my submission on loj.ac
• 参考了 zsy的博客

设

$$\begin{gathered} A(x) = \sum_{i=0}^\infty [\text{操作 i 次之后状态为 s 的概率}]\frac{x^i}{i!}\\ B(x) = \sum_{i=0}^\infty [\text{操作 i 次之后状态为 000.....00 的概率}]\frac{x^i}{i!} \end{gathered}$$

那么（可以类比奇自然数和偶自然数的 EGF）

$$\begin{gathered} A(x) &=& \prod_{i=1}^n \frac{e^{\frac{p_i}{P}x}+(-1)^{s_i}e^{-\frac{p_i}{P}x}}{2}\\ B(x) &=& \prod_{i=1}^n \frac{e^{\frac{p_i}{P}x}+e^{-\frac{p_i}{P}x}}{2} \end{gathered}$$

$A(x)$ 和 $B(x)$ 都可以表示为 $\sum_{i=-P}^P a_i e^{\frac{i}{P}x}$ 的形式。

设 $A(x),B(x)$ 对应的 OGF 为 $F(x),G(x)$。（$e^{cx}$ 对应的 OGF 为 $\sum_{i=0}^\infty (cx)^i = \frac{1}{1-cx}$）

设

$$H(x) = \sum_{i=0}^\infty [\text{操作 i 次之后第一次达到 s 的概率}]\frac{x^i}{i!}$$

则

$$\begin{gathered} H(x) G(x) = F(x)\\ H(x) = \frac{F(x)}{G(x)} \end{gathered}$$

答案是 $H(1)’ = \frac{F’(1)G(1) - F(1)G’(1)}{G^2(1)}$。

但是，因为 $\frac{1}{1-\frac{P}{P}x}$ 这一项在 $x=1$ 的时候没有定义，所以不能直接算。

对 $H(x)$ 上下同时乘以 $\prod_{i=-P}^P(1-\frac{i}{P}x)$，这时候的 $F(x),G(x)$ 都是这样的形式：

$$\sum_{i=1}^n a_i \prod_{j\neq i} (1-\frac{j}{P})$$

此时的 $F(x)$ 对应的 $F(1),F’(1)$ 为（由于 $x=1$，所以所有系数里面有 $(1-\frac{P}{P}x)$ 的项都没了）：

$$\begin{gathered} F(1) = a_P\prod_{i\neq P} (1-\frac{i}{P})\\ F'(1) = \sum_{i} a_i \sum_{j\neq i} \left(-\frac{j}{P}\right) \prod_{k\neq i,k\neq j} \left(1-\frac{k}{P}x\right)\\ = \sum_{i\neq P} a_i (-1) \prod_{k\neq i, k\neq P} \left(1-\frac{k}{P}\right) + a_P \sum_{j\neq P} \left(-\frac{j}{P}\right)\prod_{k\neq P,k\neq j} \left(1-\frac{k}{P}\right)\\ = - \left(\prod_{k\neq P} ( 1-\frac{k}{P}) \right) \cdot \left( \sum_{i\neq P} \frac{1}{1-\frac{i}{P}} \left(a_i + a_P \cdot \frac{i}{P}\right)\right) \end{gathered}$$

$G(1),G’(1)$ 的计算同理。