自动搬运

查看原文

来自洛谷，原作者为

	皎月半洒花 在那之前，你要多想。

搬运于2025-08-24 21:47:50，当前版本为作者最后更新于2020-05-04 16:42:22，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

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