레이팅 미적용농부 존은 종이 조각에 숫자 \(N\) (\(1\le N\le 300\))개를 적어 두었다. 각 \(i\in [1,N]\)에 대해 \(i\)번째 종이에는 숫자 \(a_i\) (\(1 \leq a_i \leq 9\))가 적혀 있다.
소들에게는 좋아하는 두 정수 \(A\)와 \(B\) (\(1\le A\le B< 10^{18}\))가 있고, \(Q\) (\(1\le Q\le 5\cdot 10^4\))개의 쿼리에 답해 주기를 원한다. \(i\)번째 쿼리에서 소들은 처음에 비어 있는 종이 더미를 유지하면서 종이 \(l_i\dots r_i\) (\(1\le l_i\le r_i\le N\))를 왼쪽에서 오른쪽으로 훑는다. 각 종이에 대해 더미의 맨 위에 놓거나, 맨 아래에 놓거나, 아무것도 하지 않는다. 끝나면 더미의 종이들을 위에서 아래로 읽어 하나의 정수를 만든다. 이 과정에서 소들이 선택할 수 있는 전체 \(3^{r_i-l_i+1}\)가지 방법 중, 소들이 읽는 정수가 \([A,B]\)(양 끝 포함)에 속하게 되는 방법의 수를 세고, 이를 \(10^9+7\)로 나눈 나머지를 출력한다.
출제자: Jesse Choe
배점
- 입력 2-3: \(B<100\)
- 입력 4-5: \(A=B\)
- 입력 6-13: 추가 제약이 없다.
출제자: Jesse Choe
첫째 줄에 공백으로 구분된 세 정수 \(N\), \(A\), \(B\)가 주어진다.
둘째 줄에 공백으로 구분된 \(N\)개의 숫자 \(a_1, a_2, \dots, a_N\)이 주어진다.
셋째 줄에 쿼리의 수인 정수 \(Q\)가 주어진다.
다음 \(Q\)개의 줄에 각각 공백으로 구분된 두 정수 \(l_i\)와 \(r_i\)가 주어진다.
각 쿼리에 대해 답을 한 줄에 하나씩 출력한다.
5 13 327
1 2 3 4 5
3
1 2
1 3
2 52
18
34For the first query, there are nine ways Bessie can stack papers when reading
the interval \([1, 2]\):
- Bessie can ignore \(1\) then ignore \(2\), getting \(0\).
- Bessie can ignore \(1\) then add \(2\) to the top of the stack, getting \(2\).
- Bessie can ignore \(1\) then add \(2\) to the bottom of the stack, getting \(2\).
- Bessie can add \(1\) to the top of the stack then ignore \(2\), getting \(1\).
- Bessie can add \(1\) to the top of the stack then add \(2\) to the top of the stack, getting \(21\).
- Bessie can add \(1\) to the top of the stack then add \(2\) to the bottom of the stack, getting \(12\).
- Bessie can add \(1\) to the bottom of the stack then ignore \(2\), getting \(1\).
- Bessie can add \(1\) to the bottom of the stack then add \(2\) to the top of the stack, getting \(21\).
- Bessie can add \(1\) to the bottom of the stack then add \(2\) to the bottom of the stack, getting \(12\).
Only the \(2\) ways that give \(21\) yield a number between \(13\) and \(327\), so the
answer is \(2\).
riseoj 작성
출처 올림피아드 > USACO > 2022-2023 > February > Gold