AT_arc156_b 题解

· · 题解

这道题其实不难。

我们先把原先 A 集合去重。

然后，我们观察最终集合 A 的情况。

先定义 m 表示后来加入的数中最大的值，cnt_i 表示最终集合 A 中的数字 i 的数量。

我们发现，最终集合需要满足对于任意的整数 x\in[0, m]，cnt_x \ge 1。因为如果存在整数 x\in[0, m]，cnt_x = 0，那么无论如何，加入集合 A 的数都不可能超过 x，要超过 x 需要先把 x 填好。

因此，我们可以枚举 m 的值。

对于当前的 m，我们统计出原先 A 集合中小于等于 m 的数字个数，然后再加上 K，即为最终 A 集合 \sum\limits_{i = 0}^{m}cnt_i 的值。

我们可以发现，只要满足 3 段前说明的条件，那么最终的 A 一定是合法的，我们已经对 A 集合去重了，那么每一个 x\in[0, m] 可以取到的最小值就是 1。我们使用插板法计算可能的结果数。

设 W = \sum\limits_{i = 0}^{m}cnt_i，那么一共有 W - 1 个空，需要插 m 个板子。对于当前 m，答案就是 \tbinom{W - 1}{m}。

需要注意的是，如果对于某个 m，原集合 A 中存在 m + 1，那么 cnt_{m + 1} = 1，m 的贡献已经在 m + 1 中统计过了。所以不需要统计这个 m。

代码：

#include<bits/stdc++.h>
#define int long long // 开 long long 是为了防止取模前爆 int
using namespace std;
const int N = 400005, P = 998244353; // 数据范围及模数
int n, k; // 原集合 A 的元素数量及操作个数
bool f[N]; // 标记某数是否存在于原集合
int sum = 0;  // 当前枚举到的 m 对应的 W 值 
int ans = 0;  // 答案
int frac[N];  // 阶乘数组
int ksm(int a, int n) { // 快速幂
    if(n == 0) return 1;
    if(n == 1) return a % P; 
    int d = ksm(a, n / 2);
    d = d * d % P;
    if(n & 1) d = d * a % P;
    return d;
}
int inv(int a) {  // 逆元
    return ksm(a, P - 2); // 不会的可以去看 OI wiki 乘法逆元
}
int C(int n, int m) { // 组合数
    return frac[n] * inv(frac[n - m]) % P * inv(frac[m]) % P; // 计算组合数
}
signed main() {
    cin >> n >> k;
    frac[0] = 1;
    for(int i = 1; i <= n + k; i ++) frac[i] = frac[i - 1] * i % P;
    for(int i = 1; i <= n; i ++) {
        int a;
        cin >> a;
        f[a] = 1; // 标记 a 存在于原集合 A
    }
    sum = k;
    for(int i = 0; ; i ++) {
        if(f[i]) sum ++;  // 修改当前的 M 值
        if(sum < i) break; // 无法满足条件
        if(f[i + 1]) continue;  // 无需统计
        ans += C(sum - 1, i); // 将贡献加入答案
        ans %= P; // 对 P 取模
    }
    printf("%d\n", ans); // 输出答案
    return 0;
}