E2. Close Tuples (hard version)（组合数）

本文主要是介绍E2. Close Tuples (hard version)（组合数），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

链接
https://codeforces.com/contest/1462/problem/E2

This is the hard version of this problem. The only difference between the easy and hard versions is the constraints on k and m. In this version of the problem, you need to output the answer by modulo 109+7.

You are given a sequence a of length n consisting of integers from 1 to n. The sequence may contain duplicates (i.e. some elements can be equal).

Find the number of tuples of m elements such that the maximum number in the tuple differs from the minimum by no more than k. Formally, you need to find the number of tuples of m indices i1<i2<…<im, such that

max(ai1,ai2,…,aim)−min(ai1,ai2,…,aim)≤k.
For example, if n=4, m=3, k=2, a=[1,2,4,3], then there are two such triples (i=1,j=2,z=4 and i=2,j=3,z=4). If n=4, m=2, k=1, a=[1,1,1,1], then all six possible pairs are suitable.

As the result can be very large, you should print the value modulo 109+7 (the remainder when divided by 109+7).

Input
The first line contains a single integer t (1≤t≤2⋅105) — the number of test cases. Then t test cases follow.

The first line of each test case contains three integers n, m, k (1≤n≤2⋅105, 1≤m≤100, 1≤k≤n) — the length of the sequence a, number of elements in the tuples and the maximum difference of elements in the tuple.

The next line contains n integers a1,a2,…,an (1≤ai≤n) — the sequence a.

It is guaranteed that the sum of n for all test cases does not exceed 2⋅105.

Output
Output t answers to the given test cases. Each answer is the required number of tuples of m elements modulo 109+7, such that the maximum value in the tuple differs from the minimum by no more than k.

Example
input
4
4 3 2
1 2 4 3
4 2 1
1 1 1 1
1 1 1
1
10 4 3
5 6 1 3 2 9 8 1 2 4
output
2
6
1
20

思路
组合数

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 1e9 +7;
const double esp = 1e-6;
const double PI = acos(-1);
const int N = 2e5 + 10;
int n,m,k; 
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 % mod;base = base * base % mod;b>>=1; }return ans;
}
void init(){f[0]=1;for(int i=1;i<=2e5;i++){f[i]=f[i-1]*i%mod;} 
}
ll cal(ll n,ll m){if(n<m) return 0; return 1ll*f[n]*qpow(f[m],mod-2)%mod*qpow(f[n-m],mod-2)%mod;
}
void solve(){	scanf("%d %d %d",&n,&m,&k);for(int i=1;i<=n;i++) scanf("%d",&a[i]);sort(a,a+n+1);ll res = 0;int l =1;for(int i=1;i<=n;i++){while(a[i]-a[l]>k) l++;//cout<<l<<" "<<i<<" "<<m-1<<endl; res += cal(i-l,m-1);res%=mod; }printf("%lld\n",res);
}int main(){int t = 1;init();scanf("%d",&t);while(t--){solve();}return 0;
}
/*
5 0 3 0 4
5 5 3 5 4
*/