CF 1420D. Rescue Nibel!(枚举点计算组合数)

传送门

快要被自己菜哭了

不管怎么算都会有重复

可以把所有区间的$2n$个点存下来枚举‘

按左端点顺序一条一条加入线段

对于每条线段,计算自己和前面的线段所有可能的组合

这样一定是不重不漏

遇到左端点加加,右端点减减,就可以动态维护目前有几条线段覆盖到了这个点

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int mod = 998244353;
const int maxn = 6e5+10;
int aabs(int x){ return x<0?-x:x;}
bool com(int a,int b)
{
	if( aabs(a)==aabs(b) )	return (a>b);//先处理左端点
	return aabs(a)<aabs(b); 
}
int st[maxn],top,ans,shu,fac[maxn],n,k;
int quick(int x,int n)
{
	int ans = 1;
	for( ; n ; n>>=1,x=x*x%mod )
		if( n&1 )	ans = ans*x%mod;
	return ans;
}
int C(int n,int m)
{
	return fac[n]*quick( fac[m]*fac[n-m]%mod,mod-2 )%mod;
}
signed main()
{
	cin >> n >> k;
	for(int i=1;i<=n;i++)
	{
		int l,r; scanf("%lld%lld",&l,&r);
		st[++top] = l, st[++top] = -r;
	}
	fac[0]=1;
	for(int i=1;i<=n;i++)	fac[i] = fac[i-1]*i%mod;
	sort( st+1,st+1+2*n,com );
	for(int i=1;i<=2*n;i++)
	{
		if( st[i]>0 )	shu++;
		else	shu--;
		if( st[i]>0&&shu>=k )	ans = ( ans+C(shu-1,k-1) )%mod;
	}
	cout << ans;
}