Close Tuples (hard version) (Codeforces 1462E2)
Tags: Math, combinatorics

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$$$).

Input: The first line contains a single integer $$$t$$$ ($$$1 \le t \le 2 \cdot 10^5$$$) — the number of test cases. Then $$$t$$$ test cases follow.The first line of each test case contains three integers $$$n$$$, $$$m$$$, $$$k$$$ ($$$1 \le n \le 2 \cdot 10^5$$$, $$$1 \le m \le 100$$$, $$$1 \le k \le 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 $$$a_1, a_2,\ldots, a_n$$$ ($$$1 \le a_i \le n$$$) — the sequence $$$a$$$.It is guaranteed that the sum of $$$n$$$ for all test cases does not exceed $$$2 \cdot 10^5$$$.

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


Sample Inputs:
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

Sample Outputs:
2
6
1
20

Solution (Python):
import bisect
import sys
p2D = lambda x: print(*x, sep='\n')

def II():
    return int(sys.stdin.buffer.readline())

def MI():
    return map(int, sys.stdin.buffer.readline().split())

def LI():
    return list(map(int, sys.stdin.buffer.readline().split()))

def LLI(rows_number):
    return [LI() for _ in range(rows_number)]

def BI():
    return sys.stdin.buffer.readline().rstrip()

def SI():
    return sys.stdin.buffer.readline().rstrip().decode()

def li():
    return [int(i) for i in input().split()]

def lli(rows):
    return [li() for _ in range(rows)]

def si():
    return input()

def ii():
    return int(input())

def ins():
    return input().split()
mod = 10 ** 9 + 7
fval = [1]
for i in range(1, 200001):
    x = fval[-1] * i % mod
    fval.append(x)
ifac = [1] * 200001
ifac[200000] = pow(fval[200000], mod - 2, mod)
for i in range(200000 - 1, 1, -1):
    ifac[i] = ifac[i + 1] * (i + 1) % mod

def solve():
    (n, m, k) = LI()
    a = LI()
    a.sort()
    ans = 0
    for i in range(m - 1, n):
        p = bisect.bisect_left(a, a[i] - k)
        if a[i] - a[p] < k + 1 and i - p + 1 >= m:
            ans = (ans + fval[i - p] * ifac[m - 1] * ifac[i - p + 1 - m]) % mod
    return ans

def main():
    for _ in range(II()):
        sys.stdout.write(str(solve()) + '\n')
if __name__ == '__main__':
    main()

Solution (Python):
import sys
sys.setrecursionlimit(10 ** 5)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep='\n')

def II():
    return int(sys.stdin.buffer.readline())

def MI():
    return map(int, sys.stdin.buffer.readline().split())

def LI():
    return list(map(int, sys.stdin.buffer.readline().split()))

def LLI(rows_number):
    return [LI() for _ in range(rows_number)]

def BI():
    return sys.stdin.buffer.readline().rstrip()

def SI():
    return sys.stdin.buffer.readline().rstrip().decode()
inf = 10 ** 16
md = 10 ** 9 + 7

def nCr(com_n, com_r):
    if com_n < com_r:
        return 0
    return fac[com_n] * ifac[com_r] % md * ifac[com_n - com_r] % md
n_max = 200005
fac = [1]
for i in range(1, n_max + 1):
    fac.append(fac[-1] * i % md)
ifac = [1] * (n_max + 1)
ifac[n_max] = pow(fac[n_max], md - 2, md)
for i in range(n_max - 1, 1, -1):
    ifac[i] = ifac[i + 1] * (i + 1) % md
for _ in range(II()):
    (n, m, k) = MI()
    aa = LI()
    aa.sort()
    ans = 0
    j = 0
    for (i, a) in enumerate(aa):
        while j < n and aa[j] - a <= k:
            j += 1
        ans += nCr(j - i - 1, m - 1)
        ans %= md
    print(ans)

Solution (Python):
from collections import defaultdict, Counter
import sys
import bisect

def get_array():
    return list(map(int, sys.stdin.readline().strip().split()))

def get_ints():
    return map(int, sys.stdin.readline().strip().split())

def input():
    return sys.stdin.readline().strip()
N = 200001
factorialNumInverse = [None] * (N + 1)
naturalNumInverse = [None] * (N + 1)
fact = [None] * (N + 1)

def InverseofNumber(p):
    naturalNumInverse[0] = naturalNumInverse[1] = 1
    for i in range(2, N + 1, 1):
        naturalNumInverse[i] = naturalNumInverse[p % i] * (p - int(p / i)) % p

def InverseofFactorial(p):
    factorialNumInverse[0] = factorialNumInverse[1] = 1
    for i in range(2, N + 1, 1):
        factorialNumInverse[i] = naturalNumInverse[i] * factorialNumInverse[i - 1] % p

def factorial(p):
    fact[0] = 1
    for i in range(1, N + 1):
        fact[i] = fact[i - 1] * i % p

def Binomial(N, R, p):
    ans = fact[N] * factorialNumInverse[R] % p * factorialNumInverse[N - R] % p
    return ans
p = 1000000007
InverseofNumber(p)
InverseofFactorial(p)
factorial(p)
for _ in range(int(input())):
    (n, m, k) = get_ints()
    l = get_array()
    l.sort()
    ans = 0
    for i in range(n):
        ind = bisect.bisect_right(l, l[i] + k, i)
        if ind - i >= m:
            ans = (ans + Binomial(ind - i - 1, m - 1, p)) % p
    print(ans)