[BOJ 13430] 합 구하기

이 문제에서 구하려는 함수는 다음과 같다.

함수 $S$는 다음과 같이 정의된다.

• $S(0,\ n) = n$ (모든 양의 정수 $n$)
• $S(k,\ n) = S(k-1,\ 1) + S(k-1,\ 2) + ... + S(k-1,\ n)$ (모든 양의 정수 $k,\ n$)

 

이때 $S(k, n)$을 적절히 변형시켜보자.

$S(k,\ n) = S(k-2,\ 1) + [S(k-2,\ 1) + S(k-2,\ 2)] + [S(k-2,\ 1)+S(k-2,\ 2)+S(k-2,\ 3)] + ...$

$= nS(k-2,\ 1) + (n-1)S(k-2,\ 2) + (n-2)S(k-2,\ 3) + ...$

정의에 의해서

$= nS(k-3,\ 1) + (n-1)[S(k-3,\ 1)+S(k-3,\ 2)] + (n-2)[S(k-3,\ 1)+S(k-3,\ 2)+S(k-3,\ 3)]+...$

각 계수를 조합으로 적절히 변형시켜주면

$=_{n}\mathrm{C}_{1}\ S(k-3,\ 1)+_{n-1}\mathrm{C}_{1}\ [S(k-3,\ 1)+S(k-3,\ 2)] +_{n-2}\mathrm{C}_{1}\ [S(k-3,\ 1)+S(k-3,\ 2)+S(k-3,\ 3)]+...$

하키스틱 정리를 적용하면

$=_{n+1}\mathrm{C}_{2}\ S(k-3,\ 1)+_{n}\mathrm{C}_{2}\ S(k-3,\ 2) +_{n-1}\mathrm{C}_{2}\ S(k-3,\ 3)+...$

위와 같은 과정을 반복하면

$=_{n+p}\mathrm{C}_{p+1}\ S(k-p-2,\ 1)+_{n+p-1}\mathrm{C}_{p+1}\ S(k-p-2\ ,2) +_{n+p-2}\mathrm{C}_{p+1}\ S(k-p-2,\ 3)+...$

$k-p-2=0$이라고 한다면 $p=k-2$이다.

이때 식은

$=_{n+k-2}\mathrm{C}_{k-1}\ S(0,\ 1)+_{n+k-3}\mathrm{C}_{k-1}\ S(0\ ,2) +_{n+k-4}\mathrm{C}_{k-1}\ S(0,\ 3)+...$

정의에 의해

$=_{n+k-2}\mathrm{C}_{k-1}+2_{n+k-3}\mathrm{C}_{k-1} +3_{n+k-4}\mathrm{C}_{k-1}+...$

이것은 조합의 뒷 숫자가 $k-1$인 것들의 합이므로 하키스틱 정리를 이용할 수 있다. 조합의 앞 숫자가 $k-1$인 것이 $n$개 존재하므로 조합의 앞 숫자가 $k-1$인 것부터 $n+k-2$까지, $k-1$인 것부터 $n-k-3$까지 ... 이런 방식으로 따로 따로 하키스틱 정리를 적용시킬 수 있다. 이를 적용하면

$=_{n+k-1}\mathrm{C}_{k}+_{n+k-2}\mathrm{C}_{k} +_{n+k-3}\mathrm{C}_{k}+...$

다시 하키스틱 정리를 적용하면

$=_{n+k}\mathrm{C}_{k+1}$

$\therefore S(n,\ k) =_{n+k}\mathrm{C}_{k+1}$

이제 조합을 계산하기만 하면 끝!

 

코드는 다음과 같다.

 

코드 보기

#include<stdio.h>
typedef long long int lo;
lo p=1e9+7;
lo pow(lo n,lo k){
    lo s=1,h=n;
    for(;k;k>>=1){
        if(k&1) s=s*h%p;
        h=h*h%p;
    }
    return s;
}
lo fac(lo n){
    lo s=1,i;
    for(i=1;i<=n;i++){
        s=s*i%p;
    }
    return s;
}
int main(){
    lo n,k,s=1,i;
    scanf("%lld %lld",&k,&n);
    for(i=n;i<=n+k;i++){
        s=s*i%p;
    }
    s=s*pow(fac(k+1),p-2)%p;
    printf("%lld",s);
}