Ira and Flamenco (Codeforces 1833F)
Tags: Math, two pointers

Ira loves Spanish flamenco dance very much. She decided to start her own dance studio and found $$$n$$$ students, $$$i$$$th of whom has level $$$a_i$$$.Ira can choose several of her students and set a dance with them. So she can set a huge number of dances, but she is only interested in magnificent dances. The dance is called magnificent if the following is true:   exactly $$$m$$$ students participate in the dance;  levels of all dancers are pairwise distinct;  levels of every two dancers have an absolute difference strictly less than $$$m$$$. For example, if $$$m = 3$$$ and $$$a = [4, 2, 2, 3, 6]$$$, the following dances are magnificent (students participating in the dance are highlighted in red): $$$[\color{red}{4}, 2, \color{red}{2}, \color{red}{3}, 6]$$$, $$$[\color{red}{4}, \color{red}{2}, 2, \color{red}{3}, 6]$$$. At the same time dances $$$[\color{red}{4}, 2, 2, \color{red}{3}, 6]$$$, $$$[4, \color{red}{2}, \color{red}{2}, \color{red}{3}, 6]$$$, $$$[\color{red}{4}, 2, 2, \color{red}{3}, \color{red}{6}]$$$ are not magnificent.In the dance $$$[\color{red}{4}, 2, 2, \color{red}{3}, 6]$$$ only $$$2$$$ students participate, although $$$m = 3$$$.The dance $$$[4, \color{red}{2}, \color{red}{2}, \color{red}{3}, 6]$$$ involves students with levels $$$2$$$ and $$$2$$$, although levels of all dancers must be pairwise distinct.In the dance $$$[\color{red}{4}, 2, 2, \color{red}{3}, \color{red}{6}]$$$ students with levels $$$3$$$ and $$$6$$$ participate, but $$$|3 - 6| = 3$$$, although $$$m = 3$$$.Help Ira count the number of magnificent dances that she can set. Since this number can be very large, count it modulo $$$10^9 + 7$$$. Two dances are considered different if the sets of students participating in them are different.

Input: The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — number of testcases.The first line of each testcase contains integers $$$n$$$ and $$$m$$$ ($$$1 \le m \le n \le 2 \cdot 10^5$$$) — the number of Ira students and the number of dancers in the magnificent dance.The second line of each testcase contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — levels of students.It is guaranteed that the sum of $$$n$$$ over all testcases does not exceed $$$2 \cdot 10^5$$$.

Output: For each testcase, print a single integer — the number of magnificent dances. Since this number can be very large, print it modulo $$$10^9 + 7$$$.

Note: In the first testcase, Ira can set such magnificent dances: $$$[\color{red}{8}, 10, 10, \color{red}{9}, \color{red}{6}, 11, \color{red}{7}]$$$, $$$[\color{red}{8}, \color{red}{10}, 10, \color{red}{9}, 6, 11, \color{red}{7}]$$$, $$$[\color{red}{8}, 10, \color{red}{10}, \color{red}{9}, 6, 11, \color{red}{7}]$$$, $$$[\color{red}{8}, 10, \color{red}{10}, \color{red}{9}, 6, \color{red}{11}, 7]$$$, $$$[\color{red}{8}, \color{red}{10}, 10, \color{red}{9}, 6, \color{red}{11}, 7]$$$.The second testcase is explained in the statements.

Sample Inputs:
9
7 4
8 10 10 9 6 11 7
5 3
4 2 2 3 6
8 2
1 5 2 2 3 1 3 3
3 3
3 3 3
5 1
3 4 3 10 7
12 3
5 2 1 1 4 3 5 5 5 2 7 5
1 1
1
3 2
1 2 3
2 2
1 2

Sample Outputs:
5
2
10
0
5
11
1
2
1

Solution (Python):
import sys
input = sys.stdin.readline

def inp():
    return int(input())

def inlt():
    return list(map(int, input().split()))

def insr():
    s = input()
    return list(s[:len(s) - 1])

def invr():
    return map(int, input().split())
inv_set = {1: 1}
mm = 1000000007

def inv(t):
    if t in inv_set:
        return inv_set[t]
    inv_set[t] = (mm - mm // t) * inv(mm % t) % mm
    return inv_set[t]

def solve(arr, m):
    n = len(arr)
    if m == 1:
        return n
    arr.sort()
    num = []
    cnt = []
    last = -1
    for i in range(0, n):
        if arr[i] != last:
            num.append(arr[i])
            cnt.append(1)
        else:
            cnt[-1] = cnt[-1] + 1
        last = arr[i]
    ans = 0
    cache = 0
    cache_i = -1
    for i in range(0, len(num) - m + 1):
        if num[i + m - 1] - num[i] < m:
            t = 1
            if cache_i >= 0 and cache_i + 1 == i:
                t = cache * cnt[i + m - 1] % mm
                t = inv(cnt[i - 1]) * t % mm
            else:
                for j in range(i, i + m):
                    t = t * cnt[j] % mm
            cache = t
            cache_i = i
            ans = (ans + t) % mm
    return ans
if __name__ == '__main__':
    t = inp()
    for i in range(0, t):
        t = inlt()
        arr = inlt()
        ans = solve(arr, t[1])
        print(ans)

Solution (Python):
import os
if os.path.exists('in.txt'):
    file = open('in.txt')
    input = file.readline
from itertools import *
from functools import *
from heapq import *
from collections import *
import math
mod = 1000000007
readint = lambda : int(input())
readlist = lambda : list(map(int, input().split()))

def solution():
    (n, m) = readlist()
    a = readlist()
    if m == 1:
        print(n % mod)
        return
    C = Counter(a)
    res = 0
    p = 0
    nums = sorted(C)
    for i in range(m - 1, len(nums)):
        if nums[i] - nums[i - (m - 1)] == m - 1:
            if p:
                p = p * C[nums[i]] * pow(C[nums[i - m]], mod - 2, mod) % mod
            else:
                p = reduce(lambda s, x: s * x % mod, [C[x] for x in nums[i - (m - 1):i + 1]])
            res += p
        else:
            p = 0
    print(res % mod)
for i in range(readint()):
    solution()

Solution (Python):
import os
if os.path.exists('in.txt'):
    file = open('in.txt')
    input = file.readline
from itertools import *
from functools import *
from heapq import *
from collections import *
import math
mod = 1000000007
readint = lambda : int(input())
readlist = lambda : list(map(int, input().split()))

def solution():
    (n, m) = readlist()
    a = readlist()
    if m == 1:
        print(n % mod)
        return
    C = Counter(a)
    res = 0
    p = 0
    nums = sorted(C)
    for i in range(m - 1, len(nums)):
        if nums[i] - nums[i - (m - 1)] == m - 1:
            if p:
                p = p * C[nums[i]] * pow(C[nums[i - m]], mod - 2, mod) % mod
            else:
                p = reduce(lambda s, x: s * x % mod, [C[x] for x in nums[i - (m - 1):i + 1]])
            res += p
        else:
            p = 0
    print(res % mod)
for i in range(readint()):
    solution()