ARC花式掉分
# 题面
数轴上从左到右给出 $n+1$ 个不重叠的点 $x_0,x_1,\cdots,x_n$；另有 $n$ 个动点 $y_0,y_1,\cdots,y_{n-1}$，其中 $\forall i,y_i\in(x_i,x_{i+1})$。
若每个 $y_i$ 落在其取值范围内的每个位置概率相等，求「动点两两之间的最小距离」的期望，对 $998244353$ 取模。
数据规模 $1\le n\le20$。
# 解析
看到求最小距离可能会先想到 min-max 反演 转化成最大距离（虽然我连这个都没有想到），但是这个想法是不可行的。
点击展开/折叠 此题「min-max反演」的误区
由题意，设 $n$ 个动点的点集为 $\mathbb{P}$，相当于求 $$ E\Big(\min_{i,j\in \mathbb{P}}\{|x_i-x_j|\}\Big) $$
似乎由 min-max 反演，结合期望线性性可得下式：
$$ \sum_{\mathbb{S}\subset\mathbb{P}}(-1)^{|\mathbb{P}|-|\mathbb{S}|}E\Big(\max_{i,j\in\mathbb{S}}\{x_i-x_j\}\Big) $$
进而一个点集的最远点距只与左右两个点有关，于是可以快速地计算。但是看一眼 $n$ 的范围，感觉哪里不对……但是哪里不对？
再观察一下 min-max 反演的式子：
$$ \min_{x\in \mathbb{S}}\{x\}=\sum_{\mathbb{T}\subset\mathbb{S}}(-1)^{|\mathbb{S}|-|\mathbb{T}|}\max_{x\in\mathbb{T}}\{x\} $$
其实上述做法的误区在于「集合」，这里求 min 的集合并不是点集 $\mathbb{P}$，而是点对集 $\{(i,j)\mid i,j\in\mathbb{P}\}$。于是枚举的子集也应该是点对集的子集，而枚举点对集的子集并不能简化问题。
转化成相邻两点的最小距离。设相邻两点的最小距离为 $t$，则下式成立：
点击折叠/展开「关于上式」
可以从离散随机变量的期望计算式不严谨地证明上式，若离散随机变量 $X$ 满足其取值只可能是正数，则
$$ E(X)=\sum_{i=1}iP(X=i) $$
则必有 $E(x)=\sum_{i=1}P(x\ge i)$。从代数角度容易证明，而直观也比较好理解——$P(x=i)$ 对期望的贡献系数为 $i$，将系数 $i$ 均摊到 $1\sim i$ 上，每个位置分摊 $1$ 的系数。
而若是连续随机变量（取值一定非负），我们仍有
$$ E(X)=\int_{0}^{+\infty}iP(X=i)\rm{d}i $$
依然考虑把 $P(X=i)$ 的系数 $i$ 均摊，那么既然是连续的，就要把系数分摊到区间 $(1,i)$ 上，每 $\rm di$ 分摊 $\rm di$ 的系数，得到结论。
先不考虑别的，假如给定最小距离 $d$，应该如何求解 $P(t\ge d)$？
根据题意，有下式：
那么设 $y’_i=y_i-it$，则有 $y’_{i+1}\ge y_i’$，$y_i’\in\big(x_i-it,x_{i+1}-it\big)$。
这一步转化非常重要。
但是由于变量是连续的，我们不可能直接决策每个变量的具体的值，而是决定每个变量落在哪个范围内。
$n$ 对形如 $x_i-it,x_{i+1}-it$ 的点将 $y’_i$ 可能存在的区间划分成 $2n-1$ 段。我们把这 $2n-1$ 个段依次编号为 $0\sim 2n-2$，可以预先求得 $y_i’$ 可能落在的段的编号范围，记为 $[l_i,r_i]$。
然后我们就可以设计一个 DP —— $f(i,j,k)$ 表示 $y_i’$ 落在第 $j$ 段内，此时第 $j$ 段中已有 $k$ 个变量。
那么 $y_i’$ 要么和 $y_{i-1}’$ 落在同一个段内，要么落在之后的段内。
考虑由 $f(i-1,j,k)$ 转移到下一个值：
- 若 $y_i’$ 与 $y_{i-1}’$ 落在同一个段：则先前落在段 $j$ 内的点把第 $j$ 段划分成 $k+1$ 小段，而 $y_i’$ 只能落在最后一小段，因此概率除以 $k+1$，再乘上 $y_i’$ 落在第 $j$ 段的概率 $P(i,j)$，则
- 若 $y_i’$ 落在之后的段中
令段 $j$ 的长度为 $L_j$，$y’_i$ 可能的取值范围长度为 $D_i$；那么 $P(i,j)=\frac{L_j}{D_i}$。我们发现 $D_i$ 是一个常值，而 $L_j$ 是关于 $t$ 的一个一次多项式。
第二种转移可以前缀和优化，于是可以在 $O(n^3R)$ 的复杂度内完成整个DP，$R$ 是单次转移的复杂度。
于是可以推得 $f(n-1,j,k)$ 是关于 $t$ 的 $n$ 次多项式。单词转移要么是对多项式乘以一个常数，要么是一个一次多项式与另一个多项式相乘，那么单次转移复杂度 $R=n$。
所以 DP 的复杂度为 $O(n^4)$。
再看看怎么求答案，不可能直接枚举 $t$，那么一定也是 $t$ 的一个取值范围一起计算答案。由于我们可以 DP 求得 $f(n,j,k)$ 关于 $t$ 的多项式，如果知道 $t$ 的对应范围，就可以通过定积分求解期望。
不难注意到，只要 $2n$ 个点 $x_i-it,x_{i+1}-it$ 的大小顺序不变，则最后得到的 $f(n-1,j,k)$ 关于 $t$ 的表达式就不会变。
所以对每一种点的顺序，都要计算一次 DP。
最后一个问题，一共有多少种点的顺序？答案是 $O(n^2)$。注意到点的平移速度不同，但对于同一个点，其平移速度是常数，所以最初靠后的点 $A$ 平移超过最初靠前的一个点 $B$ 后（$A$ 的平移速度大于 $B$），$A$ 就一直在 $B$ 前面。只会发生 $O(n^2)$ 次点的相对位置变化。
# 源代码
点击展开/折叠代码
1 | /*Lucky_Glass*/ |