BOJ 15309 스킬 트리

📝 문제 정보

#

• 링크: https://www.acmicpc.net/problem/15309

🧐 관찰 및 접근

#

• 이진트리..는 아니고 삼각형이구나. 걍 좀 펴서 생각하면, 이항계수처럼 생각하면 되는 것 같다.
• $i$번째 줄은 $(Ax + B)^i$ 의 계수처럼 생각하면 되는듯?
  • 아 근데 그 뭐냐 겹치게 하면 안되는구나
• 특정 삼각형은 그 초항만 생각하면 되는것같으니까, $m$개의 행을 포함하는 정삼각형을 어떻게 계산할지 생각해보자.
  • 대충 로그정도에 계산하면 되는데.. 일단 초항이 1일때 식은 뭐랑 같지?
  • $1 + (A+B) + (A^2 + AB + B^2) + \cdots$
  • 같은 느낌인건데… 어차피 행 자체에는 누적합 맛으로 할 수 있겠네.
    • 어라? 이건 그냥 윗 행에다가 $A$를 곱하고, $B^N$만 더하면 될거같은딩. 대충 해버리죠?
    • 아니 잠깐만!!!!!!!!! $m$이 $10^{18}$이다!! 비상!!!!!!!!!
      • 로그가 붙을만한곳은 분할정복 거듭제곱같은거밖에 없는데…
  • 아 잠깐만. 이거 그냥 그 유명한 고딩때 그 공식처럼 $(A-B)$곱하면 정리되는 꼴 아닌가?
  • 그러면 $(A-B) + (A^2 - B^2) + (A^3 - B^3) + \cdots$
    • 이건 $(A + A^2 + \cdots + A^m) - (B + B^2 + \cdots + B^m)$이자나!
    • $\frac{A^{m+1} - 1}{A-1} - \frac{B^{m+1} - 1}{B-1}$ 로 계산할 수 있을 것 같고, 이걸 $A-B$로 나눠서 끝내자.
• 아!! $A = B$인 경우를 조심해야할 것 같고, $A = 1$이나 $B = 1$인경우도 조심해야할 것 같다.
  • $A = B$라면? $1 + 2A + 3A^2 + \cdots + mA^{m-1}$ 를 구해야하는데,
    • 저 합을 $S$라고 하자. 그러면 $AS - S = 1 + A + A^2 + \cdots + A^m$ 니까, $A = 1$인 경우 말고는 이걸 구해서 $A-1$로 나누면 될 것 같은데?
• 케이스 처리를 조심하자.

💻 풀이

#

• 코드 (C++):

void solve(){
    mint A, B; cin >> A >> B;

    int Q; cin >> Q;
    while(Q--){
        ll x, y, m; cin >> x >> y >> m;
        x--; y--;
        mint cho = 1;
        cho *= A.pow(x-y);
        cho *= B.pow(y);
        
        mint trig = 0;

        if(A == B){
            if(A == 1) trig = mint(m)*(m+1)/2;
            else trig = (A.pow(m+1) - 1) / (A - 1).pow(2);
        }
        else{
            if(A == 1) trig += m;
            else trig += (A.pow(m+1) - 1) / (A - 1) - 1;
            if(B == 1) trig -= m;
            else trig -= (B.pow(m+1) - 1) / (B - 1) - 1;
            trig /= (A-B);
        }

        cout << cho * trig << '\n';
    }
}