这种题一般都需要用到容斥
因为操作可以改变顺序,原题就变成了
将到的排列分成两个集合,,对于每个元素,都最多有个,求划分方案数
考虑枚举集合的大小,为了满足条件,时可以选择任意的数放入,时只能在从到里选择个
#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; }