백준 13182번: 제비

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

13182번: 제비

---

이 문제 아주 어렵습니다...

 

일반항을 안 다음부터 구현 난이도는 너무 쉬운데

 

그 과정의 난이도만으로도 과거 루비5, 현재 다이아1에 위치합니다.

 

이 문제는 제 4회 kriiicon 에 출제된 문제이고, 같은 대회에 있던 문제 중에 제가 다룬 문제들은 다음과 같습니다.

2021.07.31 - [분할 정복을 이용한 거듭제곱/정수 거듭제곱] - 백준 13173번: Ω

2021.02.18 - [분할 정복을 이용한 거듭제곱/정수 거듭제곱] - 백준 13172번: Σ

2021.01.23 - [분할 정복을 이용한 거듭제곱/정수 거듭제곱] - 백준 13171번: A

 

대충 뭔가 분할정복을 이용해서 거듭제곱 좀 하고, 기댓값은 점화식을 세워서 풀어야 할 것 같습니다.

 

13173번에서는

 

현재 가진 숫자가 $i$ 일 때 확률 $p_{i}$

 

라고 정의하여 정의에 따라 점화식을 세우고 풀었습니다.

 

제비에서도 이런 과정을 거쳐야겠죠.

---

 

일단 빨간 제비가 뽑히면 그 제비는 버리기 때문에, 당연히 빨간 제비의 개수가 중요한 변수가 됩니다.

 

또한 파란 제비가 $K$ 번 뽑히면 게임이 중단되기 때문에, $K$ 번 뽑을 때까지 남은 횟수도 중요합니다.

 

그래서 다음과 같은 함수를 정의할 수 있겠습니다.

 

$D\left( r,k \right)\;\;$ : 빨간 제비가 $r$ 개 남아있고 파란 제비를 앞으로 $k$ 회 더 뽑아야 게임이 종료될 때

게임이 끝날 때까지 제비를 뽑는 횟수의 기댓값

 

이렇게 정의하면 점화관계는 어떻게 될까요?

 

우선 지문에 적힌대로, 초록 제비의 수는 $G$ 로, 파랑 제비의 수는 $B$ 로 하겠습니다.

 

$D\left( r,k \right)$ 의 상황에서

 

$\left( 1 \right)$ 빨간 제비가 뽑힐 확률은 $\frac{r}{r+G+B}$ 이고 이 경우 $D\left( r-1, k \right)$ 로 전이합니다.

 

$\left( 2 \right)$ 초록 제비가 뽑힐 확률은 $\frac{G}{r+G+B}$ 이고 이 경우 $D\left( r,k \right)$ 를 유지합니다.

 

$\left( 3 \right)$ 파란 제비가 뽑힐 확률은 $\frac{B}{r+G+B}$ 이고 이 경우 $D\left( r,k-1 \right)$ 로 전이합니다.

 

$\left( 4 \right)$ 마지막으로 $1\sim 3$ 의 상태변화를 위해 제비를 반드시 한 번 뽑아야 합니다.

 

따라서 점화관계가 다음과 같음을 알 수 있습니다.

 

$D\left( r,k \right)=\frac{rD\left( r-1,k \right)+GD\left( r,k \right)+BD\left( r,k-1 \right)}{r+G+B}+1$

 

이 점화관계를 다음 과정을 거쳐 풀 수 있습니다.

 

$D\left( r,k \right)=\frac{rD\left( r-1,k \right)+GD\left( r,k \right)+BD\left( r,k-1 \right)}{r+G+B}+1$

 

$\leftrightarrow \left( 1-\frac{G}{r+G+B} \right) D\left( r,k \right)=\frac{rD\left( r-1,k \right)+BD\left( r,k-1 \right)}{r+G+B}+1$

 

$\leftrightarrow D\left( r,k \right)=\frac{rD\left( r-1,k \right)+BD\left( r,k-1 \right)}{r+B}+\frac{r+G+B}{r+B}$

 

$\leftrightarrow D\left( r,k \right)=\frac{rD\left( r-1,k \right)+BD\left( r,k-1 \right)}{r+B}+1+\frac{G}{r+B}$

 

또한 정의에 의해 $D\left( r,0 \right)=0$ 입니다.

 

$D\left( 0,k \right)$ 값의 경우 $G$ 에 의해 달라져 아직은 알기 어렵군요.

 

