集合操作

题目描述
有一个集合 S，初始为 {1, 2, 3, \dots, n}{1,2,3,…,n}。
接下来会进行若干次操作，每次操作如下：
选择一个整数 x \in Sx∈S，满足 S 中小于 x 的元素不超过 m 个。然后在 S 中删除 x。
求出通过以上操作能够得到多少种不同的集合 S 。
答案对 998244353 取模。
思路:

1. 容易得出，所有的情况一共有 种。所以我们只需要求出不存在的情况有几种。
   不存在的情况:
   容易知道我们每一次可以从当前左边的m+1中选取一个。
   当我们减少0个数字的时候，右边n-m-1个只要有任意一个数字减少都是一种不存在的情况。这种情况就有 种。(-1的原因是因为他们全都存在，也就是不选的时候的情况)

当成功减少1个数字的时候，右边n-m-2个只要有任意一个数字减少都是一种不存在的情况。这种情况就有 (C(m+1,-1))代表的是成功删除掉一个数字的情况)

以此类推当成功减少2个数字的时候为
....

当右边数字为1个的时候停下，为1个的时候左边还剩下m个，总的个数为m+1，所有的情况都能得到
AC代码:

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
#define ll long long
#ifdef ONLINE_JUDGE
#else
#define scanf scanf_s
#endif // ONLINE_JUDGE
#define FOR(i,a,b) for(int i = a;i <= b;i++)
#define ROF(i,a,b) for(int i = a;i >= b;i--)
const ll mod = 998244353;
const int maxx = 1e5 + 10;
ll jc[maxx];
ll poww(ll a, ll b, ll mod) {
    ll base = 1;
    while (b) {
        if (b & 1) { base = base * a % mod; }
        b >>= 1; a = a * a % mod;
    }
    return base;
}
ll C(ll n, ll m) {
    if (m == 0) return 1;
    ll fenzi = jc[n];
    //ll fenmu = jc[n - m] * jc[m] % mod;
    return fenzi * poww(jc[n - m], mod - 2, mod) % mod * poww(jc[m], mod - 2, mod) %mod;
}
ll read() {
    ll X = 0, w = 1; char c = getchar();
    while (c < '0' || c>'9') { if (c == '-') w = -1; c = getchar(); }
    while (c >= '0' && c <= '9') X = X * 10 + c - '0', c = getchar();
    return X * w;
}
int main() {
    jc[0] = 1;
    ll n, m; n = read(), m = read();
    FOR(i, 1, n) jc[i] = jc[i - 1] * i % mod;
    ll total = poww(2, n, mod);
    ll less = 0;
    for (int r = n - m - 1,l = 0; r > 0; r--,l++) {
        less = (less + C(m + l, l) * (poww(2, r, mod) - 1) % mod) %mod;
    }
    cout << (total - less + mod) % mod<< endl;
}