#PU1307. USACO 2023 February Contest, Gold — Problem 3. Piling Papers

    ID: 1408 传统题 2000ms 256MiB 尝试: 0 已通过: 0 难度: 提高+/省选- 上传者: 标签>USACO赛事:feb23来源:usaco.orgscoring:equal_test_cases栈枚举前缀和

USACO 2023 February Contest, Gold — Problem 3. Piling Papers

USACO 2023 February Contest, Gold — Problem 3. Piling Papers

题目描述

Farmer John wrote down NN (1≤N≤3001\le N\le 300) digits on pieces of paper. For each i∈[1,N]i\in [1,N], the iith piece of paper contains digit aia_i (1≤ai≤91 \leq a_i \leq 9). The cows have two favorite integers AA and BB (1≤A≤B<10181\le A\le B< 10^{18}), and would like you to answer QQ (1≤Q≤5⋅1041\le Q\le 5\cdot 10^4) queries. For the iith query, the cows will move left to right across papers li…ril_i\dots r_i (1≤li≤ri≤N1\le l_i\le r_i\le N), maintaining an initially empty pile of papers. For each paper, they will either add it to the top of the pile, to the bottom of the pile, or neither. In the end, they will read the papers in the pile from top to bottom, forming an integer. Over all 3ri−li+13^{r_i-l_i+1} ways for the cows to make choices during this process, count the number of ways that result in the cows reading an integer in [A,B][A,B] inclusive, and output this number modulo 109+710^9+7.

输入格式

The first line contains three space-separated integers NN, AA, and BB. The second line contains NN space-separated digits a1,a2,…,aNa_1, a_2, \dots, a_N. The third line contains an integer QQ, the number of queries. The next QQ lines each contain two space-separated integers lil_i and rir_i.

输出格式

For each query, a single line containing the answer.

数据范围

Inputs 2-3: B<100B<100 Inputs 4-5: A=BA=B Inputs 6-13: No additional constraints. Problem credits: Jesse Choe

样例

样例 1

5 13 327
1 2 3 4 5
3
1 2
1 3
2 5
2
18
34
For 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$.