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

出题人题解。

定义 $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)$ 做法等验题人或是其他选手来解答了 ，给你们精通数数的跪了 。