To solve this problem, we need to compute the number of valid parentheses sequences of length 2n, which is given by the nth Catalan number. Catalan numbers are a sequence of natural numbers that have many applications in combinatorial mathematics, including counting valid parentheses sequences.

Approach

The nth Catalan number can be efficiently computed using its closed-form formula: [ C_n = \frac{1}{n+1} \binom{2n}{n} ] where (\binom{2n}{n}) is the binomial coefficient.

To avoid large intermediate values and ensure integer division (since Catalan numbers are integers), we compute the result iteratively:

1. Start with a result of 1.
2. For each i from 1 to n, update the result by multiplying with ((n+i)) and dividing by i (integer division).
3. Finally, divide the result by ((n+1)) to get the nth Catalan number.

Solution Code

n = int(input())
if n == 0:
    print(1)
else:
    catalan = 1
    for i in range(1, n + 1):
        catalan = catalan * (n + i) // i
    catalan = catalan // (n + 1)
    print(catalan)

Explanation

• Base Case: For n=0, the number of valid sequences is 1 (empty sequence).
• Iterative Calculation: For each i from 1 to n, we compute the product of terms (\frac{n+i}{i}) and then divide by ((n+1)) to get the Catalan number. This approach ensures that we use integer division to maintain correctness and avoid floating-point errors.

This method efficiently computes the Catalan number even for larger values of n, leveraging Python's ability to handle big integers without overflow.

Examples:

• n=1 → Output: 1 (sequence: "()")
• n=2 → Output: 2 (sequences: "()()", "(())")
• n=3 → Output:5 (sequences: "()()()", "()(())", "(())()", "(()())", "((()))")

This solution is optimal and runs in O(n) time complexity, which is efficient for the problem constraints.

作者声明:本文包含人工智能生成内容。