题解：CF2125E Sets of Complementary Sums

· · 题解

如果将 Q 中的数从小到大排序，临位作差得到查分数组，那么不难发现对 a 进行如下操作，Q 的差分数组是不变的：

因为这两种操作的本质都是将 Q 整体增加或减少同一个数。不妨将从 a 开始进行多次这样操作后得到的新数组 a' 都归为一个等价类。换言之，一个等价类的 a 所对应的 Q 的查分数组是相同的。（话说等价类是这个意思吗 QwQ）

如果要用某个 a 代表这个等价类，这个 a 一定会满足：

如果最小值不为 1，我们可以将 a 整体减 \min\{a\}-1。如果有重复元素，可以视作从没有重复元素的 a 不断扩展而来。

用这样的 a 代表整个等价类的另一个好处是，可以方便刻画「Q 大小为 n」和「Q 中最大值不超过 x」这两个条件。即：

另一个问题是，一个等价类中的 a 所对应的 Q 的差分数组是相同的，不代表 Q 是相同的。

这样考虑，从那个基本的 a（有 1 且无重复元素）开始，每次在最后添加一个 1，就能使 Q 的最大值增大 1。初始 Q 中最大值为 (\sum a_i)-1，最终 Q 的最大值为 x。所以一个等价类中的 a 所对应的 Q 的数量为 x - ((\sum a_i)-1)+1。

也就是说，对于最终答案的计算，我们并不需要得知 a_1,a_2,\dots,a_n 的具体值，而是只需要确定 \sum a_i。于是考虑将「和」放进 DP 状态中并统计方案数。

另外这个「a 中有 1」不太好刻画。一个比较偷懒的解决方式是，我们将 a 整体减一并把 0 去掉，这个 0 就是刚才的 1。然后 a 的长度变为 n-1，总和减少了 n。这些都是定值是极其方便的。

然后 DP。设 f(n,s) 表示满足以下条件的 a 的数量：

注意到，初始令 a=\varnothing，进行若干次下面任一操作后，一定可以得到满足「1 \le a_1 < a_2 < \dots < a_n」的 a：

相对应的可以得到转移方程：

f(n,s) = f(n,s-n) + f(n-1,s-n)

同时注意到 s \ge \dfrac{n(n+1)}2，且 s \le 2 \times 10^5，所以 DP 第一维是根号级别的。这样复杂度就对了。

最后因为神秘原因需要特判一下 n = 1。

#include <bits/stdc++.h>

using namespace std;

const int P = 998244353, N = 2e5 + 10, M = 800;

int f[M][N];
int n, x;

int dp(int n, int s) {
    if (n >= M || s < 0) return 0;
    return f[n][s];
}

int solve() {
    cin >> n >> x;
    if (n == 1) return x;
    int res = 0;
    for (int s = 1; s <= x + 1; ++ s ) {
        res = (res + 1ll * dp(n - 1, s - n) * (x - s + 2)) % P;
    }
    return res;
}

signed main() {
    f[0][0] = 1;
    for (int i = 1; i < M; ++ i )
        for (int j = i * (i + 1) / 2; j < N; ++ j ) {
            f[i][j] = (f[i][j - i] + f[i - 1][j - i]) % P;
        }

    int T;
    cin >> T;
    while (T -- ) cout << solve() << '\n';
    return 0;
}