Codeforces 1477F. Nezzar and Chocolate Bars

好题！ (opens new window)

题意：你有一条长为 $L$ 的线段，初始时线段上已经有 $n - 1$ 个分割点将其划分为 $n$ 段，其中第 $i$ 段长为 $l_{i}$ 。每次在 $[0, L]$ 中随机一个实数 $r$ ，在线段上加入坐标为 $r$ 的分割点，直到所有分割点将线段分割为每段长度不超过 $K$ 的若干段。求新加入的分割点个数的期望。模 $998244353$ 。

$n \leq 50, L, K \leq 2000$

题解：

令生成函数 $f$ 对应的指数生成函数为 $\tilde{f}$ 。

首先考虑 $n = 1$ 的情况。假设第 $i$ 步及以内能够结束的概率为 $p_{i}$ ，那么答案为 $\sum_{i \geq 0} (1 - p_{i})$ 。考虑如何计算 $p_{i}$ 。

显然，第 $n$ 步及以内可以结束等价于无论是否达到要求强行做到第 $n$ 步，此时符合要求。考虑每一步的随机都是独立的，那么随机生成的坐标点列 $(z_{1}, z_{2}, \dots, z_{n})$ 是均匀分布在 $Ω_{L} = {(z_{1}, z_{2}, \dots, z_{n}) | 0 \leq z_{i} \leq L, i = 1, 2, \dots, n}$ 中的，每一个特定的坐标点列 $(z_{1}, z_{2}, \dots, z_{n})$ 被生成的概率元为：

\frac{d z}{\int \dots \int_{Ω_{L}} d z} = \frac{d z}{L^{n}}

但从 $(z_{1}, z_{2}, \dots, z_{n})$ 中无法很好地分析是否满足 $\leq K$ 的要求，考虑对该空间进行转化。在 $Ω_{L}$ 中的点坐标几乎都是两两不同的，将其排序，转化为 $({\hat{z}}_{1}, {\hat{z}}_{2}, \dots, {\hat{z}}_{n})$ ，其中 $0 \leq {\hat{z}}_{1} \leq {\hat{z}}_{2} \leq \dots \leq {\hat{z}}_{n} \leq L$ ，令 ${\hat{Ω}}_{L} = {({\hat{z}}_{1}, {\hat{z}}_{2}, \dots, {\hat{z}}_{n}) | 0 \leq {\hat{z}}_{1} \leq {\hat{z}}_{2} \leq \dots \leq {\hat{z}}_{n} \leq L}$ ，则 ${\hat{Ω}}_{L}$ 中的每个点几乎都对应 $n!$ 个 $Ω_{L}$ 中的点，于是每个 ${\hat{Ω}}_{L}$ 中的点的概率元为 $\frac{n! d z}{L^{n}}$ 。

为了判断是否满足要求，进一步将 $({\hat{z}}_{1}, {\hat{z}}_{2}, \dots, {\hat{z}}_{n})$ 唯一对应到其差分数组 $({\hat{z}}_{1}, {\hat{z}}_{2} - {\hat{z}}_{1}, \dots, {\hat{z}}_{n} - {\hat{z}}_{n - 1})$ ，均匀分布在空间 ${\tilde{Ω}}_{L} = {({\tilde{z}}_{1}, {\tilde{z}}_{2}, \dots, {\tilde{z}}_{n}) | {\tilde{z}}_{i} \geq 0, \sum_{i = 1}^{n} {\tilde{z}}_{i} \leq L}$ 中，每个点的概率元仍然为 $\frac{n! d z}{L^{n}}$ 。顺便说明，这证明了 $\int \dots \int_{{\tilde{Ω}}_{L}} d z = \frac{L^{n}}{n!}$ 。

于是在 ${\tilde{Ω}}_{L}$ 中， $({\tilde{z}}_{1}, {\tilde{z}}_{2}, \dots, {\tilde{z}}_{n})$ 符合要求等价于 $0 \leq {\tilde{z}}_{i} \leq K, i = 1, 2, \dots, n$ 且 $0 \leq L - \sum_{i = 1}^{n} z_{i} \leq K$ ，于是我们有符合要求的概率等于 $Ω_{K} \cap ({\tilde{Ω}}_{L} ∖ {\tilde{Ω}}_{L - K})$ 中的点的概率元的和，即：

