ARC156 B 题解

原题链接：https://atcoder.jp/contests/arc156/tasks/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;
}

声明