LOJ3045 「ZJOI2019」开关

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

设

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

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

$$\begin{array}{ccc}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{array}$$

$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}^{\mathrm{\infty }}(cx{)}^i=\frac{1}{1-cx}$）

设

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

则

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

答案是 $H(1{)}^{\prime }=\frac{F^{\prime }(1)G(1)-F(1)G^{\prime }(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\ne i}(1-\frac{j}{P})$$

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

$$\begin{array}{c}F(1)=a_P\prod _{i\ne P}(1-\frac{i}{P})\\ F^{\prime }(1)=\sum _i{a}_i\sum _{j\ne i}(-\frac{j}{P})\prod _{k\ne i,k\ne j}(1-\frac{k}{P}x)\\ =\sum _{i\ne P}{a}_i(-1)\prod _{k\ne i,k\ne P}(1-\frac{k}{P})+a_P\sum _{j\ne P}(-\frac{j}{P})\prod _{k\ne P,k\ne j}(1-\frac{k}{P})\\ =-(\prod _{k\ne P}(1-\frac{k}{P}))\cdot \left(\sum _{i\ne P}\frac{1}{1-\frac{i}{P}}(a_i+a_P\cdot \frac{i}{P})\right)\end{array}$$

$G(1),G^{\prime }(1)$ 的计算同理。