CF1603E - A Perfect Problem 题解

题意：

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

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

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

$n\le 200$

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

将序列排序之后，区间的限制一定比子序列严格，所以只需要考虑区间的限制。
前缀的限制是最严格的。
考虑一个区间，将左端点左移，那么最小值会变小，和会变大，限制更严格。所以原序列完美等价于每一个前缀是好的。
$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$ ，不合法。
若 $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$ 。
若 $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

如果有错误请指出。