백준 10422 - 괄호

www.acmicpc.net/problem/10422

 

짝이 맞는 괄호의 개수는 카탈란 수의 잘 알려진(Well Known) 예시 중 하나이다.

 

카탈란 수에 대해 자세한 정보는 이 글에 있으며

 

$\binom{2n}{n} - \binom{2n}{n - 1} = \frac{1}{n + 1} \binom{2n}{n} = \frac{(2n)!}{(n + 1)!n!}$

 

다음과 같이 3개의 식으로 사용할 수 있다.

 

이 문제에서는 1,000,000,007로 나눈 나머지를 구해야 하므로 페르마의 소정리를 활용하기 위해 3번째 식을 이용했다.

 

주의 사항은 n쌍이 아니라 n개가 입력으로 주어지므로 괄호의 개수가 홀수개일 때는 괄호 짝이 절대 만들어지지 않는다는 점과 짝수개가 주어지면 이를 괄호의 짝 개수로 치환하기 위해 2로 나눠야 한다는 점을 생각하여 구현해야 한다.

 

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

ll mod = 1e9 + 7;

ll fact[5001];

ll pomod(ll a, int b);

int main()
{   
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    
    fact[0] = 1;
    for (int i = 1; i <= 5000; ++i)
        fact[i] = fact[i - 1] * i % mod;
    
    int t; cin >> t;
    
    while (t--)
    {
        int x; cin >> x;
        if (x & 1)
            cout << "0\n";
        else
            cout << fact[x] * pomod(fact[x / 2] * fact[x / 2 + 1] % mod, mod - 2) % mod << '\n';
    }
}

ll pomod(ll a, int b)
{
    if (b == 1)
        return a % mod;
    
    if (b & 1)
        return pomod(a, b - 1) * a % mod;
    
    return pomod(a * a % mod, b / 2);
}

 

요구 사항을 주의깊게 읽지 않아 정답률을 허공에 날려버렸다.