题解 CF1420D 【Rescue Nibel!】
Karry5307
2020-09-26 07:45:27
### 题意
给定 $n$ 条线段，求出有多少种选出 $k$ 条的方法使得它们交集非空。
$\texttt{Data Range:}1\leq k\leq n\leq 3\times 10^5$
### 题解
本题是[这个题目](https://www.cnblogs.com/Karry5307/p/13617718.html)的弱化版。
~~所以 Rikka 可爱你们说对不对啊~~
注意到任意 $k$ 条线段的交集如果非空的话必定是一条线段，且这条线段的左端点一定是某条线段的左端点。
很明显先将线段离散化，然后去枚举相交的线段的左端点。
我们设 $p$ 是覆盖了某个位置的线段的数量，$s$ 是以这个位置为左端点的线段数量。由于我们选出的这 $k$ 条线段中至少要有一条以这个位置为左端点，所以容斥一下得到这个位置的答案为
$$\binom{p}{k}-\binom{p-s}{k}$$
注意到 $p$ 会在线段左端点和右端点 $+1$ 两个位置才会更新，所以需要在右端点也更新一次，注意到如果某个位置只有右端点的更新的话算出来的为 $0$，所以可以一并计算。
具体的实现方法就是开个桶就好了。
### 代码
```cpp
// This code is written by Karry5307
#include<bits/stdc++.h>
// Definition
#define For(i,x,y) for(register int i=(x);i<(y);i++)
#define Forr(i,x,y) for(register int i=(x);i<=(y);i++)
#define Rep(i,x,y) for(register int i=(x);i>(y);i--)
#define Repp(i,x,y) for(register int i=(x);i>=(y);i--)
#define ve vector
#define iter iterator
#define pb emplace_back
#define popb pop_back
#define all(x) x.begin(),x.end()
#define sz(x) (int)(x.size())
#define F first
#define S second
#define PY return (void)puts("Yes")
#define PN return (void)puts("Yes")
#define P0 return (void)puts("0")
#define P1 return (void)puts("-1")
using namespace std;
// Typedefs
typedef int ll;
typedef long long int li;
typedef unsigned int ul;
typedef unsigned long long int ull;
typedef double db;
typedef long double ldb;
typedef pair<ll,ll> pii;
typedef pair<li,li> pll;
const ll MAXN=6e5+51,MOD=998244353,inf=0x3f3f3f3f;
// Structures and variables
ll n,kk,tot,lst,sm,res;
ll l[MAXN],r[MAXN],u[MAXN],fact[MAXN],finv[MAXN],cntl[MAXN],cntr[MAXN];
// Fast IO
inline ll read()
{
register ll num=0,neg=1;
register char ch=getchar();
while(!isdigit(ch)&&ch!='-') ch=getchar();
if(ch=='-') neg=-1,ch=getchar();
while(isdigit(ch)) num=(num<<3)+(num<<1)+(ch-'0'),ch=getchar();
return neg==1?num:-num;
}
inline li readu()
{
register li num=0;
register char ch=getchar();
while(!isdigit(ch)) ch=getchar();
while(isdigit(ch)) num=(num<<3)+(num<<1)+(ch-'0'),ch=getchar();
return num;
}
template<class T>
inline void writep(T x)
{
if(x<0){return (void)putchar('-'),writep(-x);}
if(x<10){return (void)putchar(x|48);}
writep(x/10),putchar((x%10)|48);
}
template<class T>
inline void write(T x,char ch=' '){writep(x),putchar(ch);}
template<class T>
inline void writeln(T x){writep(x),putchar('\n');}
// chkmin and chkmax
template<class T>
inline void chkmax(T &x,const T &y){x=x>y?x:y;}
template<class T>
inline void chkmin(T &x,const T &y){x=x<y?x:y;}
// Functions
template<class T,class Compare>
inline void sort(ve<T>&v,Compare cmp=less<T>()){sort(all(v),cmp);}
template<class T>
inline void reverse(ve<T>&v){reverse(all(v));}
template<class T>
inline void clear(T *arr){memset(arr,0,sizeof(arr));}
template<class T>
inline void setInf(T *arr){memset(arr,0x3f,sizeof(arr));}
// Math funcs
inline ll qpow(ll base,ll exponent)
{
li res=1;
while(exponent)
{
if(exponent&1)
{
res=(li)res*base%MOD;
}
base=(li)base*base%MOD,exponent>>=1;
}
return res;
}
inline ll gcd(ll x,ll y)
{
return !y?x:gcd(y,x%y);
}
inline li lcm(ll x,ll y)
{
return x/gcd(x,y)*y;
}
// Functions
inline void setup(ll cnt)
{
fact[0]=fact[1]=finv[0]=1;
for(register int i=1;i<=cnt;i++)
{
fact[i]=(li)fact[i-1]*i%MOD;
}
finv[cnt]=qpow(fact[cnt],MOD-2);
for(register int i=cnt-1;i;i--)
{
finv[i]=(li)finv[i+1]*(i+1)%MOD;
}
}
inline ll binom(ll m,ll n)
{
if(m<0||n<0||m<n)
{
return 0;
}
return (li)fact[m]*finv[n]%MOD*finv[m-n]%MOD;
}
int main()
{
n=read(),kk=read(),setup(3e5+10);
for(register int i=1;i<=n;i++)
{
l[i]=read(),r[i]=read(),u[++tot]=l[i],u[++tot]=r[i];
}
sort(u+1,u+tot+1),tot=unique(u+1,u+tot+1)-u-1;
for(register int i=1;i<=n;i++)
{
l[i]=lower_bound(u+1,u+tot+1,l[i])-u,cntl[l[i]]++;
r[i]=lower_bound(u+1,u+tot+1,r[i])-u,cntr[r[i]+1]++;
}
for(register int i=1;i<=tot;i++)
{
lst=sm,sm+=cntl[i]-cntr[i];
res=((li)res+binom(sm,kk)-binom(lst-cntr[i],kk)+MOD)%MOD;
}
printf("%d\n",res);
}
```