NC211969 集合操作

zrzring 2020-10-14 PM 28℃ 0条

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

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

将$1$到$n$的排列分成两个集合$A = \{a_i\}$,$B = \{b_i\}$,对于每个元素$a_i$,都最多有$m$个$b_i < a_i$,求划分方案数

考虑枚举$B$集合的大小$i$,为了满足条件,$i \leq m$时可以选择任意的数放入,$i > m$时只能在从$1$到$i - 1$里选择$m$个

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

评论


您还没有登录呦


登录 注册
Title - Artist
0:00