CF1479E School Clubs

· · 题解

CF1479E 题解

前置知识：鞅与停时定理

鞅

我们有一个随机过程 X_0,X_1, ...。如果 \forall n \in \mathbb N, \ E(Y_n) < \infty 且 \forall n \in \mathbb N^+, \ E(Y_{n + 1}|X_n,X_{n-1},...,X_0) = E(Y_n)，则我们称 Y_0, Y_1, ... 为该随机过程的鞅。

离散时间鞅

如果随机过程 X_0,X_1, ... 满足 \forall n \in \mathbb N, \ E(X_n) < \infty 且 \forall n \in \mathbb N^+, \ E(X_{n + 1}|X_n,X_{n-1},...,X_0) = E(X_n)，则我们称该随机过程为离散时间鞅。

即：已知之前所有的过程，之后的观察值的期望等于之前的观察值的期望

停时定理

对于一个随机过程，如果我们可以根据之前的过程判断该过程是否已经停止（即不用知道未来的过程），则他的停时为一个随机变量 \tau。

如果满足下列几个条件之一，则我们有 E(X_\tau) = X_0。

注意，这里由于 \tau 不是一个定值，所以和前面说的离散时间鞅的定义不同。

读者自证不难

OI里面怎么用

有随机过程 A_0, A_1, ...，考虑构造势能函数 \phi。要求 E(\phi(A_{t+1}) - \phi(A_t) | A_t, A_{t-1}, ..., A_0) = -1。

则我们构造随机过程 X_t = \phi(A_t) + t，易证 X_0, X_1, ... 为离散时间鞅。

停时定理，E(X_\tau) = X_0 即 E(\phi(A_\tau) + \tau) = \phi(A_0)，则 E(\tau) = \phi(A_0) - \phi(A_\tau)。

CF1479E School Clubs

Statement

有 n 个学生和 m 个组，每个人在一个组里面，第 i 个组的人数为 a_i。

现在，每天有一个学生（n 个学生中随机的一个）会生气，他会：

  1. 有一半的概率他会脱离这个组，并且成立一个新的组。
  2. 有一半的概率他会脱离这个组，并且进入一个已经成立的组。他进入第 i 个组的概率为 \frac {a_i} n，他可能会回到原来的组。

求第一次出现所有学生在同一个组的期望天数。

m \le 1000$，$n \le 4 \times 10^8

Sol

在这道题中，我们可以用一个可重集来描述状态，然后我们考虑如何设计 \phi。

由于不同组之间是独立的，所以我们可以分开计算其势能，即 \phi(A_t) = \sum _{a \in A_t} f(a)。

分类讨论

  1. 操作 1，有一个人离开了一个组，进入了一个新的组。则

    \phi(A_{t + 1}) = \phi(A_t) - f(a_x) + f(a_x - 1) + f(1)

  2. 操作 2，回到原来组。则

    \phi(A_{t + 1}) = \phi(A_t)

  3. 操作 2，没有回到原来组，则

    \phi(A_{t + 1}) = \phi(A_t) - f(a_x) + f(a_x - 1) - f(a_y) + f(a_y + 1)

综上

\begin{aligned} E(\phi(A_{t + 1})|A_t) &= \sum _{i = 1} ^m \dfrac {a_i} n \cdot \dfrac 1 2 \left( \phi(A_t) - f(a_i) + f(a_i - 1) + f(1) + \dfrac {a_i} n \phi(A_t) + \sum _{j = 1}^m [i\neq j] \dfrac {a_j} n \left(\phi(A_t) - f(a_i) + f(a_i-1) - f(a_j) + f(a_j+1)\right)\right) \\ &= \sum _{i = 1} ^m \dfrac {a_i} {2n} \left( 2\phi(A_t) + f(1) - \dfrac {2n - a_i} n f(a_i) + \dfrac {2n - a_i} n f(a_i - 1) + \sum _{j \neq i} (f(a_j+1) - f(a_j))\right) \\ &= \phi(A_t) + \dfrac 1 2 f(1) - \sum_i\dfrac {3na_i-2a_i^2}{2n^2} f(a_i) + \sum_i\dfrac {2na_i-a_i^2}{2n^2} f(a_i- 1) + \sum_i \dfrac {na_i - a_i^2} {2n^2} f(a_i + 1) \end{aligned}

根据势能函数需要满足的要求

E(\phi(A_{t+1})-\phi(A_t) | A_t, A_{t-1},...,A_0) = -1

所以

f(1) + 2 + \sum_i \dfrac{a_i}{n^2} (-(3n-2a_i)f(a_i)+(2n-a_i)f(a_i-1)+(n-a_i)f(a_i + 1)) = 0

由于 a_i=0 是不会产生贡献的（因为你永远不可能动他）所以相当于扔掉了，因此势能为 0，即 f(0) = 0。

因为我们关心的是势能的差，所以为了方便我们取 f(1)=-2，把常数项消掉。则

\sum_i \dfrac{a_i}{n^2} (-(3n-2a_i)f(a_i)+(2n-a_i)f(a_i-1)+(n-a_i)f(a_i + 1)) = 0 -(3n-2a)f(a)+(2n-a)f(a-1)+(n-a)f(a + 1) = 0

算法一

f(a+1) = \dfrac {(3n-2a)f(a)-(2n-a)f(a-1)} {n-a}

由于 E(A_\tau) = f(n)，所以 E(\tau) = E(A_0) - E(A_\tau) = \sum f(a_i) - f(n)。

线性暴力计算。

这个怎么能过？？？

CF 机子太快了！！1

算法二

刚才那个柿子也可以变成这样

(n-a)(f(a+1)-f(a)) = (2n-a)(f(a)-f(a-1))

则我们记 f(a) 的差分 g(a)=f(a+1)-f(a)，有

