以「ZJOI2013 抛石子」为引子，浅谈一类概率型生成函数的应用(部分)

大概是全网第一篇用 PGF 做的题解？也顺便普及一下 PGF 知识吧。 其实我写这题时的难点，完全在于实现「高精度 gcd」+「高精度除以高精度」+「第一次写压位高精」+「极限卡常上面」…… 上面是题外话，下面是正文。 _____ # 概率型生成函数 概率型生成函数本质上就是普通型生成函数，只不过多了一个对应关系。 即，如果对于某个离散型随机变量 $X\in\mathbb Z$ ，存在数列 $\{a_n\}$ 满足 $\Pr(X=i)=a_i$ ，那么离散型随机变量 $X$ 的 **概率型生成函数$(\mathbf{PGF})$** 为 $$\mathscr{F}(z)=\sum_{i=0}^{\infty} \Pr(X=i) z^i$$ 那么首先有 $$\mathscr{F}(1)=\sum_{i=0}^{\infty}[z^i]\mathscr{F}(z)=1$$ 同时根据期望的定义 $$E(X)=\sum_{i=0}^{\infty}i\Pr(X=i)$$ 可以知道期望就是 $\mathscr{F}$ 的一阶导数系数和，即 $$E(X)=\sum_{i=0}^{\infty}[z^i]\dfrac{\mathrm{d}}{\mathrm{d} z}\mathscr{F}(z)$$ 那么同时根据方差的定义以及期望的线性性可以得到 $$\mathsf{Var}(X)=E\left((X-E(X))^{2}\right)=E\left(X^{2}-2\cdot X \cdot E(X)+E(X)^{2}\right)=E\left(X^{2}\right)-E(X)^{2}$$ 从而有 $$\mathsf{Var}(X)=\sum_{i=0}^{\infty}[z^i]\left(\dfrac{\mathrm{d^2}}{\mathrm{d} z^2}\mathscr{F}(z)+\dfrac{\mathrm{d}}{\mathrm{d} z}\mathscr{F}(z)-\left(\dfrac{\mathrm{d}}{\mathrm{d} z}\mathscr{F}(z)\right)^2\right)$$ 是因为 $$E(X^2)=\sum_{i=0}^{\infty}i^2\cdot \Pr(X=i)=\sum_{i=0}^{\infty}i\cdot (i-1)\cdot \Pr(X=i)+\sum_{i=0}^{\infty}i\cdot \Pr(X=i)$$ 可以知道前面一项是二阶导，后面一项是一阶导。 然后…然后就可以做题了(倒)。 # ZJOI2013 抛硬币 > 给出一个两面的均匀骰子，正面和反面的概率分别是 $\frac{a}{b}$ 和 $1-\frac{a}{b}$ 。并给出一个长度为 $n$ 的 $01$ 序列 $A$ 。 > > 同时有一个一开始为空的序列。每次掷骰子，如果是反面，就在当前序列末尾写一个 $1$ ，否则写一个 $0$ ，如果发现此时序列中恰好有一个连续子串是 $A$ 则停止。求期望多少次才会停止操作。 > > 我认为合理的数据范围：$1\leq n\leq 10^6$，概率对 $998244353$ 取模。 > > ZJOI2013 的数据范围：$1\leq n\leq 10^3$ 输出确切概率并保留**既约分数形式**。 考虑设 $f_i$ 表示扔了 $i$ 次骰子之后恰好停止的概率，$g_i$ 表示扔了 $i$ 次骰子之后仍未结束的概率。同时考虑对这两个东西建立 PGF，分别为 $\mathscr{F,G}$， 那么有方程： $$\mathscr F(z)+\mathscr G(z)=z\cdot \mathscr G(z)+1\qquad (1)$$ 其意义是，扔了一次之后，要么结束要么不结束，$\mathscr G$ 右移一位可以看作是 $g_{i-1}$ 。同时还有 $$\mathscr G(z)\cdot \Pr(A[1...n])=\sum_{i=1}^n \mathscr{F}(z)\cdot \Pr(A[i+1...n])\cdot \zeta(i)\qquad (2)$$ 其意义是，考虑在现在的串后面接一个可以让这个过程直接结束的串，也就是接一个 $A$，$\Pr(s[1...n])$ 表示串 $s$ 出现的概率，那么可以知道等式左边的含义是「一定可以结束」；等式右边则是考虑可能会存在没有加满 $n$ 个、只加了前 $i$ 个字符就结束的情况，多乘一个 $\Pr(A[i+1...n])$ 本身是没有意义的，只是为了构造出等式，可以理解为两边都钦定扔了 $n$ 次——发现这种情况要是想要出现，就必须满足 $A[1...i]$ 是 $A$ 的一个 $\sf border$ ，所以 $\zeta(i)=[A[1...i]\in\mathbf{Border}]$ . 之后考虑如何消元。首先对 $(1)$ 式求导可以得到 $$\dfrac{\mathrm{d}}{\mathrm{d} z}\mathscr{F}(z)+\dfrac{\mathrm{d}}{\mathrm{d} z}\mathscr{G}(z)=\dfrac{\mathrm{d}}{\mathrm{d} z}\mathscr{G}(z)\cdot z+\mathscr{G}(z)\cdot 1$$ 也就是可以知道 $$\dfrac{\mathrm{d}}{\mathrm{d} z}\mathscr{F}(z)=\mathscr{G}(z)$$ 同时对于 $(2)$ 式，将 $z=1$ 代入可以得到 $$\mathscr{G}(1)\cdot \Pr(A[1...n]) =\sum_{i=1}^n\mathscr{F}(1)\cdot \zeta(i)\cdot \Pr(A[i+1...n])$$ 因为 $\mathscr{F}(1)=1$ ，所以可以得到 $$\mathscr{G}(1)=\dfrac{\sum_{i=1}^n \zeta(i)\cdot \Pr(A[i+1...n])}{\Pr(A[1...n])}$$ 然后根据 $$E(X)=\dfrac{\mathrm{d}}{\mathrm{d} z}\mathscr{F}(1)$$ 发现这题就做完了。复杂度线性。 但是注意本题要求以既约分数的形式保留精确值。因为我好久好久没写过高精度了，于是就想借此机会封装一个模板。然后…然后就写了快 $7h+$。注意到由于要求既约分数，所以要写高精度gcd，写法可以借鉴 `[SDOI2009]Super GCD` ，同时还要写高精除高精，个人没有找到什么好方法，于是就写的二分，复杂度大概是 $L^2\log V$ 的样子。 然后复杂度似乎是 $n\cdot L^2\log V$ ，并不可以过，于是考虑剪枝+卡常： 0、…高精度压位是必要的吧？这边我选择压 $8$ 位，因为发现 $10^3\cdot 10^{16}$ 恰好卡到了 `long long` 的上界。 1、发现二分时左右边界可以缩短很多，即 $l,r$ 都至多和 $V / \gcd$ 的长度相差 $1$ ，所以可以用这个来确定边界。亲测可以快大概 $6$ 倍左右(但是还是 T，极限数据大概要跑 $4s+$) 。 2、发现计算答案时，展开后存在很多公因式。于是可以提取公因式之后再计算。亲测可以快 $4$ 倍左右。 然后…大概就过了。中间写了很久的原因在于，我本来想尝试 FFT，后来发现自己没有封装好的 FFT…囧…写了半天发现自己 FFT 的常数还不如压位快…然后就没有然后了。 于是最后代码 $11k$ 左右…如果想的话可以去[这里](https://www.luogu.com.cn/blog/pks-LOVING/dai-ma-cun-dang)获取代码。