自动搬运

查看原文

来自洛谷，原作者为

	jerome_wei **

搬运于2025-08-24 22:12:28，当前版本为作者最后更新于2019-10-28 23:19:54，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

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

1($a_i \ge 0$)

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

1. $\forall _{j<i},a_i *a_j \le w$，我们称满足这类数的为 $A$ 类
2. $\forall _{j<i},a_i *a_j > w$，我们称满足这类数的为 $B$ 类

如果有以上条件，我们考虑依照这个顺序插入，这个时候是一个经典的 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。

现在的性质是：

1. $\forall _{j>i}, a_i *a_j \le w$，我们称满足这类数的为 $A$类
2. $\forall _{j>i}, a_i *a_j > w$，我们称满足这类数的为 $B$类

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

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

1. $B$类 的旁边不可能再插入一个数。
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)$ 。由于常数更小，应该可以做更大一点的数据范围。