CF1462E2

# 组合数 ------------ ### 分析 首先~~恶心人的~~是这是道纯英文的题的**题意**。借助一些奇怪的手段（指盲猜），我们可以明白这题面的意思是 给定 $t$ 个长为 $n$ 的数组 $a$，取元素个数为 $m$ 的数组 ${b}\in a$ 满足其中元素各不相同，使得 $num_1,num_2 \in b$ 满足 $max(num_1)-min(num_2)\leqslant k$，问最多能找出多少组，并取模 $10^9+7$。 想到是组合数之后，本想一发 ```sort``` 之后从头开始求区间的组合，但是偶发现有问题，由于数据**可能重复**，于是复杂度增加亿点点。 如数据 $1, 2, 3, 3, 4$ 按上述方法就是 $cnt$ 先加上 $1 \sim 3$ 之间的组合数，求完之后再加上 $2 \sim 4$ 之间的组合数，但是 $1 \sim 3$ 之间的 $2, 3, 3$ 和 $2 \sim 4$ 之间的 $2, 3, 3$ 重复了。~~于是卡了一节课 窝太菜了~~ 后经学长点拨，在排序后先取一个值 $a_i$，再在 $( a_i,a_i+2 ]$ 范围内取两个值，便可以避免重复。（妙哉！） 例如，求 $1 \sim 3$ 时，取最小值 $1$，在 $( 1 , 3 ]$ 区间内（即 $2 ,3 ,3$）任取两个值； 接着求 $2 \sim 4$ 时，取最小值 $2$，在 $( 2 , 4 ]$ 区间内任取两个值。 不难看出，以上情况无重复。 易得，求 $(a_i, a_i+k ]$ 同理。 想清楚原理后就不难实现了 **记得开 long long！** （代码中将数组 $a$ 记作 $ght$） ------------ ### 实现 贴核心代码： ```cpp const int N = 200005; const int md = 1000000007; int a[N]; ll f[N]; ll qpow(ll a, ll b) { //快速幂 ll ans = 1, base = a; while(b){ if(b&1)ans=ans*base%md; base=base*base%md; b>>=1; } return ans; } ll ght(ll n, ll m) { if (n<m) return 0; return 1ll*f[n]*qpow(f[m],md-2)%md*qpow(f[n-m],md-2)%md;//这里一不小心就会被long long 卡爆 } int t,n,m,k; int main(){ f[0]=1; for(int i=1;i<=200000;i++) f[i]=f[i-1]*i%md; read(t);//快读相关 while(t--){ read(n,m,k); for (int i=0; i<n;i++) read(a[i]);//快读相关 sort(a,a+n);//排序以便枚举 int p=0; ll ans=0; for (int i=0;i<n;i++){ p=(int)(upper_bound(a,a+n,a[i]+k)-a); if(p-i>=m) { ans+=ght(p-i-1,m-1); ans%=md; } } wrti(ans);//快写相关 } flush();//快写相关 return 0; } ``` 完整代码已 AC。 [Easy 版本](https://www.luogu.com.cn/problem/CF1462E1) 就是设组合数的最大最小值之差为 $2$，且每组只查 $3$ 个元素，原理是一样的。 ### 不开 long long 见祖宗！！！！！ 管理员手下留情ya~