以「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 左右…如果想的话可以去这里获取代码。