牛客挑战赛43 B-集合操作

集合操作

分析

• 简化：S 中小于 x 的元素不超过 m 个 = 集合中以1开头的公差为1的数列的最长长度小于等于m
• 解释：假设这个集合里没有1，那么肯定存在一种情况，删去1能使这个集合合法。于是我们的目
  标转为——求以1为开头公差为1的长度小于等于m的数列个数（有点长，注意断句）。通过直接
  枚举数列的长度i，那么剩下的数的组合就是C(n,n-i)，用一个变量求和即可

代码

#include<bits/stdc++.h>

#define ll long long

using namespace std;

const int N=1e5+10;
const ll mod=998244353;

ll n,m,ans;
ll p[N]={1};

inline ll get(ll a,ll b)
{
    ll res=1;
    for (;b;b>>=1,a=a*a%mod)
        if(b&1) res=res*a%mod;

    return res;
}

int main()
{
    scanf("%lld%lld",&n,&m);
    for (ll i=1;i<=n;i++) p[i]=p[i-1]*i%mod;
    ll ans=0;
    for (int i=0;i<=m+1;i++)
        ans=(ans+p[n]*get(p[i],mod-2)%mod*get(p[n-i],mod-2)%mod)%mod;
    printf("%lld\n",ans);
    return 0;
}