| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 1024 MB | 103 | 60 | 28 | 52.830% |
양의 정수의 무한한 수열 $a_1, a_2, a_3, \cdots $이 다음 조건을 만족한다. $c$는 고정된 양의 정수이고 $c \geq 2$이다.
임의의 양의 정수 $n$에 대하여,
양의 정수 $m$에 대하여, $a_m + a_{m+1} = c+1$ 이 성립하도록 하는 모든 양의 정수 $a_1$의 합을 $S(m)$이라고 하자. 양의 정수 $M$이 주어졌을 때, $S(1), S(2), \cdots, S(M)$의 값을 각각 구하여라. 단, 값이 매우 커질 수 있으므로 1ドル\ 000\ 000\ 007$로 나눈 나머지를 출력한다.
첫째 줄에 두 정수 $c, M$이 공백을 사이에 두고 주어진다.
$M$개의 줄에 걸쳐 정답을 출력한다. $i(1 \leq i \leq M)$번째 줄에는 $S(i)$를 1ドル\ 000\ 000 \ 007$로 나눈 나머지를 하나의 음이 아닌 정수로 출력해야 한다. 1ドル\ 000\ 000\ 007$은 소수이다.
2 6
3 7 15 34 72 153
$c=2, M=6$ 이다.
$a_1 + a_2 = 3$일 필요충분조건은 $a_1 \in \left\{1, 2 \right\}$ 이므로, $S(1) = 1 + 2 = 3$이다.
$a_2 + a_3 = 3$일 필요충분조건은 $a_1 \in \left\{1, 2, 4 \right\}$ 이므로, $S(2) = 1 + 2 + 4 = 7$이다.
$a_6 + a_7 = 3$일 필요충분조건은 $a_1 \in \left\{1, 2, 3, 4, 5, 6, 8, 12, 16, 32, 64 \right\}$ 이므로, $S(6) = 1 +たす 2 +たす 3 +たす 4 +たす 5 +たす 6 +たす 8 +たす 12 +たす 16 +たす 32 +たす 64 =わ 153$이다.
142857 2
142858 408265167
$c = 142\ 857, M =2$ 이다.
$a_2 + a_3= 142\ 858$일 필요충분조건은 $a_1 \in \left\{1, 142\ 857, 20\ 408\ 122\ 449 \right\}$이므로, $S(2) = 1 + 142\ 857 + 20\ 408\ 122\ 449= 20\ 408\ 265\ 307$이다. 두 번째 줄에는 20ドル\ 408\ 265\ 307$을 1ドル\ 000\ 000\ 007$로 나눈 나머지인 408ドル\ 265\ 167$을 출력해야 한다.
School > DGUPC > 제 2회 DGUPC I번