CF2125E Sets of Complementary Sums 题解
这个计数题还是相当有意思的。
考虑如何判定集合 \(Q\) 是合法的，那么从序列 \(a\) 的角度进行判定。先钦定 \(a\) 互不相同，考虑序列 \(a\) 的和 \(s\)，那么大致能画成下图的形式：
\(x\) 表示实际上边界的纵坐标。那么现在的问题是如果这个东西合法，一定要有 \(x=s\)，但事实不一定如此，因此需要对某些 \(a_i\) 叠加使得其到达 \(s\)，但问题是 \(a_i\) 不一定能恰好增长到 \(x\)，这样的计数是失败的。但是当存在 \(a_i=1\) 时，对它不断叠加就一定能到达这个值。那能不能钦定对于每种 \(Q\)，一定有一个 \(a_i=1\) 参与 \(a\) 的构造呢？事实上是可以的。我们先不考虑 \(Q\) 的首项，对于 \(Q\) 的差分序列，也就是折线进行 dp，那么这样能够不重不漏地计算出 \(Q\) 差分序列的所有情况。现在考虑首项，由于有 \(a_i=1\)，因此有 \(Q_{\max}+1=s\) ，那么对于 dp 出的面积 \(s\)，上边界能取到的范围是 \([s,x+1]\)，因此最终要额外乘上 \(x-s+2\)。
那么现在考虑如何去做这个计数 dp。由于实际上我们不关心上边界取到多少，而钦定只能选 \(n\) 列，因此考虑一行一行地进行 dp，\(dp_{s,i}\) 表示现在的面积是 \(s\)，走到第 \(i\) 列的方案数，转移容易做到 \(O(1)\)。复杂度看上去是假的，但是实际上有 \(n\times(n+1)\le x\)，因此实际的复杂度是 \(O(x\sqrt x)\)，是真的。
多说一嘴为什么不能一列一列去 dp，因为这样做的话有 \(a\) 单调的限制，不仅要记录当前在哪一列还要记录当前的下边界以防转移到不合法的情形，状态数是假的；而一行一行 dp 的好处在于不管是哪一行，对于第 \(i\) 列，加进去贡献时一定是 \(n-i\)，而这个东西天然是单调的，相当于去掉了一维限制。这个故事告诉我们刻画限制后如果从一个方向/维度难以做，不妨换一个方向/思路去做。
代码很简单：
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5, mod = 998244353;
inline void add(int &x, int y) {x = x + y >= mod ? x + y - mod : x + y;
}
int T;
int n, x;
int dp[2][N];
void solve() {cin >> n >> x;if (n == 1) return cout << x << "\n", void();if (1ll * n * (n + 1) / 2 > x + 1) return cout << "0\n", void();int o = 0;dp[o][n] = 1;for (int i = n - 1; i; --i) {o ^= 1;for (int j = 0; j <= x + 2; j++) dp[o][j] = 0;for (int s = n; s <= x + 1; s++) {add(dp[o][s], dp[o][s - i]);add(dp[o][s], dp[o ^ 1][s - i]);}}int ans = 0;for (int i = n; i <= x + 1; i++) add(ans, 1ll * dp[o][i] * (x - i + 2) % mod), dp[0][i] = dp[1][i] = 0;cout << ans << '\n';
}int main() {ios::sync_with_stdio(0);cin.tie(0);cin >> T;while (T--) solve();return 0;
}