Soluție HackerRank pentru Div and Span, subdomeniul Combinatorics, în Python 3. Include cerința formatată, exemple, explicația pașilor și cod sursă.
- Problemă: Div and Span
- Domeniu: Combinatorics
- Limbaj: Python 3
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
Cerință
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 ≤ T ≤ 1000
* 1 ≤ X ≤ 10^5
* 1 ≤ Y ≤ 200
Cod sursă
# 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)