백준 13182 제비

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

13182번: 제비

열심히 식을 정리하면 되는 문제이다. Trivial 하게 $D_{r, g, b, k}$를 정의하자. 이때 다음 식을 세울 수 있다.

$$D_{r, g, b, k}={r \over r+g+b}D_{r-1, g, b, k}+{g \over r+g+b}D_{r, g, b, k}+{b \over r+g+b}D_{r, g, b, k-1}+1$$

위 점화식을 조금 정리하면 아래와 같다.

$$D_{r, g, b, k}={r \over r+b}D_{r-1, g, b, k}+{b \over r+b}D_{r, g, b, k-1}+{r+g+b \over r+b}$$

그렇게 복잡해보이지 않는 꼴이지만, $r$과 $k$가 함께 변하므로 한 번에 일반항을 구하기에는 어려움이 있다. 조금 더 관찰을 추가하자. 처음 관찰할 수 있는 사실은 $D_{r, g, b, 0}=0$이라는 점이다. 하지만 $D_{0, g, b, k}$의 값은 자명하지 않다. 우선 $D_{0, g, b, k}$를 구해보자. 식을 세우면 아래와 같다.

$$D_{0, g, b, k}={g \over g+b}D_{g, b, k}+{b \over g+b}D_{g, b, k-1}+1$$

이를 통해 $D_{0, g, b, k}={g+b \over b}k$임을 확인할 수 있다.

위 과정을 $r$을 늘려가며 반복하면 모든 일반항을 구할 수 있을 것이다. $r=1$을 대입하자.

$$D_{1, g, b, k}={1 \over 1+g+b}D_{0, g, b, k}+{g \over 1+g+b}D_{1, g, b, k}+{b \over 1+g+b}D_{1, g, b, k-1}+1$$

이때 미리 구해놓은 $D_{0, b, g, k}={g+b \over b}k$를 대입하여 정리하면 다음과 같은 식을 얻는다.

$$D_{1, g, b, k}={1 \over 1+b}{g+b \over b}k+{b \over 1+b}D_{1, g, b, k-1}+{1+g+b \over 1+b}$$

$k$에 대한 점화식으로 볼 수 있으므로 일반항을 구해보면, $D_{1, g, b, k}={g+b \over b}k+1-({b \over 1+b})^{k}$를 얻는다. 같은 방법으로 $D_{2, g, b, k}$를 구해보면, $D_{2, g, b, k}={g+b \over b}k+2-2({b \over 1+b})^{k}$를 얻을 수 있고, 이를 통해 유추해보면 $D_{r, g, b, k}={g+b \over b}k+r-r({b \over 1+b})^{k}$일 것이다.

 

해의 정당성은 수학적 귀납법으로 쉽게 보일 수 있다.

 

코드는 다음과 같다.

#include<stdio.h>
typedef long long ll;
const ll mod = 1000000007;

int t;
ll r, g, b, k;

ll pow(ll a, ll b){
    ll res = 1;
    while(b){
        if(b%2) res = (res*a)%mod;
        b /= 2;
        a = (a*a)%mod;
    }
    return res;
}

ll inv(ll a){
    return pow(a, mod-2);
}

int main(){
    scanf("%d", &t);
    while(t--){
        scanf("%lld %lld %lld %lld", &r, &g, &b, &k);
        ll res = (((g+b)*((k*inv(b))%mod))%mod+r)%mod;
        res = (res-(r*pow((b*(inv(b+1)))%mod, k))%mod+mod)%mod;
        printf("%lld\n", res);
    }
}