Correct Bracket Sequence
All submissions for this problem are available.
A string consisting only of parentheses ('(' and ')') is called a bracket sequence. Some bracket sequence are called correct bracket sequences(CBS). More formally:
- Empty string is a CBS.
- If S is a CBS, then (S) is also a CBS.
- If S and T are CBS, then ST (concatenation of S and T) is also a CBS.
You are given two numbers N and K. Find the probability that a N length CBS can be converted into a 'good' CBS by at most K 'good' swaps. A swap is 'good' if the sequence after the swap is a CBS. If the answer is of the form P/Q where P and Q are coprime, print (P*Q-1) modulo 1000000007.
Input Format:The first line contains an integer T, the number of test cases. Next T lines contains two space separated integers N, K.
Output Format:For each test case, output the corresponding answer in a separate line.
- N is even.
Explanation:Correct Bracket sequences for n = 8:
In 3, the 3rd and 5th characters can be swapped to form a good CBS since it is a good swap.
Similarly 1,2,4,5,6,7,10,11,12 can also be converted to good CBS.
Thus the probability is 10/14.
|Tags||combinatorics, gvaibhav21, insomnia18, maths|
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, kotlin, PERL6, TEXT, SCM chicken, PYP3, CLOJ, COB, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.