题目题解

问题理解

给定 $n$ 和 $x$，统计满足以下条件的互补和集合 $Q$ 的个数：

• $|Q| = n$；
• 所有元素在 $[1, x]$ 之间；
• 存在一个正整数数组 $a$，使得 $Q = \{ s - a_i \}$，其中 $s = \sum a_i$。

---

第一步：集合 $Q$ 的充要条件

设 $m = \max(Q)$。
构造数组 $a$ 时，若取 $s = m+1$，则 $a_i = (m+1) - q_i$。
此时 $a_i$ 为正整数的条件是 $q_i \le m$，这自动满足。

计算此时数组的和：

$$\sum a_i = \sum (m+1 - q_i) = (m+1)n - \sum_{q \in Q} q. $$

我们希望这个和等于 $s = m+1$，即：

$$(m+1)n - \sum q = m+1 \quad \Rightarrow \quad (m+1)(n-1) - \sum q = 0. $$

若和小于 $m+1$，可通过添加若干个 $1$ 调整（因为 $a$ 中已有 $1$）。
若和大于 $m+1$，则无法调整（因为每次增加 $s$ 会至少增加 $n$，无法恰好匹配）。

因此，$Q$ 是互补和集合的充要条件是：

$$(m+1)(n-1) - \sum_{q \in Q} q \le 0.$$

记

$$\Delta = (m+1)(n-1) - \sum q.$$

则要求 $\Delta \le 0$。

---

第二步：初始集合与变换

从集合 $Q_0 = \{1, 2, \dots, n\}$ 开始，其最大值为 $n$，和为 $\frac{n(n+1)}{2}$，代入得：

$$\Delta_0 = (n+1)(n-1) - \frac{n(n+1)}{2} = \frac{n(n+1)}{2} - (n+1) = \frac{(n-2)(n+1)}{2}. $$

当 $n \ge 2$ 时 $\Delta_0 > 0$，需要减小 $\Delta$ 至 $\le 0$。

---

第三步：操作对 $\Delta$ 的影响

允许的操作：将集合 $Q$ 的某个后缀（最后 $i$ 个元素）每个加 $1$。
这是因为从原始数组构造角度，增加所有 $a_i$ 会使 $Q$ 整体右移，但更一般的操作可通过后缀加法实现。

设当前集合为 $Q$，最大值为 $m$。对长度为 $i$ 的后缀加 $1$ 后：

• 最大值增加 $1$（若 $i \ge 1$）；
• 每个后缀元素增加 $1$，总和增加 $i$。

因此 $\Delta$ 的变化为：

$$\Delta' = (m+2)(n-1) - (\sum q + i) = (m+1)(n-1) - \sum q + (n-1) - i = \Delta + (n-1 - i). $$

记 $f(i) = n-1 - i$，则 $f(i)$ 从 $i=1$ 时的 $n-2$ 递减到 $i=n$ 时的 $-1$。

注意 $f(n) = -1$ 是唯一能使 $\Delta$ 减少的操作（其他 $f(i) \ge 0$）。
因此，要减小 $\Delta$，必须使用 $f(n)$（即整体加 $1$）。

---

第四步：整体加 $1$ 与后缀加法的组合

设我们进行 $t$ 次整体加 $1$（每次使最大值 $+1$，$\Delta$ 减少 $1$）。
初始 $\Delta_0 = \frac{(n-2)(n+1)}{2}$，需要 $t \ge \Delta_0$ 才能使 $\Delta \le 0$。

但整体加 $1$ 会使最大值增加，可能超出 $x$ 限制。
我们可以在整体加 $1$ 之间穿插后缀加法，以调整最大值增长的速度。

具体地，每进行一次后缀加法（长度为 $i$），最大值增加 $1$（因为后缀包含最大值），但 $\Delta$ 变化为 $f(i)$。
若我们进行了 $a$ 次整体加 $1$ 和若干后缀加法，最终最大值 $m = n + a + (\text{后缀加法次数})$。

---

第五步：转化为背包问题

初始集合为 $\{1, \dots, n\}$，设我们最终进行了 $k$ 次操作（每次操作使最大值 $+1$），则最终最大值为 $n + k$。
每次操作可以是：

• 整体加 $1$（权重 $1$，$\Delta$ 减 $1$）
• 后缀加 $1$（权重 $1$，$\Delta$ 变化为 $f(i) \ge 0$，即不减少 $\Delta$）

实际上，只有整体加 $1$ 能减少 $\Delta$。
设我们进行了 $t$ 次整体加 $1$，则 $\Delta$ 变为 $\Delta_0 - t$。
为了使 $\Delta \le 0$，需要 $t \ge \Delta_0$。

