CF1603E - A Perfect Problem

· · 题解

题意：

定义一个可重集是好的，当且仅当集合中最大值 x，最小值 y，总和 s 满足 x\times y\ge s。

定义一个序列是完美的，当且仅当这个序列每一个子序列构成的可重集是好的。

求长度为 n，值域为 [1,n+1] 的序列中，好的序列的个数，对 M 取模。

这题很厉害，需要先发现若干个性质：

  1. 将序列排序之后，区间的限制一定比子序列严格，所以只需要考虑区间的限制。

  2. 前缀的限制是最严格的。

    考虑一个区间，将左端点左移，那么最小值会变小，和会变大，限制更严格。所以原序列完美等价于每一个前缀是好的。

  3. 记前 $i$ 个数的和为 $s_i$。由于 $s_k\ge k\times a_1$，如果 $a_k<k$，那么 $k\times a_1>a_k\times a_1$，于是有 $s_k>a_k\times a_1$，不合法。

  4. 若 a_k=k，则 \forall i<k,a_i=k。

    由于合法条件 s_{k}\le a_k\times a_1=k\times a_1，也就是 \sum_{i\le k}a_i\le k\times a_1，移项得到 \sum_{i\le k}(a_1-a_i)\ge 0，由于有序，所以 a_i=a_1=a_k=k。

  5. 若 a_n=n+1，a_{[1,n]} 是好的，且存在 a_{k}\ge k + 1，则 a_{[1,k]} 是好的。

由性质 4 得到，若 a_k=k，则 a_1=k。所以满足 a_{k}=k 的至多只有一个位置（不一定存在），即 a_1。

其余的都满足 a_k\ge k+1，故由性质 5 得到只要 a_n=n+1 且 a_{[1,n]} 是好的，这些前缀就都是好的。注意到这些条件包含了所有 a_n=n+1 的情况，对于 a_n=n 的情况很平凡，由性质 4 可以得到 a_n=n 的序列。

所以可以利用性质进行 DP，这个序列满足（只考虑了 a_n=n+1 的情况）：

为了简洁可以将 a_i 全部减去 a_1，记作 b

可以将第二个限制和第一个限制改写成：所有 b_i 在 [0,n+1-a_1] 之间，且满足至少存在 i(1\le i\le n-a_1) 个数满足 b_k\ge n+2-i-a_1。

设 f_{i,s,k} 表示考虑了填入 n+1-a_1 到 i 中的数，和为 s，现在放置了 k 个数的方案数。状态数是 O(n^3) 的，转移枚举 i 填入的次数 j，均摊是调和级数，所以总复杂度是 O(n^3\log n) 的。但是枚举 a_1 还需要 O(n)，怎么办？

实际上第二个约束非常严格，很多情况是无解的。具体来说，设 t=n-a_1，则第二个限制中，这些数的和至少为 \max_{i=1}^{t}i(t+2-i)，这是一个二次函数的形式，容易解得最大值在 i=\frac{t+2}{2} 取得。这个值是 \frac{(t+2)^2}{4}，如果 a_1 取得太小，那么这个值就会大于 n，使得无解。当 a_1 小于 n-2\sqrt{n} 时是必然无解的，但是实际上可以直接判断上述最大值，可以跑得更快。

于是总复杂度变为 O(n^{3}\sqrt{n}\log n)。但是我并不知道这个界是否是紧的。

My Submission

如果有错误请指出。