#PU997. USACO 2020 January Contest, Platinum — Problem 2. Non-Decreasing Subsequences
USACO 2020 January Contest, Platinum — Problem 2. Non-Decreasing Subsequences
USACO 2020 January Contest, Platinum — Problem 2. Non-Decreasing Subsequences
题目描述
Bessie was recently taking a USACO contest and encountered the following problem. Of course, Bessie knows how to solve it. But do you? Consider a sequence of length consisting solely of integers in the range You are given () queries of the form For each query, compute the number of non-decreasing subsequences of mod . A non-decreasing subsequence of is a collection of indices such that and Make sure to consider the empty subsequence!
输入格式
The first line contains two space-separated integers and . The second line contains space-separated integers . The third line contains a single integer The next lines each contain two space-separated integers and
输出格式
For each query you should print the number of non-decreasing subsequences of mod on a new line.
数据范围
Test cases 2-3 satisfy . Test cases 4-6 satisfy Test cases 7-9 satisfy Test cases 10-12 satisfy no additional constraints.
样例
样例 1
5 2
1 2 1 1 2
3
2 3
4 5
1 5
3
4
20
For the first query, the non-decreasing subsequences are $(), (2),$ and $(3).$
$(2,3)$ is not a non-decreasing subsequence because
$A_2\not \le A_3.$
For the second query, the non-decreasing subsequences are $()$, $(4)$, $(5)$,
and $(4,5)$.
Problem credits: Benjamin Qi