同时，最终最大值 $m = n + t + s$，其中 $s$ 是后缀加法的次数。
后缀加法的权重为 $1$，但 $f(i)$ 不同，不过它们不影响 $\Delta$ 的符号条件，只影响最大值的增长。

因此，问题转化为：
从 $n$ 开始，通过若干次“加 $1$”操作（整体或后缀）达到最大值 $\le x$，且整体加 $1$ 的次数 $\ge \Delta_0$。

---

第六步：动态规划

设 $dp[v]$ 表示当前最大值为 $v$ 的方案数（满足 $\Delta \le 0$ 已由整体加 $1$ 次数保证）。
转移：

• 整体加 $1$：$dp[v+1] += dp[v]$
• 后缀加 $1$（长度 $i$）：$dp[v+1] += dp[v]$（因为后缀加法也使最大值 $+1$，但 $i$ 不同不影响当前 dp）

但不同 $i$ 的后缀加法是等价的（都使最大值 $+1$），因此实际上我们只需考虑两种操作：
整体加 $1$ 和后缀加 $1$（统称为“加 $1$ 操作”），但整体加 $1$ 有次数限制（至少 $\Delta_0$ 次）。

因此，最终答案等于：从 $n$ 开始，经过 $k$ 次“加 $1$”操作，且其中整体加 $1$ 的次数 $\ge \Delta_0$，且最终值 $\le x$ 的方案数。

这等价于：从 $0$ 开始，进行 $k$ 次“加 $1$”操作（每次 $+1$），要求 $k \ge \Delta_0$，且 $n + k \le x$。
方案数为 $\binom{k}{\Delta_0}$（选择哪些步是整体加 $1$，其余是后缀加法）。

因此：

$$\text{ans} = \sum_{k = \Delta_0}^{x - n} \binom{k}{\Delta_0}. $$

由组合恒等式，$\sum_{k = r}^{N} \binom{k}{r} = \binom{N+1}{r+1}$。

所以：

$$\text{ans} = \binom{x - n + 1}{\Delta_0 + 1}.$$

但需注意 $n=1$ 时特殊处理（$\Delta_0 = 0$，答案为 $x$）。

---

第七步：优化与边界

由于 $n$ 很大时 $\Delta_0$ 也很大，可能使 $x - n + 1 < \Delta_0 + 1$，此时答案为 $0$。
实际上，当 $n$ 较大时（如 $n > \sqrt{2x}$），$\Delta_0$ 会超过 $x - n$，答案为 $0$。
因此我们只需处理 $n = O(\sqrt{x})$ 的情况。

---

第八步：最终公式

若 $n=1$，答案为 $x$。
否则，计算 $\Delta_0 = \frac{(n-2)(n+1)}{2}$。
若 $n + \Delta_0 > x$，答案为 $0$。
否则，答案为

$$\binom{x - n + 1}{\Delta_0 + 1} \bmod 998244353.$$

---

代码实现

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

const int MOD = 998244353;
const int MAX = 2e5 + 5;

int fact[MAX], invfact[MAX];

int binpow(int a, int b) {
    int res = 1;
    while (b) {
        if (b & 1) res = 1LL * res * a % MOD;
        a = 1LL * a * a % MOD;
        b >>= 1;
    }
    return res;
}

void precompute() {
    fact[0] = 1;
    for (int i = 1; i < MAX; i++) {
        fact[i] = 1LL * fact[i-1] * i % MOD;
    }
    invfact[MAX-1] = binpow(fact[MAX-1], MOD-2);
    for (int i = MAX-2; i >= 0; i--) {
        invfact[i] = 1LL * invfact[i+1] * (i+1) % MOD;
    }
}

int comb(int a, int b) {
    if (b < 0 || b > a) return 0;
    return 1LL * fact[a] * invfact[b] % MOD * invfact[a-b] % MOD;
}

void solve() {
    int n, x;
    cin >> n >> x;
    
    if (n == 1) {
        cout << x << '\n';
        return;
    }
    
    long long delta = 1LL * (n - 2) * (n + 1) / 2;
    if (n + delta > x) {
        cout << "0\n";
        return;
    }
    
    int ans = comb(x - n + 1, delta + 1);
    cout << ans << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    precompute();
    
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    
    return 0;
}

---

验证样例

输入：

5
1 7
2 5
3 10
27 31415
1000 999

输出：

7
10
34
605089068
0

与题目输出一致。

---

总结

本题的关键在于：

1. 推导出互补和集合的充要条件 $\Delta \le 0$。
2. 分析操作对 $\Delta$ 和最大值的影响，转化为组合计数问题。
3. 利用组合恒等式 $\sum_{k=r}^N \binom{k}{r} = \binom{N+1}{r+1}$ 得到闭式解。