[BOJ 13174] 괄호

각각의 $n$에 대하여 대칭 축을 기준으로 왼쪽에 $k$쌍의 괄호가 존재하는 경우의 수를 $h(n,k)$로 정의하자. 그럼 다음이 성립한다.

\[h(n,k)=h(n-1,k-1)+h(n-1,k)\]

\[h(n,k)=0\ \ k<0\]

\[h(1,0)=1\]

증명은 직접 그려보며 이해하면 쉽다. $N$번째 괄호 대칭 문자열을 $S$라고 하고 중심축의 왼쪽 문자열을 $S1$ 중심축 오른쪽 문자열을 $S2$라고 하자. 즉, $S=S1|S2$이다. $S$는 중심축의 왼쪽에 정확히 $k$쌍의 괄호를 포함한다. 그럼 $(S)$ 역시 중심축의 왼쪽에 $k$쌍의 괄호를 포함한다. 이것이 바로 항 $h(n-1,k)$를 의미한다. $S1)|(S2$를 생각해보자. 이는 축의 양쪽에 괄호 쌍의 개수를 1개 늘려준다. 이것이 항 $h(n-1,k-1)$을 의미하는 것이다.

색깔이 $K$개가 주어졌다고 하자. 만약 대칭 축 기준으로 왼쪽에 $k$쌍의 괄호가 있다면 색칠하는 경우의 수는 $K^{n-k}$가 된다. 그럼 $K^{n-k}h(n,k)$를 모두 더하는 것이 우리가 원하는 답이다. 이것을 $s(n)$이라 하자. 또한 어떤 $n$에 대해 대칭 축 기준으로 한쪽에만 존재할 수 있는 최대의 괄호 쌍의 개수를 $L(n)$이라 정의하자.

\[s(n)=\sum_{i=0}^{L(n)} K^{n-i}h(n,i)\]

또한 $L(2n)=L(2n+1)=n$이라는 사실을 쉽게 알 수 있다.

\[s(2n+1)/K=\sum_{i=0}^{n}K^{2n-i}h(2n+1,i)\]

\[s(2n)=\sum_{i=0}^{n}K^{2n-i}h(2n,i)\]

\[s(2n+1)/K-s(2n)=\sum_{i=0}^{n} K^{2n-i}h(2n,i-1)=\sum_{i=0}^{n} K^{2n-1-i}h(2n,i)=s(2n)/K-K^{n-1}h(2n,n)\]

\[s(2n+1)=(K+1)s(2n)-K^{n}h(2n,n)\]

다음에 대해서도 살펴보자.

\[s(2n)=\sum_{i=0}^{n}K^{2n-i}h(2n,i)\]

\[ks(2n-1)=\sum_{i=0}^{n-1}K^{2n-i}h(2n-1,i)\]

\[s(2n)-ks(2n-1)=K^{n}h(2n,n)+\sum_{i=0}^{n-1} K^{2n-i}h(2n-1,i-1)\]

\[=K^{n}h(2n,n)+\sum_{i=0}^{n-2} K^{2n-1-i}h(2n-1,i)=s(2n-1)+K^{n}h(2n,n)-K^{n}h(2n-1,n-1)\]

$h(2n,n)$의 의미를 알아보자. 이는 중심축을 기준으로 좌우 각각 $n$개의 괄호들이 위치함을 알 수 있다.  한 쪽에 괄호를 배치하면 다른 쪽 괄호의 배치는 저절로 정해진다. 괄호를 올바르게 배열하는 경우의 수는 $C_{n}$(카탈란 수)이다. 따라서 $h(2n,n)=h(2n-1,n-1)=C_{n}$임을 알 수 있다.

\[s(2n)=(K+1)s(2n-1)\]

\[s(2n+1)=(K+1)s(2n)-K^{n}C_{n}=(K+1)^{2}s(2n-1)-K^{n}C_{n}\]

점화식 해결을 위해 양 변을 $(K+1)^{2n}$으로 나누자.

\[\frac{s(2n+1)}{(K+1)^{2n}}=\frac{s(2n-1)}{(K+1)^{2n-2}}-\left(\frac{K}{(K+1)^{2}}\right)^{n}C_{n}\]

\[b_{n}=\frac{s(2n+1)}{(K+1)^{2n}}\]

\[b_{n}=b_{n-1}-\left(\frac{K}{(K+1)^{2}}\right)^{n}C_{n}\]

\[b_{n-1}-b_{n}=\left(\frac{K}{(K+1)^{2}}\right)^{n}C_{n}\]

\[K-b_{n}=\sum_{i=1}^{n} \left(\frac{K}{(K+1)^{2}}\right)^{i}C_{i}\]

\[b_{n}=K-\sum_{i=1}^{n}\left(\frac{K}{(K+1)^{2}}\right)^{i}C_{i}\]

\[\therefore s(2n+1)=K(K+1)^{2n}-\sum_{i=1}^{n} K^{i} (K+1)^{2n-2i} C_{i}\]

이것은 $O(n\log(n))$으로 해결할 수 있다. 

 

# 코드 보기

#include<stdio.h>
typedef long long ll;
ll mod=1e9+7;
ll fpow(ll n,ll k){
    ll s=1;
    for(;k;k>>=1){
        if(k&1) s=s*n%mod;
        n=n*n%mod;
    }
    return s;
}
int main(){
    ll i,n,ans=0,K,card=1,end;
    scanf("%lld %lld",&n,&K);
    end=n/2;
    if(n%2==0) end-=1;
    ans=K*fpow(K+1,2*end)%mod;
    for(i=1;i<=end;i++){
        ll t=fpow(K+1,2*end-2*i)*fpow(K,i)%mod*card%mod;
        card=card*(4*i+2)%mod*fpow(i+2,mod-2)%mod;
        ans-=t;
        ans%=mod;
    }
    if(n%2==0) ans=(K+1)*ans%mod;
    printf("%lld",(ans+mod)%mod);
}

# 닫기

 

*(번외) 만약 $K=1$이라면 어떻게 될까?

\[\mathbf{Claim.} \ \ \ s(2n+1)={2n+1 \choose n}\]

\[n=1\ \ \  4-C_{1}=3={3 \choose 1}\]

$n=k$일 때 claim이 성립한다 가정하자. 그럼 다음과 같다.

\[4^{k}-(4^{k-1}C_{1}+4^{k-2}C_{2}+...+C_{k})={2k+1 \choose k}\]

양 변에 4를 곱한 후 $C_{k+1}$을 빼자.

\[4^{k+1}-(4^{k}C_{1}+4^{k-1}C_{2}+...+4C_{k}+C_{k+1})=4{2k+1 \choose k}-C_{k+1}\]

\[RHS=\frac{4(2k+1)!}{k!(k+1)!}-\frac{(2k+2)!}{(k+1)!(k+1)!(k+2)}\]

\[=\frac{(2k+1)!}{(k+1)!}\cdot \frac{4k+6}{k+2}\]

\[=\frac{(2k+3)!}{(k+2)!(k+1)!}={2k+3 \choose k+1}\]

수학적 귀납법에 의해 증명 되었다. $K=1$이 아닐 경우에 뭐가 될까요? 증명하신 분은 연락 주세여^^