이정도 점화식이면, 그래도 $R\;G\;B\;K$ 의 범위가 적당하다면 나이브한 DP를 써도 되겠습니다만...

 

아무래도 일반항을 구해봐야 할 것 같습니다.

---

 

그에 앞서, 우리가 처음부터 모든 $R\;G\;B\;K$ 값에 대해 위 문제를 해결하려 하는 것은 과히 어렵습니다.

 

그래서 쉬운 케이스부터 할 텐데, 우선 $G=0$ 인 케이스를 보겠습니다.

 

그리고 $G=0$ 인 케이스의 $D\left( r,k \right)$ 를 $D_{1}\left( r,k \right)$ 로 정의하고,

 

$G>0$ 인 케이스의 $D\left( r,k \right)$ 를 $D_{2}\left( r,k \right)$ 로 정의하겠습니다.

 

그렇다면 $D\left( r,k \right)=D_{1}\left( r,k \right)+D_{2}\left( r,k \right)$ 이 됩니다.

 

한편 $G=0$ 에서 자연스럽게 $D_{1}\left( r,k \right)=\frac{rD_{1}\left( r-1,k \right)+BD_{1}\left( r,k-1 \right)}{r+B}+1$ 이고

 

$D_{1}$ 과 $D_{2}$ 의 합이 $D$ 인 성질을 이용하면 $D_{2}=\frac{rD_{2}\left( r-1,k \right)+BD_{2}\left( r,k-1 \right)}{r+B}+\frac{G}{r+B}$ 를 얻습니다.

---

이제 $D_{1}\left( r,k \right)$ 을 풀 차례입니다.

 

하지만 여전히 변수가 두 개라서 접근이 난해합니다.

 

일단 $r=1$ 인 케이스에 대해 생각해보겠습니다.

 

이 경우 $D_{1}\left( 1,k \right)=\frac{D_{1}\left( 0,k \right)+BD_{1}\left( 1,k-1 \right)}{1+B}+1$ 입니다.

 

그런데 $G=0$ 인 상황을 고려하면 $D_{1}\left( 0,k \right)=k$ 임이 자명합니다.

 

따라서 $D_{1}\left( 1,k \right)=\frac{k+BD_{1}\left( 1,k-1 \right)}{1+B}+1$ 입니다.

 

한편 정의에 따르면 $D_{1}\left( 1,0 \right)=0$ 입니다. 이를 바탕으로 몇 가지 케이스에 대해 계산해보면 $\cdots$

 

$D_{1}\left( 1,1 \right)=\frac{1+BD_{1}\left( 1,0 \right)}{1+B}+1=\frac{1}{1+B}+1$

 

$D_{1}\left( 1,2 \right)=\frac{2+BD_{1}\left( 1,1 \right)}{1+B}+1=\frac{2+B\left( 1+\frac{1}{1+B} \right)}{1+B}+1=\frac{\left( B+1 \right)\left( B+2 \right) + B}{\left( B+1 \right)^{2}}+1=\frac{2B+1}{\left( B+1 \right)^{2}}+2$

 

$D_{1}\left( 1,3 \right)=\frac{3+BD_{1}\left( 1,2 \right)}{1+B}+1=\frac{3+\frac{2B^{2}+B}{\left( B+1 \right)^{2}}+2B}{1+B}+1=\frac{3\left( B+1 \right)^{2}+2B^{2}+B+2B\left( B+1 \right)^{2}}{\left( B+1 \right)^{3}}+1$

$\;\;\;\;\;\;\;\;\;\;\;\;\;=\frac{\left( B+1 \right)^{2}+2B^{2}+B}{\left( B+1 \right)^{3}}+3=\frac{3B^{2}+3B+1}{\left( B+1 \right)^{3}}+3$

 

어쩌면 분자의 형태가 낯이 익을 수도 있습니다. 다음 형태를 캐치하셨어야 합니다. ($k=0$ 인 경우도 같은 패턴입니다!)

 

$D_{1}\left( 1,1 \right)=1+1-\frac{B}{1+B}$

 

$D_{1}\left( 1,2 \right)=2+1-\left( \frac{B}{1+B} \right)^{2}$

 

$D_{1}\left( 1,3 \right)=3+1-\left( \frac{B}{1+B} \right)^{3}$

 

수학적 귀납법으로 $D_{1}\left( 1,k \right)=k+1-\left( \frac{B}{1+B} \right)^{k}$ 임을 보이겠습니다. $\left( k\geq 0 \right)$

 

