Non-Decreasing Subsequences

提交数: 4, 通过率: 25%, 平均分: 29

题目描述:

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

考虑一个仅由范围在 1…K（1≤K≤20）之间的整数组成的长为 N 的序列 A1,A2,…,AN（1≤N≤5⋅104）。给定 Q（1≤Q≤2⋅105）个形式为 [Li,Ri]（1≤Li≤Ri≤N）的询问。对于每个询问，计算 ALi,ALi+1…,ARi 中不下降子序列的数量模 109+7 的余数。

AL,…,AR 的一个不下降子序列是一组索引(j1,j2,…,jx)，满足RL≤j1<j2<⋯<jx≤R 以及Aj1≤Aj2≤⋯≤Ajx。确保你考虑了空子序列！

测试点性质：
  • 测试点 2-3 满足 N≤1000。
  • 测试点 4-6 满足 K≤5。
  • 测试点 7-9 满足Q≤105。
  • 测试点 10-12 没有额外限制。

输入格式:

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

第二行包含 N 个空格分隔的整数 A1,A2,…,AN。

第三行包含一个整数 Q。

以下 Q 行每行包含两个空格分隔的整数Li 和 Ri。

输出格式:

对于每个询问[Li,Ri]，你应当在新的一行内输出 ALi,ALi+1…,ARi 的不下降子序列的数量模 109+7 的余数。

样例输入:

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

样例输出:

3
4
20

提示:

对于第一个询问，不下降子序列为 ()、(2) 和 (3)。(2,3) 不是一个不下降子序列，因为A2≰A3。

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

时间限制: 1000ms
空间限制: 256MB

来源: USACO 2020 JAN Platinum