p_{n} = \int \dots \int_{Ω_{K} \cap ({\tilde{Ω}}_{L} ∖ {\tilde{Ω}}_{L - K})} \frac{n! d z}{L^{n}} = \frac{n!}{L^{n}} (\int \dots \int_{Ω_{K} \cap {\tilde{Ω}}_{L}} d z - \int \dots \int_{Ω_{K} \cap {\tilde{Ω}}_{L - K}} d z)

现在关注如何求出 $\int \dots \int_{Ω_{A} \cap {\tilde{Ω}}_{B}} d z$ ，定义可重集 $Φ_{A, S} = {(z_{1}, z_{2}, \dots, z_{n}) | z_{i} \geq A, i \in S, z_{i} \geq 0, i \notin S}$ 。

容斥 $Ω_{A}$ 中 $z_{t} \leq A$ 的限制，就可以将 $Ω_{A}$ 几乎完全地用若干个 $Φ_{A, S}$ 表示出来（除若干边界上的点以外）：

Ω_{A} = \sum_{S \subseteq {1, 2, \dots, n}} (- 1)^{| S |} Φ_{A, S}

于是：

\int \dots \int_{Ω_{A} \cap {\tilde{Ω}}_{B}} d z = \sum_{S \subseteq {1, 2, \dots, n}} (- 1)^{| S |} \int \dots \int_{Φ_{A, S} \cap {\tilde{Ω}}_{B}} d z

而对于 $Φ_{A, S} \cap {\tilde{Ω}}_{B}$ 中的点 $(z_{1}, z_{2}, \dots, z_{n})$ ，可以将满足 $i \in S$ 的 $z_{i}$ 减去 $A$ ，从而与 ${\tilde{Ω}}_{B - | S | A}$ 中的点一一对应，于是 $Φ_{A, S} \cap {\tilde{Ω}}_{B}$ 与 ${\tilde{Ω}}_{B - | S | A}$ 的积分相等，由前文证明的结论可以得到：

\int \dots \int_{Ω_{A} \cap {\tilde{Ω}}_{B}} d z = \sum_{S \subseteq {1, 2, \dots, n}} (- 1)^{| S |} \int \dots \int_{{\tilde{Ω}}_{B - | S | A}} d z

= \sum_{i = 0}^{n} (- 1)^{i} (\binom{n}{i}) \int \dots \int_{{\tilde{Ω}}_{B - i A}} d z = \sum_{i = 0}^{⌊ \frac{B}{A} ⌋} (- 1)^{i} (\binom{n}{i}) \frac{(B - i A)^{n}}{n!}

回代到 $p_{n}$ 的表达式中，可以得到：

p_{n} = \frac{n!}{L^{n}} (\sum_{i = 0}^{⌊ \frac{L}{K} ⌋} (- 1)^{i} (\binom{n}{i}) \frac{(L - i K)^{n}}{n!} - \sum_{i = 0}^{⌊ \frac{L}{K} ⌋ - 1} (- 1)^{i} (\binom{n}{i}) \frac{(L - (i + 1) K)^{n}}{n!})

= \sum_{i = 0}^{⌊ \frac{L}{K} ⌋} (- 1)^{i} (\binom{n}{i}) (1 - i \frac{K}{L})^{n} + \sum_{i = 1}^{⌊ \frac{L}{K} ⌋} (- 1)^{i} (\binom{n}{i - 1}) (1 - i \frac{K}{L})^{n}

= 1 + \sum_{i = 1}^{⌊ \frac{L}{K} ⌋} (- 1)^{i} (\binom{n + 1}{i}) (1 - i \frac{K}{L})^{n}

于是没有初始分割点的答案就为 $\sum_{i \geq 0} \sum_{j = 1}^{⌊ \frac{L}{K} ⌋} (- 1)^{j + 1} (\binom{i + 1}{j}) (1 - j \frac{K}{L})^{i}$ ，下面考虑存在初始分割点的情况。

