시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 256 MB | 231 | 72 | 46 | 34.586% |
메이지 나라에 사는 리샤는 전선을 이용한 통신 시스템을 만들었다. 리샤가 만든 통신 규약에 따르면 모든 전선에는 각자 정해진 용량이 있고, 전선의 용량이 $i$라는 것은, $i$개의 문자를 보낼 수 있다는 것을 의미한다.
메이지 나라에서 사용하는 문자는 112345종류이다. 이것은, 전선의 용량이 $i$인 전선이 $112345^i$종류의 정보를 보낼 수 있다는 것이고 전선의 가치가 $112345^i$라는 것을 의미한다.
메이지 나라에는 리샤 이외에도 많은 공학자들이 있다. 매년 메이지 나라에 있는 모든 전선에 대해, 그 전선의 용량이 $X$라면, 그 전선들을 바나흐-타르스키 역설을 이용하여(!) 두개로 나누어서, 용량이 각각 $f(X)=aX^2 + bX + c$와 $g(X)=dX^2 + eX + f$인 전선으로 만든다. 처음의 용량 $N$의 전선으로 시작해서, 1년 후에는, 용량이 각 $f(N), g(N)$인 전선이, 2년 후에는, $f(f(N)), f(g(N)), g(f(N)), g(g(N))$ 인 전선이, 그리고 $M$년 후에는 $2^M$개의 전선이 같은 방법으로 만들어진 용량을 가지고 존재할 것이다. $M$년 후의 전선들의 가치의 총 합을 구하여라.
첫째 줄에는, $N$, $M$이 공백으로 구분되어 들어온다.
둘째 줄에는, $a$, $b$, $c$, $d$, $e$, $f$가 공백으로 구분되어 들어온다.
$0 \le N, M, a, b, c, d, e, f \le 1000000000 = 10^9$을 만족한다.
$M$년 후의 전선들의 가치의 총 합을 1000000009(=$10^9 + 9$)로 나눈 나머지를 구하여라.
0 1 1 2 3 4 5 6
844207762
0 2 1 0 0 0 0 1
337036
첫 번째 예제에서의 전선 가치의 총 합은 $112345^3 + 112345^6$이다.
University > KAIST > 2017 KAIST RUN Spring Contest (HYEA Cup) I번