$\left( 1 \right)$ $0\leq k\leq 3$ 에서 성립함을 이미 보였습니다.

 

$\left( 2 \right)$ 자연수 $t$ 에 대해 $D_{1}\left( 1,t \right)=t+1-\left( \frac{B}{1+B} \right)^{t}$ 를 가정하겠습니다.

 

$\left( 3 \right)$ $\frac{t+1+BD_{1}\left( 1,t \right)}{1+B}+1=D_{1}\left( 1,t+1 \right)$ 을 보이면 됩니다.

 

$\frac{t+1+BD_{1}\left( 1,t \right)}{1+B}+1$

 

$\leftrightarrow \frac{t+1+B\left \{ t+1-\left( \frac{B}{1+B} \right)^{t} \right \}}{1+B}+1$

 

$\leftrightarrow \left( t+1 \right)+\frac{-B^{t+1}}{\left( 1+B \right)^{t+1}}+1$

 

$\leftrightarrow \left( t+1 \right)+1-\left( \frac{B}{1+B} \right)^{t+1} \leftrightarrow D_{1}\left( 1,t+1 \right)$

 

따라서 $D_{1}\left( 1,k \right)$ 을 구했습니다!

 

이제 $r=2$ 로 넘어가겠습니다.

---

$r=2$ 에서도 여전히 $D_{1}\left( 2,0 \right)=0$ 입니다.

 

그리고 $D_{1}\left( 2,k \right)=\frac{2D_{1}\left( 1,k \right)+BD_{1}\left( 2,k-1 \right)}{2+B}+1$ 이겠죠?

 

앞서 증명했듯이 $D_{1}\left( 1,k \right)=k+1-\left( \frac{B}{1+B} \right)^{k}$ 이고요.

 

이제 $k\leq 3$ 까지 계산해보겠습니다.

 

$D_{1}\left( 2,1 \right)=\frac{2D_{1}\left( 1,1 \right)+BD_{1}\left( 2,0 \right)}{2+B}+1=\frac{2\left(1+1-\frac{B}{1+B} \right)}{2+B}+1=\frac{2}{2+B}+1$

 

$D_{1}\left( 2,2 \right)=?$

 

$D_{1}\left( 2,2 \right)=\frac{2D_{1}\left( 1,2 \right)+BD_{1}\left( 2,1 \right)}{2+B}+1$

 

$=\frac{2\left( 2+\frac{2B+1}{\left( B+1 \right)^{2}}\right)+B\left( 1+\frac{2}{1+B} \right)}{2+B}+1$

 

$=\frac{4\left( 1+B \right)^{2}+2\left( 2B+1 \right)+B\left( 1+B \right)^{2}+2B\left( 1+B \right)}{\left( 2+B \right) \left( 1+B \right)^{2} }+1$

 

$=\frac{B^{3}+8B^{2}+15B+6}{\left( 2+B \right) \left( 1+B \right)^{2} }+1=\frac{B^{2}+6B+3}{\left( 1+B \right)^{2}}+1$

 

$=\frac{2\left( 2B+1 \right)}{\left( 1+B \right)^{2}}+2$

 

$D_{1}\left( 2,3 \right)=?$

 

$D_{1}\left( 2,3 \right)=\frac{2D_{1}\left( 1,3 \right)+BD_{1}\left( 2,2 \right)}{2+B}+1$

 

$=\frac{2\left( 3+\frac{3B^{2}+3B+1}{\left( B+1 \right)^{3}}\right)+B\left( 2+\frac{2\left( 2B+1 \right)}{ \left( 1+B \right)^{2}} \right)}{2+B}+1$

 

$=\frac{6\left( 1+B \right)^{3}+2\left( 3B^{2}+3B+1 \right)+2B\left( 1+B \right)^{3}+2B\left( 1+2B \right)\left( 1+B \right)}{\left( 2+B \right) \left( 1+B \right)^{3} }+1$

 

$=\frac{2\left( 1+B \right)^{3}+2\left( 3B^{2}+3B+1 \right)+2B\left( 1+2B \right)\left( 1+B \right)}{\left( 2+B \right) \left( 1+B \right)^{3} }+3$

 

$=\frac{6B^{3}+18B^{2}+14B+4}{\left( 2+B \right) \left( 1+B \right)^{3} }+3=\frac{2\left( 3B^{2}+3B+1 \right)}{ \left( 1+B \right)^{3} }+3$

 

