Excellent Arrays (Codeforces 1550D)
Tags: Math, two pointers

Let's call an integer array $$$a_1, a_2, \dots, a_n$$$ good if $$$a_i \neq i$$$ for each $$$i$$$.Let $$$F(a)$$$ be the number of pairs $$$(i, j)$$$ ($$$1 \le i < j \le n$$$) such that $$$a_i + a_j = i + j$$$.Let's say that an array $$$a_1, a_2, \dots, a_n$$$ is excellent if:   $$$a$$$ is good;  $$$l \le a_i \le r$$$ for each $$$i$$$;  $$$F(a)$$$ is the maximum possible among all good arrays of size $$$n$$$. Given $$$n$$$, $$$l$$$ and $$$r$$$, calculate the number of excellent arrays modulo $$$10^9 + 7$$$.

Input: The first line contains a single integer $$$t$$$ ($$$1 \le t \le 1000$$$) — the number of test cases. The first and only line of each test case contains three integers $$$n$$$, $$$l$$$, and $$$r$$$ ($$$2 \le n \le 2 \cdot 10^5$$$; $$$-10^9 \le l \le 1$$$; $$$n \le r \le 10^9$$$).It's guaranteed that the sum of $$$n$$$ doesn't exceed $$$2 \cdot 10^5$$$.

Output: For each test case, print the number of excellent arrays modulo $$$10^9 + 7$$$.

Note: In the first test case, it can be proven that the maximum $$$F(a)$$$ among all good arrays $$$a$$$ is equal to $$$2$$$. The excellent arrays are:   $$$[2, 1, 2]$$$;  $$$[0, 3, 2]$$$;  $$$[2, 3, 2]$$$;  $$$[3, 0, 1]$$$. 

Sample Inputs:
4
3 0 3
4 -3 5
42 -33 55
69 -42 146

Sample Outputs:
4
10
143922563
698570404

Solution (Python):
def comb(n, r):
    return fact[n] * inv[r] % mod * inv[n - r] % mod if n >= r >= 0 else 0
mod = pow(10, 9) + 7
l = 200005
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
t = int(input())
for _ in range(t):
    (n, l, r) = map(int, input().split())
    m = min(1 - l, r - n)
    n0 = n // 2 + n % 2
    ans = m * comb(n, n0) % mod * (n % 2 + 1) % mod
    (c1, c2) = (0, 0)
    (l0, r0) = (1, n)
    for _ in range(n):
        m += 1
        if l0 - m < l:
            c1 += 1
        if r0 + m > r:
            c2 += 1
        x = n - c1 - c2
        ans += comb(x, n0 - c1)
        ans %= mod
        if n % 2:
            ans += comb(x, n0 - c2)
            ans %= mod
    print(ans)

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

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

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

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

def LI1():
    return list(map(int1, sys.stdin.readline().split()))

def LLI1(rows_number):
    return [LI1() for _ in range(rows_number)]

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

def nCr(com_n, com_r):
    if com_r < 0:
        return 0
    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

def solve():
    (n, l, r) = LI()
    ans = 0
    mn = max(1, 1 - r, l - n)
    mx = min(1 - l, r - n)
    if mn <= mx:
        if n & 1:
            ans += nCr(n, n // 2) * 2 * (mx - mn + 1 - (mn <= 0 <= mx)) % md
        else:
            ans += nCr(n, n // 2) * (mx - mn + 1 - (mn <= 0 <= mx)) % md
    s = mn - 1
    while s > 0:
        L = max(1, l + s)
        R = min(n, r - s)
        ans += nCr(R - L + 1, n // 2 - L + 1)
        if n & 1:
            ans += nCr(R - L + 1, n // 2 - L + 2)
        s -= 1
    s = mx + 1
    while 1:
        L = max(1, l + s)
        R = min(n, r - s)
        if L > R + 1:
            break
        ans += nCr(R - L + 1, n // 2 - L + 1)
        if n & 1:
            ans += nCr(R - L + 1, n // 2 - L + 2)
        s += 1
        ans %= md
    print(ans)
for testcase in range(II()):
    solve()

Solution (Python):
N = 200000 + 1
MOD = 10 ** 9 + 7
F = [1] * N
G = [1] * N

def init():
    for i in range(1, N):
        F[i] = F[i - 1] * i % MOD
    G[N - 1] = pow(F[N - 1], MOD - 2, MOD)
    for i in range(N - 2, 0, -1):
        G[i] = G[i + 1] * (i + 1) % MOD

def C(n, m):
    if m > n or m < 0:
        return 0
    return F[n] * G[m] * G[n - m] % MOD

def solve():
    (n, l, r) = list(map(int, input().split()))
    answer = 0
    common_offset = max(min(1 - l, r - n), 0)
    if common_offset:
        answer = common_offset * C(n, n // 2) % MOD
        if n % 2:
            answer += common_offset * C(n, n // 2 + 1) % MOD
    for offset in range(common_offset + 1, min(r - 1, n - l) + 1):
        u = min(r - offset, n) - max(l - offset, 1) + 1
        v = min(r + offset, n) - max(l + offset, 1) + 1
        if u + v < n:
            break
        answer += C(u + v - n, n // 2 - n + v) % MOD
        if n % 2:
            answer += C(u + v - n, n // 2 + 1 - n + v) % MOD
        answer %= MOD
    return answer
init()
for case in range(int(input())):
    print(solve())