Prediction (Codeforces 1809G)
Tags: Math, combinatorics

Consider a tournament with $$$n$$$ participants. The rating of the $$$i$$$-th participant is $$$a_i$$$.The tournament will be organized as follows. First of all, organizers will assign each participant an index from $$$1$$$ to $$$n$$$. All indices will be unique. Let $$$p_i$$$ be the participant who gets the index $$$i$$$.Then, $$$n-1$$$ games will be held. In the first game, participants $$$p_1$$$ and $$$p_2$$$ will play. In the second game, the winner of the first game will play against $$$p_3$$$. In the third game, the winner of the second game will play against $$$p_4$$$, and so on — in the last game, the winner of the $$$(n-2)$$$-th game will play against $$$p_n$$$.Monocarp wants to predict the results of all $$$n-1$$$ games (of course, he will do the prediction only after the indices of the participants are assigned). He knows for sure that, when two participants with ratings $$$x$$$ and $$$y$$$ play, and $$$|x - y| > k$$$, the participant with the higher rating wins. But if $$$|x - y| \le k$$$, any of the two participants may win.Among all $$$n!$$$ ways to assign the indices to participants, calculate the number of ways to do this so that Monocarp can predict the results of all $$$n-1$$$ games. Since the answer can be large, print it modulo $$$998244353$$$.

Input: The first line contains two integers $$$n$$$ and $$$k$$$ ($$$2 \le n \le 10^6$$$; $$$0 \le k \le 10^9$$$).The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$0 \le a_1 \le a_2 \le \dots \le a_n \le 10^9$$$).

Output: Print one integer — the number of ways to assign the indices to the participants so that Monocarp can predict the results of all $$$n-1$$$ games.

Note: In the first example, a match with any pair of players can be predicted by Monocarp, so all $$$24$$$ ways to assign indices should be counted.In the second example, suitable ways are $$$[1, 3, 2]$$$, $$$[2, 3, 1]$$$, $$$[3, 1, 2$$$] and $$$[3, 2, 1]$$$.

Sample Inputs:
4 3
7 12 17 21

3 7
4 9 28

4 1
1 2 3 4

4 1
1 2 2 4

16 30
8 12 15 27 39 44 49 50 51 53 58 58 59 67 68 100

Sample Outputs:
24

4

0

12

527461297

Solution (Python):
(n, k) = map(int, input().split())
a = list(map(int, input().split()))
MOD = 998244353

def add(x, y):
    return ((x + y) % MOD + MOD) % MOD

def mul(x, y):
    return x * y % MOD

def binpow(x, y):
    z = 1
    while y:
        if y % 2 == 1:
            z = mul(z, x)
        x = mul(x, x)
        y //= 2
    return z

def inv(x):
    return binpow(x, MOD - 2)

def divide(x, y):
    return mul(x, inv(y))
a.reverse()
fact = [1] * (n + 1)
for i in range(1, n + 1):
    fact[i] = mul(fact[i - 1], i)
first_no_conflict = [0] * n
for i in range(n):
    if i > 0:
        first_no_conflict[i] = first_no_conflict[i - 1]
    while first_no_conflict[i] < n and a[first_no_conflict[i]] >= a[i] - k:
        first_no_conflict[i] += 1
dp = [0] * (n + 1)
if a[0] - a[1] > k:
    dp[1] = 1
for i in range(1, n):
    no_of_conflicting = first_no_conflict[i] - i - 1
    dp[i + no_of_conflicting + 1] = add(dp[i + no_of_conflicting + 1], mul(dp[i], divide(fact[i + no_of_conflicting - 1], fact[i - 1])))
    dp[i + 1] = add(dp[i + 1], mul(dp[i], i))
print(dp[n])

Solution (Python):
import sys, os, io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

def comb(n, r):
    return fact[n] * inv[r] % mod * inv[n - r] % mod if n >= r >= 0 else 0
(n, k) = map(int, input().split())
mod = 998244353
a = list(map(int, input().split()))
a.reverse()
if a[0] - a[1] <= k:
    ans = 0
    print(ans)
    exit()
l = n + 5
fact = [1] * (l + 1)
for i in range(1, l + 1):
    fact[i] = i * fact[i - 1] % mod
inv = [1] * (l + 1)
inv[l] = pow(fact[l], mod - 2, mod)
for i in range(l - 1, -1, -1):
    inv[i] = (i + 1) * inv[i + 1] % mod
dp = [0] * n
dp[0] = 1
j = 1
for i in range(1, n):
    dpi = dp[i - 1] % mod
    dp[i] += dpi * i % mod
    while j < n and a[i] - a[j] <= k:
        j += 1
    dp[j - 1] += fact[j - i - 1] * comb(j - 2, j - i - 1) % mod * dpi % mod
ans = dp[-1] % mod
print(ans)

Solution (Python):
MOD = 998244353

def modmul(x, y, c=0):
    return (x * y + c) % MOD

def inv(x):
    return pow(x, MOD - 2, MOD)
MAX = 10 ** 6 + 10
fact = [1]
for i in range(1, MAX):
    fact.append(modmul(i, fact[i - 1]))
invfact = [1] * MAX
invfact[MAX - 1] = inv(fact[MAX - 1])
for i in range(MAX - 2, -1, -1):
    invfact[i] = modmul(i + 1, invfact[i + 1])
(n, k) = map(int, input().split())
l = list(map(int, input().split()))[::-1]
dp = [1]
left = 0
right = 1
if l[0] <= l[1] + k:
    print(0)
    quit()
pointer = 0
for i in range(1, n):
    while l[pointer] > l[i] + k:
        base = dp[pointer]
        diff = modmul(invfact[pointer - 1], fact[i - 2])
        ch = modmul(diff, base)
        right -= ch
        left += ch
        pointer += 1
    left %= MOD
    right %= MOD
    dp.append(left)
    left = modmul(left, i)
    right = modmul(right, i - 1)
    right += dp[i]
print((left + right) % MOD)