题解 P5606 【小K与毕业旅行】

· · 题解

我们称一对数可以匹配当且仅当两个数的乘积\le w

1(a_i \ge 0)

如果直接按照从小到达插入或从大到小插入很难处理，想办法构造一个插入顺序，使得任何位置 i 插入的数 a_i 满足以下条件之一：

如果有以上条件，我们考虑依照这个顺序插入，这个时候是一个经典的 dp 套路，设 f[i][j] 表示插入了前 i 个数，前 i 个数已经组成了 j 个连续段（指填入的数位置连续）的方案数。（这个套路的 dp 题很多，「JOI Open 2016」摩天大楼 是其中一例）

每次的转移有三种：

  1. 插入一个新的连续段
  2. 合并两个相邻连续段
  3. 一个连续段的两边延长

发现 A 类三种转移都能转移， B 类只能转移第一类。

这个 插入顺序 有很多种方法构造，在此叙述比较简单的一种：

排序之后考虑最小的数和最大的数，设为 a_1, a_n 。

如果a_1 * a_n \le w，则 a_n 与所有数都可以匹配，将它插入到当前插入顺序的头。

反之，则 a_1 与所有数都不能匹配，将它插入到当前插入顺序的头。

然后递归到子问题即可。

2

对 <0 的部分和 \ge 0 的部分分别跑上述 dp 因为小于 0 的段和 \ge 0 的段一定可以相邻，将 dp 的结果合并即可。

3(a_i\ge 0)

以上的插入顺序看起来并不能继续优化，考虑构造一个更优秀的插入顺序。

考虑把以上 插入顺序 reverse。

现在的性质是：

考虑插入的时候插在两个位置中间，与这两个位置相邻。

现在插入的时候有一些限制：

  2. 只能插入在两个 A类 之间。

考虑两个相邻的 A类 一定是可以匹配的，不会出现将一对不可以匹配的相邻数变成不相邻的情况。（这一结论保证了如此插入不会算漏）

仔细分析后还会发现：

每次插入 B类 之后会使得一个可以插入的位置变得没法插入，即空位-1

每次插入 A类 之后会使得一个可以插入的位置变成两个，即空位+1

于是可以在排序后 O(n) 的时间得到答案。

4

考虑事先硬点有多少段，即最开始给了多少空位。

如果最开始的空位个数是 x，可以看出最后的方案数是关于 x 的 n 次多项式。

这个多项式可以 分治FFT 求出。

我们要求出若干个 x 的答案，相当于求 f(1), f(2), \dots，这是一个多点求值。

注意到枚举的空位其实是最多多少段（可能有段最终仍然是空）。我们需要容斥。

这个容斥是一个卷积的形式，一次 FFT 即可。

综上我们即可在 O(n\log^2n) 的时间里求解了。

More

参考 @xgcxgc 的做法，最后的多点求值可以通过下降幂多项式优化，最终复杂度是分治下降幂多项式乘法的 O(N\log^2 N) 。由于常数更小，应该可以做更大一点的数据范围。