이제 $r=1$ 때와 비슷한 형태를 찾을 수 있죠?

 

$D_{1}\left( 2,1 \right)=1+2\left( 1- \frac{B}{1+B} \right)$

 

$D_{1}\left( 2,2 \right)=2+2\left( 1-\left( \frac{B}{1+B} \right)^{2} \right)$

 

$D_{1}\left( 2,3 \right)=3+2\left( 1-\left( \frac{B}{1+B} \right)^{3} \right)$

 

마찬가지로 수학적 귀납법을 이용해서 $D_{1}\left( 2,k \right)=k+2\left( 1-\left( \frac{B}{1+B} \right)^{k} \right)$ 임을 보이겠습니다.

 

$\left( 1 \right)$ $0\leq k\leq 3$ 에서 성립함을 이미 보였습니다.

 

$\left( 2 \right)$ 자연수 $t$ 에 대해 $D_{1}\left( 2,t \right)=t+2\left( 1-\left( \frac{B}{1+B} \right)^{t} \right)$ 를 가정하겠습니다.

 

$\left( 3 \right)$ $\frac{2D_{1}\left( 1,t+1 \right)+BD_{1}\left( 2,t \right)}{2+B}+1=D_{1}\left( 2,t+1 \right)$ 을 보이면 됩니다.

 

$\frac{2D_{1}\left( 1,t+1 \right)+BD_{1}\left( 2,t \right)}{2+B}+1$

 

$\leftrightarrow \frac{2\left( t+1+1-\left( \frac{B}{1+B} \right)^{t+1} \right)+B\left( t+2\left( 1-\left( \frac{B}{1+B} \right)^{t} \right) \right)}{2+B}+1$

 

$\leftrightarrow t+2+1+\frac{-2\left \{ \frac{B^{t+1}}{\left( 1+B \right)^{t+1}} + \frac{B^{t+1}}{\left( 1+B \right)^{t}} \right \}}{2+B}$

 

$\leftrightarrow t+1+2-2\frac{B^{t+1}}{\left( 1+B \right)^{t+1}}=\left( t+1 \right)+2\left( 1-\left( \frac{B}{1+B} \right)^{t+1} \right) \leftrightarrow D_{1}\left( 2,t+1 \right)$

 

따라서 $D_{1}\left( 2,k \right)=k+2\left( 1-\left( \frac{B}{1+B} \right)^{k} \right)$ 이 증명되었습니다.

---

여기까지의 성과를 보면 다음과 같습니다.

 

$\left( 1 \right)\;\;D_{1}\left( r,0 \right)=0$

 

$\left( 2 \right)\;\;D_{1}\left( 1,k \right)=k+1-\left( \frac{B}{1+B} \right)^{k}$

 

$\left( 3 \right)\;\;D_{1}\left( 2,k \right)=k+2\left( 1- \left( \frac{B}{1+B} \right)^{k} \right)$

 

이제 어떤 패턴을 찾을 수 있을까요?

 

수학적 귀납법으로 $D_{1}\left( r,k \right)=k+r\left( 1- \left( \frac{B}{1+B} \right)^{k} \right)$ 을 보이겠습니다.

 

$\left( 1 \right)$ $r\leq 2$ 의 경우 모든 $k$ 값에 대해 성립함을 보였습니다.

 

$\left( 2 \right)$ 모든 $r<p$ 와 모든 $k$ 값에 대해 위 명제가 성립하게 하는 자연수 $p$ 의 존재를 가정하겠습니다.

 

$\left( 3 \right)$ 만약 $r=p$ 일 때 모든 $k$ 값에 대해 위 명제가 성립한다면 명제가 증명된 것입니다.

 

$\left( 3-a \right)$ $D_{1}\left( p,0 \right)=0$ 입니다. 이는 $D_{1}$ 의 정의에 의하여 항상 참입니다.

 

$\left( 3-b \right)$ $D_{1}\left( p,1 \right)$ 을 구하는 과정을 제시하겠습니다.

 

$D_{1}\left( p,1 \right)=\frac{pD_{1}\left( p-1,1 \right)+BD_{1}\left( p,0 \right)}{p+B}+1=\frac{p}{p+B}\times\left[ 1+\left( p-1 \right) \left \{ 1-\left( \frac{B}{1+B} \right) \right \} \right]+1$

