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

。

代码：

CPP

#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;
}

文章操作

相关推荐

评论

AT_arc156_b 题解