https://www.acmicpc.net/problem/13174

문제

올바른 괄호 문자열이란 다음과 같은 문자열의 집합이다.

• 빈 문자열은 올바른 괄호 문자열이다.
• S가 올바른 괄호 문자열이면 (S)도 올바른 괄호 문자열이다. 즉 올바른 괄호 문자열의 앞에 여는 괄호를 붙이고 뒤에 닫는 괄호를 붙여도 올바른 괄호 문자열이다.
• S와 T가 올바른 괄호 문자열이면 ST도 올바른 괄호 문자열이다. 즉 올바른 괄호 문자열을 이어 붙여도 올바른 괄호 문자열이다.

그는 괄호 문자열을 매우 좋아한다. 하지만 괄호의 종류를 하나만 사용해왔던 것이 너무 재미가 없어서 서로 구별할 수 있는 K 개의 색을 괄호에 칠하기로 했다. 예를 들어 K = 3 이고 빨간색, 녹색, 파란색을 사용하기로 했다면 위의 정의에서 두 번째 부분이 아래처럼 확장된다.

• S가 올바른 괄호 문자열이면 (S), (S), (S)도 올바른 괄호 문자열이다. 즉 올바른 괄호 문자열의 앞에 여는 괄호를 붙이고 뒤에 닫는 괄호를 붙여도 올바른 괄호 문자열이다.

K 가 더 늘어나면 구별 가능한 색을 더 추가해서 정의를 확장하면 된다. 이제 2N 개의 괄호를 사용하여 만든 올바른 문자열 중에서 자기 자신과 자기 자신을 뒤집은 문자열이 같은 것들의 개수를 구하는 프로그램을 작성하라. 어떤 문자열을 뒤집는다는 것은 문자열을 거울에 비춘 다음 거울에 비친 모양대로 적는다는 것과 같다. 예를 들어 (())()를 뒤집으면 ()(())가 될 것이다. 이 문자열은 자기 자신과 뒤집은 문자열이 같지 않으므로 세면 안 된다. ()(())()는 뒤집어도 똑같이 ()(())()가 될 것이므로 개수를 세어야 한다.

입력

첫 번째 줄에는 사용하는 괄호의 개수와 괄호의 색을 나타내는 두 자연수 N, K 가 공백으로 구분되어 주어진다. (1 ≤ N ≤ 10⁶, 1 ≤ K ≤ 10⁶)

출력

K 종류의 괄호를 2N 개 사용해 올바른 괄호 문자열을 만들었을 때, 자기 자신과 자기 자신을 뒤집은 문자열이 같은 것들의 개수를 출력한다. 이 수는 매우 커질 수 있으므로 1,000,000,007로 나눈 나머지를 출력해야 한다.

풀이

먼저, 어차피 구하려는 문자열이 좌우 대칭이므로 길이가 $n$인 왼쪽 절반만 고려하자.

올바른 괄호 문자열을 만드는 경우의 수와 각각의 경우에 대해 색을 입히는 경우의 수를 조합하여 풀 수 있는 문제이다.

색을 입히는 경우의 수는 왼쪽 절반에 존재하는 여는 괄호의 수 $k$에 대해 $K^k$임을 알 수 있다. 올바른 괄호 문자열의 수를 $k$에 대한 식으로 구할 수 있으면 for문 하나로 풀 수 있을 것이다.

길이가 $n$인 문자열 중 여는 괄호 (의 수가 $k$인 것 중 적절한 문자열의 수를 $S(n, k)$라고 하자. 여기서 적절한 문자열이란 오른쪽에 대칭으로 붙였을 때 올바른 괄호 문자열이 나오는 것으로, 왼쪽부터 한 글자씩 읽었을 때 )의 수가 (의 수보다 항상 적어야 함을 알 수 있다.

길이가 $n-1$인 적절한 문자열의 맨 뒤에 ( 또는 )를 붙여 길이가 $n$인 문자열을 만들 수 있다.

• (를 붙이는 경우

적절한 문자열 뒤에 (를 붙이면 항상 적절한 문자열이 된다.

• )를 붙이는 경우

(와 )의 수가 같은 문자열의 뒤에 )를 붙이면 적절하지 않은 문자열이 된다. 이 경우를 제외하면 항상 적절한 문자열이 된다.

위를 바탕으로 식을 세우면 다음과 같다.

식 1이 이항 계수와 매우 유사하다. 이항 계수를 선형 결합하여 식 2를 만족하는 해를 찾아보자.

$\binom{2n}{n} = \binom{2n-1}{n} + \binom{2n-1}{n-1} = 2 \binom{2n-1}{n}$를 바탕으로 비슷한 이항 계수를 가지고 끼워 맞춰보면 $\binom{2n}{n} - \binom{2n}{n+1} = \binom{2n-1}{n} - \binom{2n-1}{n+1}$를 찾을 수 있다.

즉 $S(n, k) = \binom{n}{k} - \binom{n}{k+1}$는 위 두 식을 모두 만족한다. 이미 해를 아는 경우를 대입해 이 식이 맞는지 확인해보자. )가 하나만 존재하는 경우 총 $n-1$개의 경우의 수가 존재한다. $S(n, n-1) = \binom{n}{n-1} - \binom{n}{n} = n-1$이다.

해가 맞는 것으로 보이니 풀어보자. 색을 입히는 경우의 수가 $K^k$이므로 전체 경우의 수는 다음과 같다.

for문으로 k를 순회하며 이를 전부 더해주면 된다. 이때, $k$가 $n$의 절반을 넘을 때만 올바른 괄호 문자열이 만들어질 수 있으므로 그때만 더해야 한다. $\binom{n}{k+1} = \frac{n-k}{k+1} \binom{n}{k}$임을 이용하면 for문 하나로 전부 처리할 수 있다.

1,000,000,007은 소수이므로 모듈러 역원을 쉽게 이용할 수 있다. 백준 13977 - 이항 계수와 쿼리와 같이 분할정복을 이용한 거듭제곱을 통해 모듈러 역원을 $O(\log{n})$에 구할 수 있다.

코드

#include <bits/stdc++.h>
#define p 1000000007
#define ll long long
using namespace std;
ll modinv(ll base){
    ll pow = p - 2, result = 1;
    while (pow){
        if (pow & 1) result = (result * base) % p;
        base = (base * base) % p;
        pow >>= 1;
    }
    return result;
}
int main(){
    int n, k; cin >> n >> k;
    ll kp = 1, nck = 1, nckp1, result = 0;
    for (int i = 0; i <= n; i++){
        nckp1 = ((nck * (n - i)) % p * modinv(i + 1)) % p;
        if (2 * i >= n) result = (result + kp * (nck - nckp1 + p)) % p;
        nck = nckp1;
        kp = (kp * k) % p;
    }
    cout << result;
}