NC211969 集合操作

更好的阅读体验

这种题一般都需要用到容斥

因为操作可以改变顺序，原题就变成了

将到的排列分成两个集合，，对于每个元素，都最多有个，求划分方案数

考虑枚举集合的大小，为了满足条件，时可以选择任意的数放入，时只能在从到里选择个

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <queue>

using namespace std;

const int N = 1e6 + 10, M = 2e6 + 10, inf = 0x3f3f3f3f, P = 998244353;

inline int read() {
    bool sym = 0; int res = 0; char ch = getchar();
    while (!isdigit(ch)) sym |= (ch == '-'), ch = getchar();
    while (isdigit(ch)) res = (res << 3) + (res << 1) + (ch ^ 48), ch = getchar();
    return sym ? -res : res;
}

int n, m, cnt, mul[N], inv[N];

int qpow(int a, int x) {
    int res = 1;
    while (x) {if (x & 1) res = 1ll * res * a % P; a = 1ll * a * a % P; x >>= 1;}
    return res;
}

int C(int m, int n) {
    if (m > n) return 0; if (m == 0 || n == m) return 1;
    return 1ll * mul[n] * inv[m] % P * inv[n - m] % P;
}

int main() {
    n = read(); m = read(); mul[0] = 1;
    for (int i = 1; i <= n; i++) mul[i] = 1ll * mul[i - 1] * i % P;
    inv[n] = qpow(mul[n], P - 2);
    for (int i = n; i >= 1; i--) inv[i - 1] = 1ll * inv[i] * i % P;
    int ans = 0;
    for (int i = 0; i <= m; i++) ans = (1ll * ans + C(i, n)) % P;
    for (int i = m + 1; i <= n; i++) ans = (1ll * ans + C(m, i - 1)) % P;
    printf("%d", ans);
    return 0;
}