Piling Papers

题目描述

Farmer John 在纸片上写下了 $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\ot 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$ 取模的结果。

输入格式

第一行包含三个用空格分隔的整数 $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 5

2
18
34

提示

对于第一个询问，当读取区间 $[1, 2]$ 时，Bessie 有 9 种堆叠纸片的方式： Bessie 可以忽略 $1$，然后忽略 $2$，得到 $0$。 Bessie 可以 忽略 $1$，然后把 $2$ 放到纸堆顶部，得到 $2$。 Bessie 可以忽略 $1$，然后把 $2$ 放到纸堆底部，得到 $2$。 Bessie 可以把 $1$ 放到纸堆顶部，然后忽略 $2$，得到 $1$。 Bessie 可以把 $1$ 放到纸堆顶部，然后把 $2$ 放到纸堆顶部，得到 $21$。 Bessie 可以把 $1$ 放到纸堆顶部 然后把 $2$ 放到纸堆底部，得到 $12$。 Bessie 可以把 $1$ 放到纸堆底部，然后忽略 $2$，得到 $1$。 Bessie 可以把 $1$ 放到纸堆底部，然后把 $2$ 放到纸堆顶部，得到 $21$。 Bessie 可以把 $1$ 放到纸堆底部 然后把 $2$ 放到纸堆底部，得到 $12$。 只有得到 $21$ 的 $2$ 种方式会产生一个介于 $13$ 和 $327$ 之间的数，因此答案是 $2$。 SCORING: 输入 2-3：$B<100$ 输入 4-5：$A=B$ 输入 6-13：无额外限制。 题目作者：Jesse Choe

标签: USACO|2023|Gold

来源

USACO|2023|Gold