题解：P12394 「RiOI-6」神曲

Watersphere · 2025-05-01 19:47:33 · 题解

本题解为 O(nm) 做法的组合意义证明。

考虑依次在数轴上填入二元组，因为后填包含先填的限制，每填一个就相当于把 [l_i,r_i] 内所有点缩为一个。

对于每个 v，设 f_{i,j} 表示填入了前 i 个二元组，剩余 j 个点的方案数。

如果当前填入的长度为 len(len \le j) 则有 j-len+1 种不同的填法，并且将 j 缩为 j-len+1 个点。

即 f_{i,j} \times (j-len+1) \to f_{i+1,j-len+1}

考虑这个式子的意义，即选择一个长度为 n 的不增序列，满足值域 \in [1,v]，权值为元素的乘积。

考虑倒过来做，即选择不减序列，设 g_{i,j} 表示选了 i 个元素，最大值为 j。

有 g_{i,j}=g_{i,j-1}+g_{i-1,j}\times j。

对于 v 答案即为 g_{n,v}。

移位一下就是是第二类斯特林数的转移式子了。