Non-Decreasing Subsequences

题目描述

Bessie 最近在参加一场 USACO 比赛时遇到了下面这道题。 当然，Bessie 知道怎么解。但你会吗？

给定一个长度为 $N$ $(1\le N\le 5\cdot 10^4)$ 的序列 $A_1,A_2,\ldots,A_N$，其中每个元素都是 $1\ldots K$ 范围内的整数 $(1\le K\le 20).$ 你将收到 $Q$ $(1\le Q\le 2\cdot 10^5)$ 个形如 $[L_i,R_i]$ 的询问 $(1\le L_i\le R_i\le 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<\cdots<j_x\le R$ 且 $A_{j_1}\le A_{j_2}\le \cdots \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$ 取模的结果，每个结果占一行。

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

3
4
20

提示

SCORING: 测试点 2-3 满足 $N\le 1000$。 测试点 4-6 满足 $K\le 5.$ 测试点 7-9 满足 $Q\le 10^5.$ 测试点 10-12 没有额外限制。

对于第一个询问，非递减子序列为 $(), (2),$ 和 $(3).$ $(2,3)$ 不是非递减子序列，因为 $A_2\not \le A_3.$

对于第二个询问，非递减子序列为 $()$, $(4)$, $(5)$, 以及 $(4,5)$。

题目鸣谢：Benjamin Qi

标签: USACO|2020|Platinum

来源

USACO|2020|Platinum