P9129 [USACO23FEB] Piling Papers G

题目描述

农夫约翰在纸片上写下了 $N (1 \le N \le 300)$ 个数字。对于每个 $i \in [1,N]$，第 $i$ 张纸片上写着数字 $a_i (1 \le a_i \le 9)$。

奶牛们有两个最喜欢的整数 $A$ 和 $B(1 \le A \le B<10^{18})$，希望你回答 $Q (1 \le Q \le 5 \times 10^4)$ 个查询。对于第 $i$ 个查询，奶牛们将从左到右移动穿过纸片 $l_i \cdots 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, \cdots ,a_N$。

第三行包含一个整数 $Q$，表示查询的数量。

接下来的 $Q$ 行每行包含两个用空格分隔的整数 $l_i$ 和 $r_i$。

输出格式

对于每个查询，输出一个单独的答案。

输入输出样例 #1

输入 #1

5 13 327
1 2 3 4 5
3
1 2
1 3
2 5

输出 #1

2
18
34

说明/提示

示例 1 的解释

对于第一个查询，Bessie 在读取区间 $[1,2]$ 时有九种方式堆叠纸片：

• 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$。

只有 $2$ 种方式得到的数字在 $13$ 和 $327$ 之间，所以答案是 $2$。

评分

• 输入 $2-3$：$B<100$
• 输入 $4-5$：$A=B$
• 输入 $6-13$：无额外约束。

题面翻译由 ChatGPT-4o 提供。