3328. [USACO20 Jan Platinum]Non-Decreasing Subsequences

【题目描述】

Bessie 最近参加了一场 USACO 竞赛，遇到了以下问题。当然 Bessie 知道怎么做。那你呢？

考虑一个仅由范围在 $1\ldots K(1\le K\le 20)$之间的整数组成的长为 $N$ 的序列 $A_1,A_2,\ldots,A_N(1\le N\le 5 × 10^4)$。

给定 $Q(1\le Q\le 2 × 10^5)$个形式为 $[L_i,R_i](1\le L_i\le R_i\le N)$的询问。

对于每个询问，计算 $A_{L_i},A_{L_i+1}..., A_{R_i}$ 中不下降子序列的数量模 $10^9+7$ 的余数。

$A_L,...,A_R$ 的一个不下降子序列是一组索引 $(j_1,j_2,..., j_x)$，满足 $L\le j_1<j_2<...<j_x\le R$ 以及 $A_{j_1}\le A_{j_2}\le ... \le A_{j_x}$。

确保你考虑了空子序列！

【输入格式】

输入的第一行包含两个空格分隔的整数 $N$ 和 $K$。

第二行包含 $N$ 个空格分隔的整数 $A_1,A_2,..., A_N$。

第三行包含一个整数 $Q$。

以下 $Q$ 行每行包含两个空格分隔的整数 $L_i$ 和 $R_i$。

【输出格式】

对于每个询问 $[L_i,R_i]$，你应当在新的一行内输出 $A_{L_i},A_{L_i+1},..., A_{R_i}$ 的不下降子序列的数量模 $10^9+7$ 的余数。

【样例输入】

5 2
1 2 1 1 2
3
2 3
4 5
1 5

【样例输出】

3
4
20

【样例解释】

对于第一个询问，不下降子序列为 $()$、$(2)$ 和 $(3)$。$(2,3)$ 不是一个不下降子序列，因为 $A_2\not \le A_3$。

对于第二个询问，不下降子序列为 $()$、$(4)$、$(5)$ 和 $(4,5)$。

【提示】

对于$ 17\% $的测试数据(测试点$ 2\sim3 $)，满足$ N ≤ 1,000 $。

另有$ 25\% $的测试数据(测试点$ 4\sim6 $)，满足$ K ≤ 5 $。

另有$ 25\% $的测试数据(测试点$ 7\sim9 $)，满足$ Q ≤ 1 × 10^5 $。

对于$ 100\% $的测试数据，均满足上文所给出的数据规模。

【来源】

USACO 一月公开赛 Platinum 组