CF1603E - A Perfect Problem 题解

题意：

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

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

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

$n\le 200$

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

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

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

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

3. $a_k\ge k$。

   记前 $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]}$ 是好的。

   • $a_n\times a_1=(n+1)a_1\ge \sum_{i=1}^{n}a_i$，那么移项得到 $a_1\ge \sum_{i=1}^{n}(a_i-a_1)$，进一步放缩有，$a_1\ge \sum_{i=1}^{k}(a_i-a_1)$，移项回去得到 $(k+1)a_1\ge \sum_{i=1}^{k}a_i$，当 $a_k\ge k+1$ 时，此条件被满足。

由性质 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_1\le a_i\le n+1,1\le i\le a_1$
• $i+1\le a_i\le n+1,i>a_1$
• $a_n\times a_1=(n+1)a_1\ge \sum_{i=1}^{n}a_i$ 即 $a_1\ge \sum_{i=1}^{n}(a_i-a_1)$。

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

• $0\le b_i\le n+1-a_1,i\le a_1$
• $i+1-a_1\le b_i\le n+1-a_1,i>a_1$
• $\sum_{i=1}^{n}b_i\le a_1$

可以将第二个限制和第一个限制改写成：所有 $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

如果有错误请指出。