[USACO20JAN] Non-Decreasing Subsequences P
题目描述
Bessie 最近参加了一场 USACO 竞赛,遇到了以下问题。当然 Bessie 知道怎么做。那你呢?
考虑一个仅由范围在 $1 \ldots K$($1 \leq K \leq 20$)之间的整数组成的长为 $N$ 的序列 $A_1,A_2, \ldots ,A_N$($1 \leq N \leq 5 \times 10^4$)。给定 $Q$( $1 \leq Q \leq 2 \times 10^5$ )个形式为 $[L_i,R_i]$($1 \leq L_i \leq R_i \leq N$)的询问。对于每个询问,计算 $A_{L_i},A_{L_i+1}, \ldots ,A_{R_i}$ 中不下降子序列的数量模 $10^9+7$ 的余数。
$A_L,\ldots ,A_R$ 的一个不下降子序列是一组索引 ($j_1,j_2, \ldots ,j_x$),满足 $L\le j_1<j_2<\ldots<j_x\le R$ 以及 $A_{j_1}\le A_{j_2}\le \ldots \le A_{j_x}$。确保你考虑了空子序列!
输入输出格式
输入格式
输入的第一行包含两个空格分隔的整数 $N$ 和 $K$。
第二行包含 $N$ 个空格分隔的整数 $A_1,A_2, \ldots ,A_N$。
第三行包含一个整数 $Q$。
以下 $Q$ 行每行包含两个空格分隔的整数 $L_i$ 和 $R_i$。
输出格式
对于每个询问 $[L_i,R_i]$,你应当在新的一行内输出 $A_{L_i},A_{L_i+1},\ldots, A_{R_i}$ 的不下降子序列的数量模 $10^9+7$ 的余数。
输入输出样例
输入样例 #1
5 2
1 2 1 1 2
3
2 3
4 5
1 5
输出样例 #1
3
4
20
说明
### 样例解释
对于第一个询问,不下降子序列为 $()$、$(2)$ 和 $(3)$。$(2,3)$ 不是一个不下降子序列,因为 $A_2\not \le A_3$。
对于第二个询问,不下降子序列为 $()$、$(4)$、$(5)$ 和 $(4,5)$。
### 子任务
- 测试点 $2 \sim 3$ 满足 $N \leq 1000$。
- 测试点 $4 \sim 6$ 满足 $K \leq 5$。
- 测试点 $7 \sim 9$ 满足 $Q \leq 10^5$。
- 测试点 $10 \sim 12$ 没有额外限制。