P12394 「RiOI-6」神曲题解 最后更新于 2025-05-02 00:52:53

前情，Ri 在题解中设 $f_{n,m}$ 为答案，运用了特别复杂的证明证明过程（我认为去做泰勒展开还是太人类智慧了）证明。 我们沿用这个设置，但是使用不一样的证明。 思路也与另一位使用组合意义证明的大佬略有不同。 首先，如果不知道 $f_{n,m}=S(n+m,m)$（其中 $S$ 为第二类斯特林数，那么不易证明（或许需要极强的观察能力）） 但是直接求证的话就不需要观察力了。 方法 1：沿用我赛时的思路（数学归纳法）进行证明 这样的结构等价于将区间组织成层次化的森林： - 每个层次中的区间互不相交。 - 较高层次的区间包含较低层次的所有区间。 设 $f(n, V)$ 表示长度为 $n$、值域为 $V$ 的合法序列数。 我们容易发现有两种操作。 1. 新建一个根区间： - 该区间覆盖整个值域 $[1, V]$。 - 剩下的 $n-1$ 个区间必须被包含在此根区间内，形成子结构。 - 对应递推项：$f(n-1, V-1)$（值域缩小为 $V-1$，因为根已占据 $[1, V]$）。 2. 将第 $n$ 个区间插入现有结构： - 选择一个现有层次 $k$（共 $V$ 种选择），将新区间插入该层次。 - 该层次内的区间必须保持互不相交。 - 对应递推项：$V \cdot f(n-1, V)$（保持值域 $V$）。 故 $f$ 递推关系为： $$ f(n, V) = f(n-1, V-1) + V \cdot f(n-1, V). $$ tips：由于对斯特林数及其不敏感导致我赛时推导到了这里没发现结论。 第二类斯特林数 $S(N, K)$ 的递推关系为： $$ S(N, K) = S(N-1, K-1) + K \cdot S(N-1, K). $$ 其组合意义是将 $N$ 个元素划分为 $K$ 个非空子集的方式数。 观察发现，$f(n, V)$ 的递推式与 $S(n+V, V)$ 的递推式完全一致： - $S(n+V, V) = S(n+V-1, V-1) + V \cdot S(n+V-1, V)$. 1. 当 $n=0$ 时： - 空序列唯一存在，故 $f(0, V) = 1$。 - $S(V, V) = 1$（每个元素单独成子集），满足 $f(0, V) = S(0+V, V)$. 2. 当 $V=1$ 时： - 所有区间必须是 $[1,1]$，只有一种方式，故 $f(n, 1) = 1$。 - $S(n+1, 1) = 1$（所有元素放在一个子集），满足 $f(n,1) = S(n+1,1)$. 假设对所有 $m < n$ 和 $k \leq V$，有 $f(m, k) = S(m+k, k)$。 对于 $f(n, V)$，根据递推关系： $$ f(n, V) = f(n-1, V-1) + V \cdot f(n-1, V). $$ 由归纳假设： $$ f(n, V) = S(n-1 + (V-1), V-1) + V \cdot S(n-1 + V, V) = S(n+V-1, V-1) + V \cdot S(n+V-1, V). $$ 这正是 $S(n+V, V)$ 的递推式，故 $f(n, V) = S(n+V, V)$。 --- 方法 2：稍加思考可以发现也可以利用双射证明（组合意义） 我们可以通过构造一个显式的双射来证明，满足条件的区间序列与将 $n + V$ 个元素划分为 $V$ 个非空子集的方案一一对应。 我们需要构造长度为 $n$ 的区间序列，满足： - 每个区间 $[l_i, r_i]$ 满足 $1 \leq l_i \leq r_i \leq V$。 - 对于任意 $i < j$，要么 $[l_i, r_i]$ 被 $[l_j, r_j]$ 完全包含，要么两区间不相交。 将区间序列的构造过程映射到元素划分过程： - 元素定义：将 $n$ 个区间和 $V$ 个特殊标记（对应值域中的位置 - 如何划分：将这 $n + V$ 个元素划分为 $V$ 个非空子集，每个子集对应值域中的一个位置 $j \in \{1, 2, \dots, V\}$。 每个子集 $S_j$ 对应值域位置 $j$，并满足以下条件： 1. 特殊标记唯一性：每个子集 $S_j$ 必须包含且仅包含一个特殊标记（位置 $j$）。 2. 分配：区间元素被分配到子集 $S_j$，表示该区间的右端点为 $j$，即 $r_i = j$。 3. 约束：子集 $S_j$ 中的区间必须满足： - 所有区间的右端点固定为 $j$。 - 左端点 $l_i \leq j$。 - 按顺序插入时，要么被包含在已有的某个区间中（形成嵌套），要么不相交（成为新的根区间）。 - 特殊标记的分配：$V$ 个特殊标记固定占据每个子集的一个位置，确保子集非空。 - 区间的分配：将 $n$ 个区间分配到 $V$ 个子集，每个子集 $S_j$ 可包含任意多个区间，但需满足右端点为 $j$。 - 斯特林数的意义：第二类斯特林数 $S(n + V, V)$ 恰好统计了将 $n + V$ 个元素划分为 $V$ 个非空子集的方式，其中 $V$ 个特殊标记强制每个子集非空。 验证双射： - 唯一性：每个子集 $S_j$ 中的区间右端点为 $j$，且特殊标记 $j$ 唯一标识该子集。 - 合法性：子集内的区间满足嵌套或不相交的条件： - 若一个区间被分配到 $S_j$，其右端点固定为 $j$，左端点可自由选择（共 $j$ 种可能）。 - 这等价于将 $n$ 个区间分配到 $V$ 个子集，每个子集对应一个右端点，且子集非空（必须包含特殊标记）。 --- 这种方法虽然可以推导出结论，但是过于人类智慧了，在不知道结论的前提下需要及其强大的注意力（ 接下来不难发现原问题被转换为求第二类斯特林数对角线和。 对于这玩意我的第一反应就是生成函数，然后用卷积 `ntt` 之类的去优化，但是稍加推导就会发现闭合式又臭又长。 （悬赏生成函数做法，30R） 对于每个 $m$ 需要求： $$ \frac{(n+m)!}{m!} [x_n](\frac{e^x-1}{x})^m $$ 我个人认为用 bostan-mori 可以卡过去，可以考虑用一些常规的卡常方法加上[这篇文章的方法](https://www.luogu.com.cn/article/tphid0th)。