$=\frac{p\times \left( p-\frac{\left( p-1 \right)B}{1+B} \right)}{p+B}+1=1+\frac{p}{p+B}=1+p\left( 1-\left( \frac{B}{1+B} \right) \right)$

 

$\left( 3-c \right)$ $D_{1}\left( p,t \right)=t+p\left \{ 1-\left( \frac{B}{1+B} \right)^{t} \right \}$ 를 만족하는 자연수 $t$ 를 가정하겠습니다.

 

그러면 다음 과정에 의해

 

$\frac{pD_{1}\left( p-1,t+1 \right)+BD_{1}\left( p,t \right)}{p+B}+1$

 

$=\frac{p\left[ \left( t+1 \right) + \left( p-1 \right) \left \{ 1-\left( \frac{B}{1+B} \right)^{t+1} \right \} \right]+B\left[  t+p\left \{ 1-\left( \frac{B}{1+B} \right)^{t} \right \} \right]}{p+B}+1$

 

$=t+p+1-\frac{p}{p+B}\times \left[ \left( p-1 \right)\frac{B^{t+1}}{\left( 1+B \right)^{t+1}} + \frac{B^{t+1}}{\left( 1+B \right)^{t}} \right]$

 

$=\left( t+1 \right)+p\left \{ 1-\left( \frac{B}{1+B} \right)^{t+1} \right \}=D_{1}\left( p,t+1 \right)$

 

$r=p$ 이면 모든 $k$ 값에 대해 $D_{1}\left( p,k \right)=k+p\left \{ 1-\left( \frac{B}{1+B} \right)^{k} \right \}$ 임이 확인됐습니다.

 

이상에서, 모든 0이상의 정수 $r\;k$ 에 대해 $D_{1}\left( r,k \right)=k+r\left( 1- \left( \frac{B}{1+B} \right)^{k} \right)$ 입니다.

---

$G=0$ 일 때, 즉 $D_{1}$ 을 성공적으로 구했습니다.

 

즉 $D_{2}$ 를 구할 차례입니다.

 

$D_{2}\left( r,k \right)$ 은 다르게 표현하면 $D$ 에서 $D_{1}$ 의 여사건입니다.

 

그 점을 염두에 두고, $D_{2}\left( r,0 \right)$ 과 $D_{2}\left( 0,k \right)$ 의 값을 구해봅시다.

 

$D_{2}\left( r,0 \right)=0$ 입니다.

 

$G>0$ 이어도 $k=0$ 이면 제비 뽑기가 바로 중단되기 때문에 그렇습니다.

 

한편 우리는 자연스럽게 $D_{1}\left( 0,k \right)=k$ 로 두었습니다.

 

그런데 $D$ 의 정의를 떠올려본다면, $r=0$ 일 때 파란 제비가 뽑힐 확률이

$P=\frac{B}{B+G}$ 임을 고려하여 $D\left( 0,k \right)=\frac{k}{P}=k\frac{B+G}{B}=k\left( 1+\frac{G}{B} \right)$ 입니다.

 

따라서 $D_{2}\left( 0,k \right)=\frac{Gk}{B}$ 입니다.

 

$D_{2}$ 에 관한 다음 점화관계를 remind하며 진행해봅시다.

 

$D_{2}\left( r,k \right)=\frac{rD_{2}\left( r-1,k \right)+BD_{2}\left( r,k-1 \right)}{r+B}+\frac{G}{r+B}$

---

 

$r=1$ , 즉 $D_{2}\left( 1,k \right)$ 를 구하겠습니다.

 

$D_{2}\left( 1,0 \right)=0$ 입니다.

 

$D_{2}\left( 1,1 \right)=\frac{D_{2}\left( 0,1 \right)+BD_{2}\left( 1,0 \right)}{1+B}+\frac{G}{1+B}=\frac{ \frac{G}{B} + G }{1+B}=\frac{G}{B}$ 입니다.

 

이제 $D_{2}\left( 1,k \right)=\frac{Gk}{B}$ 임을 귀납법으로 보이겠습니다!

 

$\left( 1 \right)$ $k\leq 1$ 일 때는 위에서 보였습니다.

 

$\left( 2 \right)$ $D_{2}\left( 1,t \right)=\frac{Gt}{B}$ 인 자연수 $t$ 의 존재를 가정합시다.

 

$\left( 3 \right)$

 

