HackerRank Combinatorics – Div and Span

Challenge: Div and Span

Subdomeniu: Combinatorics (combinatorics)

Scor cont: 70.0 / 70

Submission status: Accepted

Submission score: 1.0

Submission ID: 464745293

Limbaj: python3

Link challenge: https://www.hackerrank.com/challenges/div-and-span/problem

Cerinta

Maya is teaching Alex about HyperText Markup Language ([HTML](https://en.wikipedia.org/wiki/HTML)). Alex is confused about *div* and *span* tags, so Maya decides to reduce the concept to a simpler visual by representing *div* tags as square brackets and *span* tags as parentheses. In other words, she represents `<div>` as `[`, `</div>` as `]`, `<span>` as `(`, and `</span>` as `)`.

 We use the following rules to determine the validity of a configuration:

1. The empty string (""), a single pair of square brackets `[]`, and single pair of parentheses `()` are all considered to be valid configurations. We can express each of these as $V$.
2. A valid configuration, $V$, which *does not contain* square brackets is called a *normal* configuration, which we can express as $N$. For example, `()` is *normal*.
3. Two or more consecutive valid configurations (e.g., $VV$) also constitute a valid configuration. For example, `[][]`, `()()`, and `[]()[]` are all valid.
4. The following configurations are also valid: `[V]`, `(N)`. 	
	For example, `[[(())]()]`, `((()))`, and `[(())[]]` are all valid; however, `([])` is *not valid* (you cannot nest a *div* tag inside a *span* tag).

Given some number of distinguishable square brackets, $X$, and some number of distinguishable parentheses, $Y$, how many valid configurations can we build using the above rules? As this answer can be very large, print it modulo $10^9+7$.

Input Format

The first line contains a single positive integer, $T$, denoting the number of test cases. 		
Each of the $T$ subsequent lines contains $2$ positive space-separated integers describing the respective values of $X$ (the number of distinguishable square brackets) and $Y$ (the number of distinguishable parentheses).

Output Format

For each test case, print the number of different valid configurations modulo $10^9+7$.

Constraints

* $1 \leq T \leq 1000$
* $1 \leq X \leq 10^5$
* $1 \leq Y \leq 200$

Cod sursa

# Enter your code here. Read input from STDIN. Print output to STDOUT
m = 10 ** 9 + 7
# parantheses
p_lim = 201
# dpp[i][j] is # of paranth. configurations of length i, consisting of j elements
dpp = [[0 for _ in range(p_lim)] for _ in range(p_lim)]
dpp[0][0] = 1
cumsum = [0 for _ in range(p_lim)]
cumsum[0] = 1
fact = [1]
for i in range(1, 250000):
    fact.append((fact[-1] * i) % m)

def egcd(a, b):
    '''
    Extended Euclidian algorithm
    '''
    if a == 0:
        return (b, 0, 1)
    else:
        g, y, x = egcd(b % a, a)
        return (g, x - (b // a) * y, y)

def modinv(a, m):
    '''
    Finds modular inverse modulo m
    '''  
    while a < 0:
        a += m
    g, x, y = egcd(a, m)
    if g != 1:
        raise Exception('Modular inverse does not exist')
    else:
        return x % m

def choose(n, k):
    '''
    Computes binomial efficiently
    '''
    r = (fact[n] * modinv(fact[k], m)) % m
    return (r * modinv(fact[n - k], m)) % m
    
def C(n): # catalan number
    return (fact[2 * n] * modinv(fact[n + 1], m)) % m

for i in range(1, p_lim):
    dpp[i][1] = cumsum[i - 1] % m
    cumsum[i] = (cumsum[i] + dpp[i][1]) % m
    for j in range(2, p_lim):
        for k in range(1, i - j + 2):
            dpp[i][j] = (dpp[i][j] + dpp[k][1] * dpp[i - k][j - 1]) % m   
        cumsum[i] = (cumsum[i] + dpp[i][j]) % m
for _ in range(int(input())):
    x, y = map(int,input().split())
    r = 0
    for i in range(y + 1):
        r += dpp[y][i] * choose(2 * x + i, i)
        r %= m
    r = (r * fact[y]) % m
    r = (r * C(x)) % m
    print(r)