Description

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 $ 10^9+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 $ i_1 < i_2 < \ldots < i_m $ , such that

$\max(a_{i_1}, a_{i_2}, \ldots, a_{i_m}) - \min(a_{i_1}, a_{i_2}, \ldots, a_{i_m}) \le 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 $ 10^9 + 7 $ (the remainder when divided by $ 10^9 + 7$).

Solution

首先将a排序

依次指定每个数为最小值，那剩下的$m-1$个数的选择区域就确定了

每次向答案累加$\binom{len}{m-1}$

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
using namespace std;
int T,n,m,k,a[200005];
long long fac[200005]={1},ans,inv[200005];
const long long mod=1e9+7;
inline int read()
{
    int w=0,f=1;
    char ch=0;
    while(ch<'0'||ch>'9'){if(ch=='-') f=-1; ch=getchar();}
    while(ch>='0'&&ch<='9')w=(w<<1)+(w<<3)+ch-'0',ch=getchar();
    return w*f;
}
long long ksm(long long a,long long p)
{
    long long ret=1ll;
    while(p)
    {
        if(p&1) (ret*=a)%=mod;
        p>>=1,(a*=a)%=mod;
    }
    return ret;
}
long long C(int x,int y)
{
    if(y>x) return 0;
    return fac[x]*inv[y]%mod*inv[x-y]%mod;
}
int main()
{
    for(int i=1;i<=200000;i++) fac[i]=fac[i-1]*i%mod;
    inv[200000]=ksm(fac[200000],mod-2);
    for(int i=199999;~i;i--) inv[i]=inv[i+1]*(i+1)%mod;
    T=read();
    for(;T;T--)
    {
        n=read(),m=read(),k=read(),ans=0;
        for(int i=1;i<=n;i++) a[i]=read();
        sort(a+1,a+n+1);
        for(int i=1;i<=n;i++)
        {
            int l=i+1,r=upper_bound(a+1,a+n+1,a[i]+k)-a;
            (ans+=C(r-l,m-1))%=mod;
        }
        printf("%lld\n",ans);
    }
    return 0;
}

Close Tuples