시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 512 MB | 86 | 18 | 12 | 17.143% |
현기는 평소에 첨탑 부수기라는 게임을 즐겨한다. 첨탑 부수기 게임은 1층에 존재하는 첨탑의 입구로 들어가 꼭대기 층까지 한 층씩 등반하며 첨탑 내의 모든 괴물을 쓰러뜨리는 게임이다. 첨탑의 꼭대기까지 등반하여 게임을 클리어하더라도 다시 도전하면 그때마다 또 다른 괴물을 만날 수 있어 몇 번을 하더라도 새로운 재미를 선사한다.
첨탑 부수기 게임은 새로운 게임을 시작할 때 무작위로 생성되는 시드$(=Seed)$를 바탕으로 각 층에 생성되는 괴물의 강함$(=Strength)$이 정해진다. 시드는 알파벳 대소문자와 0을 제외한 숫자로 이루어진 10자리 문자열이다. 괴물의 강함을 계산하기 위해 시드의 각 자리 문자를 사용할 때에는 아래의 표와 같이 다른 정숫값으로 바꿔 연산한다.
$Seed$의 각 자리 문자 | 1 | $\cdots$ | 8 | 9 | A | B | $\cdots$ | Y | Z | a | b | $\cdots$ | y | z |
값 | 1 | $\cdots$ | 8 | 9 | 10 | 11 | $\cdots$ | 34 | 35 | 36 | 37 | $\cdots$ | 60 | 61 |
예를 들어 시드가 "AB1z8DcdT4"일 경우에 시드의 첫 번째 문자$(=Seed[0])$인 'A'는 정수 10을 의미한다. 여기서, $Seed[i]$는 시드를 구성하는 문자 중 왼쪽에서 $i+1$번째 문자에 해당한다.
층 수가 $N$인 첨탑 부수기 게임을 플레이할 때, 1층에서 마주치는 괴물의 강함은 1이고 $k(\neq 1)$층에서 마주치는 괴물의 강함은 아래와 같이 계산한다.
$\begin{cases} f(i,k) = Seed[(i\times k)\ \textrm{mod}\ 10] \\ g(k) = \sum_{i=1}^{10} f(i,k) \times k \\ Strength(k) = g(k) ^ {Strength(k-1)} \end{cases}$
현기가 꼭대기 층이 $N$층인 첨탑 부수기 게임을 새로 시작할 때, 꼭대기 층에서 마주치는 괴물의 강함을 구하여라. 단, 괴물의 강함이 매우 클 수 있으므로 괴물의 강함을 $M$으로 나눈 나머지를 출력하라.
첫째 줄에 두 정수 $N$과 $M$이 주어진다. $(1\le N, M \le10^9)$
둘째 줄에 $Seed$가 주어진다. $Seed$는 알파벳 대소문자와 0을 제외한 숫자로 이루어진 10자리 문자열이다.
첫째 줄에 괴물의 강함을 $M$으로 나눈 나머지를 출력한다.
4 37 AB1z8DcdT4
1
주어진 시드를 바탕으로 2층 이상에서의 $g(k)$을 계산해보면
\begin{align*} g(2) & = \sum_{i=1}^{10} f(i,2) \times 2 \\ & = (Seed[2]+Seed[4]+Seed[6]+Seed[8]+Seed[0]+Seed[2]+Seed[4]+Seed[6]+Seed[8]+Seed[0]) \times 2 \\ & = (1+8+38+29+10+1+8+38+29+10) \times 2 \\ & = 344 \end{align*}
\begin{align*} g(3) & = \sum_{i=1}^{10} f(i,3) \times 3 \\ & = (Seed[3]+Seed[6]+Seed[9]+Seed[2]+Seed[5]+Seed[8]+Seed[1]+Seed[4]+Seed[7]+Seed[0]) \times 3 \\ & = (61+38+4+1+13+29+11+8+39+10) \times 3 \\ & = 642 \end{align*}
\begin{align*} g(4) & = \sum_{i=1}^{10} f(i,4) \times 4 \\ & = (Seed[4]+Seed[8]+Seed[2]+Seed[6]+Seed[0]+Seed[4]+Seed[8]+Seed[2]+Seed[6]+Seed[0]) \times 4 \\ & = (8+29+1+38+10+8+29+1+38+10) \times 4 \\ & = 688 \end{align*}
이다.
따라서 각 층에서 마주치는 괴물의 강함을 계산하면 아래와 같다.
$\begin{cases} Strength(1)=1 \\ Strength(2)=g(2)^{Strength(1)}=344^1=344 \\ Strength(3)=g(3)^{Strength(2)}=642^{344} \\ Strength(4)=g(4)^{Strength(3)}=688^{(642^{344})}\end{cases}$
여기서 $688^{(642^{344})}$을 $37$로 나누었을 때 나머지가 $1$이므로 $1$을 출력한다.
8 22 65n1Ad87oQ
10
University > 부산대학교 > 2022 부산대학교 CodeRace F번