笨蛋花的小窝qwq

笨蛋花的小窝qwq

“我要再和生活死磕几年。要么我就毁灭,要么我就注定铸就辉煌。如果有一天,你发现我在平庸面前低了头,请向我开炮。”

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

posted on 2020-05-04 16:42:22 | under 题解 |

大概是全网第一篇用 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$ 左右…如果想的话可以去这里获取代码。