g(a) = \dfrac {2n-a}{n-a} g(a-1) = \prod _{i=1} ^a \dfrac {2n-i}{n-i} g(0)

而因为 f(0)=0，f(1)=-2，所以 g(1)=-2。

f(a) = \sum_{i=0}^{a-1} g(i)

然后就是考虑怎么求

S(a) = \sum _{i=1}^a \prod_{j=1}^i \dfrac {2n-j}{n-j}

有一个很巧妙的 trick。N 是一个比 a 大的数。令

s(a) = S(a) \cdot \prod_{i=1}^N (n-i)

考虑分块求解，块长 B = \sqrt N，则令

R(z) = \sum_{i=z+1}^{z+B} \left(\prod_{j=z+1}^i (2n-j)\prod_{j=i+1}^{z+B} (n-j)\right)

则

s(a) = \sum _{i=0}^{a/B} \left(\prod _{j=1}^{Bi} (2n-j)\cdot \prod_{j=Bi+B+1}^N (n-j)\cdot R(Bi)\right) + \sum_{i=(\lfloor a/B\rfloor+1)*B+1}^a \left(\prod _{j=1}^i (2n-j) \cdot \prod_{j=i+1}^N (n-j)\right)

接下来考虑如何计算。

对于 R(z)，首先 R(0) 是可以 O(\sqrt n) 计算的。

考虑递推

R(z) = R(z-1) \cdot \dfrac {n-(z+B)}{2n-z} + \prod_{i=z+1}^{z+B} (2n - i)- \prod_{i=z+1}^{z+B}(n - i)

求出 R(0) .. R(B) 之后我们进行插值，就可以得到多项式 R(z)。然后我们可以多点求值求出所有 R(Bi)。

对于剩余的部分，我们需要求的其实是一些 2n-x 或者 n-x 的前缀或者后缀积。

我们考虑如何求一个一次函数 F(x) 的前缀积。（后缀积不说了，因为可以很方便地转化成前缀积）

我们延续前面的分块的思想。记 D(z) = \prod _{i=z+1}^{z+B} F(i)。

注意到 D(z) 是一个关于 x 的 B 次多项式，所以我们延续前面求 R(z) 的想法，先求出 D(0) , D(1), \cdots, D(B) 然后插值、多点求值求出所有的 D(Bi)。

这么做的时间复杂度是 \mathcal O(\sqrt n(m + \log^2 N))。

算法三

快速插值和多点求值常数太大辣！！！

其实我们可以用“快速阶乘”的 trick 去掉一个 log。

首先我们有多项式 f(x) 和若干个点值 (x_i, f(x_i))。考虑拉格朗日插值的公式

f(x) = \sum_{i=1} ^m f(x_i) \prod _{j \ne i} \dfrac {x - x_j} {x_i - x_j}

在这个问题中 x_i 分别为 0 到 d。所以

f(x) = \sum_{i=0} ^d f(i) \prod _{j \ne i} \dfrac {x - j} {i - j}

考虑怎么求 f(d + k)，1 \le k \le t

\begin{aligned} f(d+k) &= \sum_{i=0} ^t f(i) \prod _{j \ne i} \dfrac {d + k - j} {i-j}\\ &= \prod _{j=0} ^t (d+k-j) \cdot \left(\sum_{i=0}^t \dfrac {(-1)^{t-i}f(i)}{i!(t-i)!} \cdot \dfrac 1 {d+k-i}\right) \end{aligned}

括号里面可以卷积计算：

F(x) = \sum _{i=0} ^t \dfrac {(-1)^{t-i}f(i)}{i!(t-i)!} x^i G(x) = \sum_{i=0}^{2t} \dfrac 1 {d-t+i} x^i

故

f(d+k) = \prod _{j=0} ^t (d+k-j) \cdot [x^{k+t}] F(x)G(x)

如果给出 f(0), f(B), f(2B), .. f(Bk)，要求 f(d), f(d+B), .., f(d+Bk)，则设 g(x) = f(Bx) 就可以解决。

接下来考虑如何求 R(z)。

R(z,B) = \sum_{i=z+1}^{z+B} \left(\prod_{j=z+1}^i (2n-j)\prod_{j=i+1}^{z+B} (n-j)\right) P(z, B) = \prod _{j = z + 1} ^{z + B} (2n - j) Q(z, B) = \prod _{j = z + 1} ^{z + B} (n - j)

那么我们要算的就是 P(0, B), P(s, B), ... , P(sB, B)，R, Q 同理。

如何递归计算？

R(z, 2B) = R(z,B)\cdot Q(z+B,B)+R(z+B,B) \cdot P(z,B) P(z, 2B) = P(z,B) \cdot P(z+B,B) Q(z, 2B) = Q(z, B) \cdot Q(z + B, B)

我们发现，我们需要计算的其实是：

那么我们使用前面给出的方法容易由第一组 $P$ 算出其他三组。 然后就可以使用倍增求解。时间复杂度 $T(k) = T(k / 2) + O(k \log k) = O(k \log k)$，其中 $k$ 为多项式的次数。 这种方法的时间复杂度是 $\mathcal O(\sqrt n(m + \log N))$，比算法二少了一个 log，常数也由显著提升（因为不用多点求值） ### 总结 这道题是一道好题。 对于求停时期望的问题，构造势能函数、使用停时定理是一种非常好的解决问题的方法。 算法一考察了选手胆大心细的能力以及对CF评测机的了解程度（bushi）。 算法二考察了对于一类多项式的类似阶乘的形式的问题，使用分块求解的方法。 算法三考察了对于拉格朗日插值公式的变形，在此类问题中把多点求值问题转化成标准的卷积性质的方法。 ### 代码 翻cf递交记录吧。