本文共 858 字，大约阅读时间需要 2 分钟。

快要被自己菜哭了

不管怎么算都会有重复

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

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

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

这样一定是不重不漏

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

#include 
   
    using namespace std;#define int long longconst 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)
    
     >=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;}
    
   

转载地址：https://issue-is-vegetable.blog.csdn.net/article/details/110185499 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！