[CF2125E] Sets of Complementary Sums

题目

CF2125E。

思路

对任意一个 $Q$，找到了对应的 $a_i$，设 $a_i$ 升序排序，根据题目的定义有：

1. $Q=\left\{\sum_{j=1}^m a_j -a_i\mid 1\le i\le m\right\}$，那么，有 $|Q|=|\left\{a_i\mid 1\le i\le m\right\}|$，即 $|Q|$ 是 $a$ 中互不相同的元素个数。
2. 若在 $a$ 中增加某个 $a_i$，会使得 $Q$ 的所有值增加 $a_i$；如果 $a_1=1$，显然可以把增加某个 $a_i$ 等价为增加 $a_i$ 次 $1$。
3. 如果 $a_1=1$，并且 $a_i\neq 1$ 重复出现，那么我们可以把那些重复的删掉，增加若干个 $1$ 使得 $Q$ 不变。

下面是本题最难以想到的地方：任给一个 $a$，我总能把它等价为 $a_1'=1$ 的 $a'$。

如果 $a_1>1$，那么令所有的 $a_i\gets a_i-(a_1-1)$，此时 $a$ 的相对大小并没有改变，我们看 $Q$ 中的某个元素：

$$\sum_{j=1}^m (a_j-(a_1-1))-(a_i-(a_1-1))=\sum_{j=1}^m a_j-a_i-(m-1)(a_1-1)$$

也就是说，所有的元素都减小了 $(m-1)(a_1-1)$，并且 $a_1=1$，运用第 $2$ 条性质，我们给 $a$ 的开头插入这么多个 $1$，就会使 $Q$ 不变。

同样，运用第 $3$ 条性质，可以使 $a$ 所有大于 $1$ 的元素唯一。

我们可以证明，如果 $Q$ 是 a set of complementary sums，一定有唯一的 $a'$ 满足 $a_1'=1$ 且所有 $a_i'>1$ 都唯一。

存在性：因为我们可以把任意的 $a$ 转化成这样，它既然存在一个 $a$，就一定有满足条件的 $a'$ 存在。

唯一性：假设存在两个不同的 $a,b$，那么可以分两种情况：

1. $a,b$ 去重后相同，那么就是 $1$ 的数量不同，而这是不可能的。不妨设 $b$ 中的 $1$ 更少，将 $b$ 插入若干个 $1$ 才能到达与 $a$ 相同的 $Q$，所以它们的 $Q$ 一定不相同，与假设矛盾。

2. $a,b$ 去重后不同，由于 $1$ 是一定存在的，并且去重后的长度也一定是 $|Q|$，所以只能是 $>1$ 的元素不同。

   又因为它们得到的 $Q$ 相同，两数组对应的最大的元素是 $s_a-1$ 和 $s_b-1$，它们一定相同，那么 $s_a=s_b$。

   那么 $Q_a=Q_b$ 就会有 $\{s_a-a_i\mid 1\le i\le m_a\}=\{s_b-b_i\mid 1\le i\le m_b\}$ 得到 $\{a_i\mid 1\le i\le m_a\}=\{b_i\mid 1\le i\le m_b\}$，这与 $a,b$ 去重后不同这一假设矛盾。

因此对 $Q$ 计数等价与对这样特殊的 $a$ 计数。

我们观察 $a$，它是由 $\ge 1$ 个 $1$ 和互不相同的 $\ge 2$ 的数升序构成的。我们可以先认为只有一个 $1$，得到一个 $Q$，然后，插入一个 $1$ 等价于把 $Q$ 的所有元素加 $1$，所以只要保证 $\max Q=\sum a_j - 1\le x$ 就是一个合法的方案。

具体地说，先考虑只有 $1$ 个 $1$ 的情况，设 $dp_{i,j}$ 表示考虑前 $i$ 个位置，数的和是 $j$ 的方案。

假设我们求出了 $dp_{n,j}$，答案是，$\sum_{j=(n+1)n/2}^{x+1}(x+1-j+1)dp_{n,j}$。

从这个式子可以观察到，如果答案不为 $0$，一定有 $\frac{n(n+1)}{2}\le x+1$，这可以得出 $n\le O(\sqrt x)$。

下面的问题就是，我们该如何求 $dp_{i,j}$？因为 $a$ 是递增的，这里有一个方法，枚举 $\Delta=a_i-a_{i-1}\ge 1$ 就可以了：

$$dp_{i,j}=\sum_{\Delta\ge 1} dp_{i-1,j-\Delta(n-i+1)}$$

为什么是 $j-\Delta(n-i+1)$？因为后续的 $(n-i+1)$ 个元素都会加上这个增量。

貌似是在某种背包 dp 中，有一种优化的思路，那就是：

$$dp_{i,j-(n-i+1)}=\sum_{\Delta\ge 1} dp_{i-1,j-(\Delta+1)(n-i+1)}$$

因此：

$$dp_{i,j}=dp_{i,j-(n-i+1)}+dp_{i-1,j-(n-i+1)}$$

这样复杂度就是 $O(nx)\le O(x\sqrt x)$ 了。

实现

这里用了滚动数组优化掉 $dp$ 的第一维。

#include <bits/stdc++.h>
using namespace std;

#define int long long
const int P = 998244353;

int solve() {
    int n, x;
    cin >> n >> x;
    if ((n+1)*n/2 > x+1) return 0;
    if (n == 1) return x;

    vector<int> pre(x+2);
    vector<int> now(x+2);
    pre[n] = 1;
    for (int i = 2; i <= n; i++) {
        for (int j = 0; j <= x+1; j++) {
            now[j] = 0;
            if (j - (n-i+1) >= 0) {
                now[j] = (pre[j - (n-i+1)] + now[j - (n-i+1)]) % P;
            }
        }
        pre.swap(now);
    }

    int ans = 0;
    for (int k = (1+n)*n/2; k <= x+1; k++) {
        ans = (ans + (x+1 - k + 1) * pre[k]) % P;
    }
    return ans;
}

signed main() {
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int T;
    cin >> T;
    while (T--) cout << solve() << '\n';
    return 0;
}