题解：P14381 【MX-S9-T4】「LAOI-16」顽疾

yyyx_ · 2025-11-02 18:59:59 · 题解

出题人题解。

定义 f(a) 为有多少个长为 n 排列 p 满足 \forall i\in[1,n),a_{p_i}\times a_{p_{i+1}}\le w。

定义 g(a) 为 \prod_{i=1}^{n-1} (a_{i+1}-a_i+1)^t。

求 \sum_{a\in A} f(a)\times g(a)，其中，A 为所有长度为 n，值域在 [1,k] 中且满足 \forall i\in[1,n-1],a_i\le a_{i+1} 的所有序列组成的集合。

首先，考虑如何快速计算一个数列 a 的 f(a)。我们可以定义一个最终的答案序列。然后，钦定一个选择顺序，每次选取一个 f(a) 中的数，将其插入到答案序列中。如果我们保证了每次插入后该数与相邻两项的乘积都小于等于 w，或者不合法的连续二元组之后会被分开，那么该序列就是合法的。

考虑我们从两边往中间放，对于现在要放的数 a_l,a_r。

如果 a_l\times a_r\le w，则有 \forall i\in[l+1,r],a_l\times a_i\le w，称其为 A 类点。放入后 l++。

如果 a_l\times a_r\ge w，则有 \forall i\in[l,r-1],a_i\times a_r\ge w，称其为 B 类点。放入后 r--。

所以对于放入过程，我们可以记录一个数 cnt 表示当前可以放入数的位置个数。

当放入一个 A 类点时，有 cnt 种放入方法，之后 cnt++。

当放入一个 B 类点时，有 cnt 种放入方法，之后 cnt--。

显然，如果存在一时刻满足 cnt=0，那么就无解。

考虑此题，可以 dp 求解，设 dp_{i,j,l,r} 表示当前已经放入了 i 个数，上述的 cnt=j，且两侧还没放的点的值分别为 l,r 时的答案，则转移时考虑枚举下一个放入的数 x，然后根据 j 进行转移。

时间复杂度 O(n^2k^3)。

考虑一个拆分幂次的办法，x^t 相当于有多少种方案是将 t 个互不相同的小球放入 x 个盒子中。

对于上述转移，可以用上述办法做到 O(n^2k^2t^2)。

注意到对于任意的两个数列 a,b，如果在数列 a 中存在两个值 v1,v2 满足 v1 先被插入到答案序列，则在 b 中如果也存在 v1,v2，则 v1 也会先被插入到答案序列中。

考虑反证法，如果 v1 在 a 中先被插入，但在 b 中 v2 先插入，则 v1,v2 必然作为不同类别（一个时 A 类，一个是 B 类）被考虑。

若 v1 作为 A 类点，则有 v1\times x\le w，其中 x\ge v2。而又有 v2\times y> w，其中 y\le v1。显然矛盾。

当 v1 作为 B 类点时，同理。

所以，可以预处理出一个全局的放入顺序。

之后，设 dp_{i,j,k,l,r} 表示已经考虑了钦定顺序的前 i 个数，当前已经放了 j 个数，可以放数的位置数为 k。而 l,r 为拆幂次优化转移时需要的两边放入的球的个数。转移时枚举放几个球。

时间复杂度为 O(n^2kt^3)。

还有 O(n^2kt^2) 做法等验题人或是其他选手来解答了 ~~，给你们精通数数的跪了~~ 。