| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1.2 초 (추가 시간 없음) | 1024 MB (추가 메모리 없음) | 853 | 240 | 158 | 27.101% |
피보나치 수는 1ドル$로 시작한다. 0ドル$번째 피보나치 수는 1ドル$이고, 1ドル$번째 피보나치 수는 1ドル$이다. 2ドル$번째 피보나치 수부터는 바로 앞 두 피보나치 수의 합이 된다. 이를 식으로 표현하면 $F_n = F_{n-2} + F_{n-1}$ ($n \geq 2$)이 된다.
$n$번째 피보나치 수 하나는 쉽게 구할 수 있지만, 이번 문제는 호락호락하지 않다. 모든 값이 0ドル$인 길이 $N$의 수열이 주어진다. 이때, 다음 쿼리를 주어진 순서대로 수행한 후의 결과를 출력하는 프로그램을 작성해보자.
l r : 수열의 $l$번째 위치부터 $r$번째 위치까지의 값들을 각각 $F_1, F_2, \cdots , F_{r-l+1}$로 바꾼다.첫째 줄에 수열의 크기 $N$이 주어진다. (1ドル \leq N \leq 1\ 000\ 000$)
둘째 줄에 쿼리의 개수 $Q$가 주어진다. (1ドル \leq Q \leq 1\ 000\ 000$)
셋째 줄부터 $Q$개 줄에 걸쳐 쿼리에 대한 정보 $l,ドル $r$이 주어진다. (1ドル \leq l \leq r \leq N$)
입력으로 주어지는 모든 수는 정수이다.
모든 쿼리를 순서대로 적용한 후, 수열의 모든 수를 공백으로 구분해 출력한다. 단, 수가 너무 커질 수 있으니 각각의 수를 10ドル^9+7$으로 나눈 나머지를 출력한다.
10 2 1 10 6 10
1 2 3 5 8 1 2 3 5 8
8 1 2 7
0 1 2 3 5 8 13 0