[백준 10422] 괄호 (C++)

문제 링크: https://www.acmicpc.net/problem/10422

10422번: 괄호

1. 주의할 점

- 카탈란 수에 대해 알고 있어야 한다

- 입력받는 수가 홀수인 경우 0을 출력하고, 짝수인 경우 반으로 나눈 후 진행한다

- 페르마 소정리에 대해 알고 있어야 한다

- 시간복잡도를 Lg(N)으로 줄여야 한다

 

페르마 소정리에 대해 모르는 경우 11401의 해설에 적힌 페르마 소정리에 대해 이해한다

문제 링크: https://imnotabear.tistory.com/98

[백준 11401] 이항 계수 3 (C++)

 

2. 구현

- 괄호와 관련된 카탈란 수의 경우, 짝이 N개인 괄호를 통해 2nCn/(n+1)만큼의 올바른 괄호 문자열을 만들 수 있다

- 페르마의 소정리를 사용해 {2nCn/(n+1)} % MOD를 변형시킨다

{2nCn/(n+1)} % MOD

-> (2n)! % MOD / [{(n+1)! % MOD} * {n! % MOD}] %MOD

-> {(2n)! % MOD}*  [{(n+1)! % MOD} * {n! % MOD}]^(MOD-2) % MOD가 성립한다

- Factorial을 구하는 함수는 테스트 케이스가 돌때마다 하면 시간 낭비 -> 따로 빼서 구한다

- Pow를 구하는 함수는 Math.h 헤더에 있는 것을 사용할 경우, 지수만큼의 시간복잡도가 소요되서 TLE가 발생할 수 있다 -> Lg(지수) 의 시간복잡도가 소요되도록 Pow함수를 구현한다. 

#include <iostream>
using namespace std;

long long MOD = 1000000007, result;
long long fact[10001];

long long pow(long long val, long long idx) {
	if (idx == 0) return 1;
	else if (idx == 1) return val;
	if (idx % 2 == 0) {
		long long temp = pow(val, idx / 2);
		temp *= temp;
		temp %= MOD;
		return temp;
	}
	else {
		long long temp = pow(val, idx - 1);
		temp *= val;
		temp %= MOD;
		return temp;
	}
}

int main() {
	int test, len;
	cin >> test;
	fact[0] = 1;
	for (int i = 1; i <= 10000; i++) {
		fact[i] = fact[i - 1] * i;
		fact[i] %= MOD;
	}

	for (int i = 0; i < test; i++) {
		cin >> len;
		if (len % 2 == 1) {
			cout << 0 << '\n';
			continue;
		}
		len /= 2;
		long long up = fact[2 * len];
		long long down = fact[len + 1];
		down *= fact[len];
		down %= MOD;
		result = up * pow(down, MOD - 2);
		cout << result % MOD << '\n';
	}
	system("pause");
	return 0;
}