$\frac{D_{2}\left( 0,t+1 \right)+BD_{2}\left( 1,t \right) }{1+B}+\frac{G}{1+B}$

 

$=\frac{ \frac{G}{B}\left( t+1 \right)+Gt+G}{1+B}=\frac{G}{B}\left( t+1 \right)$

 

$=D_{2}\left( 1,t+1 \right)$

 

따라서, $D_{2}\left( 1,k \right)=\frac{Gk}{B}$ 였습니다

---

내용 반복을 좀 줄일게요.

 

$D_{2}\left( r,k \right)=\frac{Gk}{B}$ 를 귀납법으로 보이겠습니다.

 

$\left( 1 \right)$ 우선 $r\leq 1$ 이면 성립합니다.

 

$\left( 2 \right)$ $r<p$ 와 모든 $k$ 값에 대해 만족하는 자연수 $p$ 를 생각해봅시다. (e.g. $p=2$ )

 

$\left( 3 \right)$ 이제 $D_{2}\left( p,k \right)=\frac{Gk}{B}$ 를 보입니다.

 

$\left( 3-a \right)$ $D_{2}\left( p,0 \right)=0$ 입니다.

 

$\left( 3-b \right)$ $D_{2}\left( p,1 \right)$ 을 구할까요?

 

$D_{2}\left( p,1 \right)=\frac{pD_{2}\left( p-1,1 \right) + BD_{2}\left( p,0 \right)}{p+B}+\frac{G}{p+B}$

 

$=\frac{p\times \frac{G}{B} + G}{p+B}=\frac{G}{B}$

 

$\left( 3-c \right)$ $D_{2}\left( p,t \right)=\frac{Gt}{B}$ 를 만족하는 자연수 $t$ 를 생각해봅시다.

 

$\frac{pD_{2}\left( p-1,t+1 \right) + BD_{2}\left( p,t \right)}{p+B}+\frac{G}{p+B}$

 

$=\frac{p\times \frac{G}{B}\left( t+1 \right)+Gt+G}{p+B}=\frac{G\left( t+1 \right)}{p+B} \leftrightarrow D_{2}\left( p,t+1 \right)$

 

그러니까, $r=p$ 일 때도 모든 $k$ 값에 대해 $D_{2}\left( p,k \right)=\frac{Gk}{B}$ 입니다.

 

따라서 모든 $r\;k$ 값에 대해 $D_{2}\left( r,k \right)=\frac{Gk}{B}$ 입니다.

---

이제 일반항을 구할 수 있습니다.

 

앞서 말했듯이 $D\left( r,k \right)=D_{1}\left( r,k \right)+D_{2}\left( r,k \right)$ 입니다.

 

따라서 다음과 같은 결론을 얻습니다.

 

$D\left( r,k \right)=k+r\left \{ 1-\left( \frac{B}{1+B} \right)^{k} \right \}+\frac{Gk}{B}$

 

주어지는 $R\;G\;B\;K$ 값은 자연수이므로 따로 처리해야 할 예외사항은 없습니다.

 

이제 $D\left( R,K \right)$ 를 구하는 코드를 구현하면 문제가 해결됩니다.

 

$D\left( R,K \right)$ 를 구하는 코드가 $O\left( log\;P \right)$ 인데, 이를 $T$ 번 반복하니까 최종적으로

 

$O\left( T\;log\;P \right)$ 를 얻습니다. 제 코드는 다음과 같습니다.

#include <stdio.h>
#define mod 1000000007

long long power_modular (long long A, long long power);

int main() {

	int T;
	scanf("%d", &T);
	
	int R, G, B, K;
	while(T--) {
		scanf("%d %d %d %d", &R, &G, &B, &K);
		
		long long ANS = K;
		
		long long temp;
		temp = power_modular(B, K) * power_modular(1+B, mod - K - 1) % mod;
		temp = (1 - temp + mod) % mod;
		temp = temp * R % mod;
		
		ANS = (ANS + temp) % mod;
		
		temp = G * power_modular(B, mod - 2) % mod;
		temp = temp * K % mod;
		
		ANS = (ANS + temp) % mod;
		printf("%lld\n", ANS);
	}
	return 0;
}

long long power_modular (long long A, long long power) {
	long long result = 1;
	while(power) {
		if (power % 2) {
			result = result * A % mod;
		}
		A = A * A % mod;
		power /= 2;
	}
	return result;
}

(C11, 1116KB, 0ms, 제출번호 31715570)

---