专栏文章

题解：CF2125E Sets of Complementary Sums

22huk
CF2125E题解参与者 2已保存评论 4

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
4 条
当前快照
1 份
快照标识符
@mioqh9lq
此快照首次捕获于
2025/12/02 23:29
3 个月前
此快照最后确认于
2025/12/02 23:29
3 个月前
查看原文
如果将 QQ 中的数从小到大排序，临位作差得到查分数组，那么不难发现对 aa 进行如下操作，QQ 的差分数组是不变的：
  • 将 aa 的所有值都增加或减少同一个数；
  • 在 aa 最后添加一个已经出现过的数。
因为这两种操作的本质都是将 QQ 整体增加或减少同一个数。不妨将从 aa 开始进行多次这样操作后得到的新数组 a′a' 都归为一个等价类。换言之，一个等价类的 aa 所对应的 QQ 的查分数组是相同的。（话说等价类是这个意思吗 QwQ）
如果要用某个 aa 代表这个等价类，这个 aa 一定会满足：
  • 最小值为 11；
  • 没有重复元素。
如果最小值不为 11，我们可以将 aa 整体减 min⁡{a}−1\min\{a\}-1。如果有重复元素，可以视作从没有重复元素的 aa 不断扩展而来。
用这样的 aa 代表整个等价类的另一个好处是，可以方便刻画「QQ 大小为 nn」和「QQ 中最大值不超过 xx」这两个条件。即：
  • ∣a∣=n|a|=n；
  • (∑ai)−1≤x(\sum a_i) - 1 \le x，即 ∑ai≤x+1\sum a_i \le x + 1。
另一个问题是，一个等价类中的 aa 所对应的 QQ 的差分数组是相同的，不代表 QQ 是相同的。
这样考虑，从那个基本的 aa（有 11 且无重复元素）开始，每次在最后添加一个 11，就能使 QQ 的最大值增大 11。初始 QQ 中最大值为 (∑ai)−1(\sum a_i)-1，最终 QQ 的最大值为 xx。所以一个等价类中的 aa 所对应的 QQ 的数量为 x−((∑ai)−1)+1x - ((\sum a_i)-1)+1。
也就是说，对于最终答案的计算，我们并不需要得知 a1,a2,…,ana_1,a_2,\dots,a_n 的具体值，而是只需要确定 ∑ai\sum a_i。于是考虑将「和」放进 DP 状态中并统计方案数。
另外这个「aa 中有 11」不太好刻画。一个比较偷懒的解决方式是，我们将 aa 整体减一并把 00 去掉，这个 00 就是刚才的 11。然后 aa 的长度变为 n−1n-1，总和减少了 nn。这些都是定值是极其方便的。
然后 DP。设 f(n,s)f(n,s) 表示满足以下条件的 aa 的数量：
  • ∣a∣=n|a|=n；
  • ∑ai=s\sum a_i = s；
  • 1≤a1<a2<⋯<an1 \le a_1 < a_2 < \dots < a_n。
注意到，初始令 a=∅a=\varnothing，进行若干次下面任一操作后，一定可以得到满足「1≤a1<a2<⋯<an1 \le a_1 < a_2 < \dots < a_n」的 aa：
  • 将 aa 全部加一；
  • 将 aa 全部加一，接着在 aa 开头添加一个 11。
相对应的可以得到转移方程：
f(n,s)=f(n,s−n)+f(n−1,s−n)f(n,s) = f(n,s-n) + f(n-1,s-n)
同时注意到 s≥n(n+1)2s \ge \dfrac{n(n+1)}2，且 s≤2×105s \le 2 \times 10^5，所以 DP 第一维是根号级别的。这样复杂度就对了。
最后因为神秘原因需要特判一下 n=1n = 1。
CPP
#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;
}

评论

共 4 条评论，欢迎与作者交流。

正在加载评论...