Codeforce 1420 D. Rescue Nibel! 解析(思維、組合、離散化、差分)

今天我們來看看CF1420D
題目連結

題目
給你$n$個區間，求有幾種方法使得$k$個區間的交集非空。

前言

組合不會算，也想不到離散化

想法

首先需要找個依據來枚舉開始計算，而我們可以觀察到:對於任何一個$k$個區間的交集，這個交集的左界一定是某個區間的左界，也就是說我們可以枚舉交集所有可能的左界，把答案加總即可。
而假設要計算交集從$i$開始的方法數，我們必須知道究竟有多少個區間有包含這個左界，但是$l_i,r_i\le10^9$實在太大了，即使我們做差分也時間不夠，因此我們需要離散化整個座標軸。

差分即是:$cnt[左界]++,cnt[右界+1]–$，如此一來只要把整個$cnt$數列做前綴和，其結果就是每個點被覆蓋的次數。

離散化:我們先把所有$l_i,r_i$丟進一個$vector$裡，並且只留下相異元素、排序，如此一來某原始座標$x$的離散化後的座標即是$lower_bound(vector_{start},vector_{end},x)$。

我們還需要紀錄:對於每一個座標，有多少左界從這開始。
如此一來，我們只要遍歷所有座標點，答案加上:(覆蓋的區間中選$k$個的方法數$-$沒選到從當前座標開始的區間的方法數)，就可以算出答案。

而還有一個難點即是計算組合數。我們可以先愈處理所有$x!$的數值和模反元素(計算模反元素可以用Fermat’s Little Theorem:$a^{p-1}\equiv1\mod p$，因為$998244353$是質數，所以$a^{p-2}\equiv a^{-1}\mod p$)，接著就用一般的公式計算即可。

程式碼:

const int _n=3e5+10;  
int t,n,k,cnt[_n<<1],num[_n<<1];  
PII la[_n];  
VI v;  
int fac[_n],inv[_n];  
void exgcd(int a,int b,int& d,int& x,int& y){  
  if(!b)x=1,y=0,d=a;  
  else exgcd(b,a%b,d,y,x),y=(1ll*y-1ll*x*(a/b)%mod+mod)%mod;  
}  
int C(int m,int n){  
  if(m<n)return 0;  
  if(m<mod and n<mod)return 1ll*fac[m]*inv[n]%mod*inv[m-n]%mod;  
  return 1ll*C(m/mod,n/mod)*C(m%mod,n%mod)%mod;  
}  
void genInv(){  
  fac[0]=1;rep(i,1,n+1)fac[i]=1ll*fac[i-1]*i%mod;  
  //int tmp1,tmp2;rep(i,0,n+1)exgcd(fac[i],mod,tmp1,inv[i],tmp2);  
  inv[n]=powmod(fac[n],mod-2);per(i,0,n)inv[i]=1ll*inv[i+1]*(i+1)%mod;  
}  
main(void) {ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);  
  cin>>n>>k;rep(i,0,n){cin>>la[i].fi>>la[i].se;v.pb(la[i].fi),v.pb(la[i].se);}  
  sort(all(v));int nn=unique(all(v))-v.begin(); genInv(); ll ans=0;  
  rep(i,0,n){  
    la[i].fi=lower_bound(v.begin(),v.begin()+nn,la[i].fi)-v.begin();  
    la[i].se=lower_bound(v.begin(),v.begin()+nn,la[i].se)-v.begin();  
  }rep(i,0,n)cnt[la[i].fi]++,cnt[la[i].se+1]--,num[la[i].fi]++;  
  rep(i,1,nn)cnt[i]=cnt[i-1]+cnt[i];  
  rep(i,0,nn)ans=(ans+C(cnt[i],k)-C(cnt[i]-num[i],k)+mod)%mod;  
  cout<<ans<<'\n';  
  return 0;  
}  

標頭、模板請點Submission看($exgcd$用不到，且$C$函數我寫的是Lucas定理法)
Submission