定义 $q_{i, j} = 1 + \sum_{k = 1}^{⌊ \frac{l_{i}}{K} ⌋} (- 1)^{k} (\binom{j + 1}{k}) (1 - k \frac{K}{l_{i}})^{j}$ ， $Q_{i} = \sum_{k \geq 0} q_{i, k} (\frac{l_{i}}{L})^{k} x^{k}$ ， $p_{i}$ 仍然如上定义， $P = \sum_{k \geq 0} p_{k} x^{k}$ ，则此时 $p_{i}$ 的值为：

p_{i} = \sum_{k_{1} + k_{2} + \dots + k_{n} = i} (\binom{i}{k_{1}, k_{2}, \dots, k_{n}}) \prod_{j = 1}^{n} (\frac{l_{j}}{L})^{k_{j}} q_{j, k_{j}}

\frac{p_{i}}{i!} = \sum_{k_{1} + k_{2} + \dots + k_{n} = i} \prod_{j = 1}^{n} \frac{(\frac{l_{j}}{L})^{k_{j}} q_{j, k_{j}}}{k_{j}!}

即：

\tilde{P} = \prod_{i = 1}^{n} {\tilde{Q}}_{i}

我们要求的答案是 $\sum_{k \geq 0} (1 - k! [x^{k}] \tilde{P}) = \sum_{k \geq 0} k! [x^{k}] (e^{x} - \tilde{P})$ ，那么首先考虑 ${\tilde{Q}}_{i}$ 的表达式：

{\tilde{Q}}_{i} = \sum_{j \geq 0} \frac{1}{j!} (1 + \sum_{k = 1}^{⌊ \frac{l_{i}}{K} ⌋} (- 1)^{k} (\binom{j + 1}{k}) (1 - k \frac{K}{l_{i}})^{j}) (\frac{l_{i}}{L})^{j} x^{j}

= \sum_{j \geq 0} \frac{1}{j!} (\frac{l_{i}}{L})^{j} x^{j} + \sum_{j \geq 0} \frac{1}{j!} \sum_{k = 1}^{⌊ \frac{l_{i}}{K} ⌋} (- 1)^{k} (\binom{j + 1}{k}) (\frac{l_{i} - k K}{L})^{j} x^{j}

= e^{\frac{l_{i}}{L} x} + \sum_{j \geq 0} \sum_{k = 1}^{min {j + 1, ⌊ \frac{l_{i}}{K} ⌋}} (- 1)^{k} \frac{j + 1}{k! (j + 1 - k)!} (\frac{l_{i} - k K}{L})^{j} x^{j}

= e^{\frac{l_{i}}{L} x} + \sum_{j \geq 0} \sum_{k = 1}^{min {j + 1, ⌊ \frac{l_{i}}{K} ⌋}} (- 1)^{k} \frac{j + 1 - k + k}{k! (j + 1 - k)!} (\frac{l_{i} - k K}{L})^{j} x^{j}

= e^{\frac{l_{i}}{L} x} + \sum_{j \geq 0} \sum_{k = 1}^{min {j, ⌊ \frac{l_{i}}{K} ⌋}} (- 1)^{k} \frac{1}{k! (j - k)!} (\frac{l_{i} - k K}{L})^{j} x^{j} + \sum_{j \geq 0} \sum_{k = 1}^{min {j + 1, ⌊ \frac{l_{i}}{K} ⌋}} (- 1)^{k} \frac{1}{(k - 1)! (j + 1 - k)!} (\frac{l_{i} - k K}{L})^{j} x^{j}

= e^{\frac{l_{i}}{L} x} + \sum_{k = 1}^{⌊ \frac{l_{i}}{K} ⌋} \frac{(- 1)^{k}}{k!} \sum_{j \geq k} \frac{(\frac{l_{i} - k K}{L})^{j}}{(j - k)!} x^{j} + \sum_{k = 1}^{⌊ \frac{l_{i}}{K} ⌋} \frac{(- 1)^{k}}{(k - 1)!} \sum_{j \geq k - 1} \frac{(\frac{l_{i} - k K}{L})^{j}}{(j - (k - 1))!} x^{j}

