集合操作
分析
- 简化: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;
}