Balanced Subsequences (Codeforces 1924D)
Tags: Math, combinatorics

A sequence of brackets is called balanced if one can turn it into a valid math expression by adding characters '+' and '1'. For example, sequences '(())()', '()', and '(()(()))' are balanced, while ')(', '(()', and '(()))(' are not.A subsequence is a sequence that can be derived from the given sequence by deleting zero or more elements without changing the order of the remaining elements.You are given three integers $$$n$$$, $$$m$$$ and $$$k$$$. Find the number of sequences consisting of $$$n$$$ '(' and $$$m$$$ ')', such that the longest balanced subsequence is of length $$$2 \cdot k$$$. Since the answer can be large calculate it modulo $$$1\,000\,000\,007$$$ ($$$10^9 + 7$$$).

Input: Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 3 \cdot 10^3$$$). Description of the test cases follows.The first line of each test case contains three integers $$$n$$$, $$$m$$$ and $$$k$$$ ($$$1 \le n, m, k \le 2 \cdot 10^3$$$)

Output: For each test case, print one integer — the answer to the problem.

Note: For the first test case "()()", "(())" are the $$$2$$$ sequencesFor the second test case no sequence is possible.For the third test case ")((()", ")(()(", ")()((", "())((" are the $$$4$$$ sequences.

Sample Inputs:
3
2 2 2
3 2 3
3 2 1

Sample Outputs:
2
0
4

Solution (Python):
def power(a, b, p):
    if a == 0:
        return 0
    res = 1
    a %= p
    while b > 0:
        if b & 1:
            res = res * a % p
        b >>= 1
        a = a * a % p
    return res

def pre():
    global fact, inv
    fact = [0] * N
    inv = [0] * N
    fact[0] = inv[0] = 1
    for i in range(1, N):
        fact[i] = fact[i - 1] * i % mod
    for i in range(1, N):
        inv[i] = power(fact[i], mod - 2, mod)

def nCr(n, r):
    if min(n, r) < 0 or r > n:
        return 0
    if n == r:
        return 1
    return fact[n] * inv[r] % mod * inv[n - r] % mod

def f(n, m, k):
    if k >= min(n, m):
        return nCr(n + m, m)
    return nCr(n + m, k)
N = 4005
mod = 1000000007
pre()
t = int(input())
for _ in range(t):
    (n, m, k) = map(int, input().split())
    result = (f(n, m, k) - f(n, m, k - 1) + mod) % mod
    print(result)

Solution (Python):
from sys import stdin
P = 10 ** 9 + 7
n_max = 4 * 10 ** 3
factorials = [1]
for i in range(1, n_max + 1):
    factorials.append(factorials[i - 1] * i % P)
inv_factorials = [1] * (n_max + 1)
inv_factorials[-1] = pow(factorials[-1], P - 2, P)
for i in reversed(range(1, n_max)):
    inv_factorials[i] = inv_factorials[i + 1] * (i + 1) % P
n_tests = int(stdin.readline())
for test_id in range(n_tests):
    (n, m, k) = [int(w) for w in stdin.readline().split()]
    if k > min(m, n):
        print(0)
        continue
    print(factorials[m + n] * (inv_factorials[k] * inv_factorials[m + n - k] - inv_factorials[k - 1] * inv_factorials[m + n - k + 1]) % P)

Solution (Python):
from sys import stdin
P = 10 ** 9 + 7
n_max = 4 * 10 ** 3
factorials = [1]
for i in range(1, n_max + 1):
    factorials.append(factorials[i - 1] * i % P)
inv_factorials = [1] * (n_max + 1)
inv_factorials[-1] = pow(factorials[-1], P - 2, P)
for i in reversed(range(1, n_max)):
    inv_factorials[i] = inv_factorials[i + 1] * (i + 1) % P

def rHillsPaths(n, r):
    if n == r:
        return 1
    return factorials[2 * n - r - 1] * (inv_factorials[n - r] * inv_factorials[n - 1] - inv_factorials[n - r - 1] * inv_factorials[n]) % P
n_tests = int(stdin.readline())
for test_id in range(n_tests):
    (n, m, k) = [int(w) for w in stdin.readline().split()]
    if k > min(m, n):
        print(0)
        continue
    r = m + n - 2 * k + 1
    print(rHillsPaths(r + k, r))