= e^{\frac{l_{i}}{L} x} + \sum_{k = 1}^{⌊ \frac{l_{i}}{K} ⌋} \frac{(- 1)^{k} (\frac{l_{i} - k K}{L})^{k} x^{k}}{k!} \sum_{j \geq 0} \frac{(\frac{l_{i} - k K}{L})^{j}}{j!} x^{j} + \sum_{k = 1}^{⌊ \frac{l_{i}}{K} ⌋} \frac{(- 1)^{k} (\frac{l_{i} - k K}{L})^{k - 1} x^{k - 1}}{(k - 1)!} \sum_{j \geq 0} \frac{(\frac{l_{i} - k K}{L})^{j}}{j!} x^{j}

= e^{\frac{l_{i}}{L} x} + \sum_{k = 1}^{⌊ \frac{l_{i}}{K} ⌋} \frac{(- 1)^{k} (\frac{l_{i} - k K}{L})^{k} x^{k}}{k!} e^{(\frac{l_{i} - k K}{L}) x} + \sum_{k = 1}^{⌊ \frac{l_{i}}{K} ⌋} \frac{(- 1)^{k} (\frac{l_{i} - k K}{L})^{k - 1} x^{k - 1}}{(k - 1)!} e^{(\frac{l_{i} - k K}{L}) x}

= e^{\frac{l_{i}}{L} x} (1 + \sum_{k = 1}^{⌊ \frac{l_{i}}{K} ⌋} \frac{(- 1)^{k} (\frac{l_{i} - k K}{L})^{k}}{k!} x^{k} e^{- k \frac{K}{L} x} + \sum_{k = 1}^{⌊ \frac{l_{i}}{K} ⌋} \frac{(- 1)^{k} (\frac{l_{i} - k K}{L})^{k - 1}}{(k - 1)!} x^{k - 1} e^{- k \frac{K}{L} x})

括号外的部分全部相乘，即为 $e^{x}$ ，考虑括号内的部分，可以发现相乘之后可以表示为若干项 $x^{k - j} e^{- k \frac{K}{L} x}$ 的线性组合，于是可以利用以 $j, k$ 为下标的二维卷积计算每一项的系数，就得到了 $e^{x} - \tilde{P}$ 的一个以若干项 $x^{k} e^{C x}$ 的线性组合表示的表达式。

最后，只需要考虑如何计算 $\sum_{i \geq 0} i! [x^{i}] (x^{k} e^{C x})$ 即可。考虑：

\sum_{i \geq 0} i! [x^{i}] (x^{k} e^{C x}) = \sum_{i \geq 0} (i + k)! \frac{C^{i}}{i!} = k! \sum_{i \geq 0} (\binom{i + k}{i}) C^{i}

令 $F_{k} = \sum_{i \geq 0} (\binom{i + k}{i}) C^{i}$ ，于是：

F_{k} = \sum_{i \geq 0} (\binom{i + k}{i}) C^{i} = \sum_{i \geq 0} ((\binom{i + k - 1}{i - 1}) + (\binom{i + k - 1}{i})) C^{i}

= \sum_{i \geq 1} (\binom{i - 1 + k}{i - 1}) C^{i} + \sum_{i \geq 0} (\binom{i + k - 1}{i}) C^{i}

= C \cdot F_{k} + F_{k - 1}

又 $F_{0} = \frac{1}{1 - C}$ ，于是 $F_{k} = \frac{1}{(1 - C)^{k + 1}}$ ，有 $\sum_{i \geq 0} i! [x^{i}] (x^{k} e^{C x}) = \frac{k!}{(1 - C)^{k + 1}}$ 。

利用前文的分析，用分治 $F F T$ 计算二维卷积，可以在 $O (n L \log n L)$ 的时间内解决问题。最后记得处理边界条件，如 $K = l_{i}$ 的情况可能要令 $0^{0} = 0$ 。