链接： D. Rescue Nibel!
题意：
有 n 栈灯 ，每栈灯在 [ l , r] 时间段内是开着的 ，现在需要选择 k 栈灯 ，使他们能在同一时间内打开 ，问有多少种选择方法 。
思路：
- 如果不考虑重复的情况 ， 我们可以算出每个时间点 有多少盏灯亮着 ，然后用一个组合数就可以把答案算出来 ，但这样明显会有很多重复的情况 。 所以对于每个时间的点 ， 我们只算开始时间在这个点的灯的贡献 ， 所以需要在减去 开始时间都不在这个点的贡献 。
- 我们可以先离散化一下，再用差分数组 统计每个时间点亮着的灯的数量 。
代码：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e6+7;
const int mod = 998244353;
ll a1[maxn],b1[maxn];
struct node{
ll l,r;
}num[maxn];
ll n,k,val[maxn],cnt;
ll ans , d[maxn] , x[maxn] , c[maxn];
ll quickpow(ll a ,ll b){
ll ans=1;while(b>0){
if(b&1) ans=ans*a%mod;a=a*a%mod;b>>=1;}return ans;
}
ll ni(ll x){
return quickpow(x,mod-2);
}
void init (){
a1[0]=1;for(int i = 1 ;i < maxn ;i ++){
a1[i] = (a1[i-1] * i) % mod;}b1[maxn - 1] = ni(a1[maxn - 1]);for(int i = maxn - 2 ;i >= 0 ;i --){
b1[i] = b1[i+1] * (i + 1) % mod;}
}
ll C(ll n,ll m){
if(n < m) return 0;return (a1[n] * b1[m] % mod) * b1[n-m] % mod;
}
int main() {
scanf("%lld%lld",&n,&k);init();for(int i = 1; i <= n; i ++){
scanf("%lld%lld",&num[i].l,&num[i].r);val[cnt ++] = num[i].l;val[cnt ++] = num[i].r;}sort(val,val + cnt);cnt = unique(val,val + cnt) - val;for(int i = 1; i <= n; i ++){
num[i].l = lower_bound(val , val + cnt , num[i].l) - val + 1;num[i].r = lower_bound(val , val + cnt , num[i].r) - val + 1;//printf ("%lld %lld %lld\n",num[i].l,num[i].r,cnt);}for(int i = 1; i <= n; i ++){
x[num[i].l] ++;d[num[i].l] ++;d[num[i].r + 1] -- ;}for(int i = 1; i <= cnt; i ++){
c[i] = c[i - 1] + d[i];}for(int i = 1; i <= cnt; i ++){
if(c[i] < k) continue;//printf ("%lld %lld ",C(c[i] , k),C(c[i] - x[i] , k));ans = (ans + C(c[i] , k) - C(c[i] - x[i] , k) + mod) % mod;}printf ("%lld\n",ans);return 0;
}