3460: Period Sequence
内存限制：64 MB
时间限制：6.000 S
评测方式：文本比较
命题人：
提交：1
解决：1
题目描述
Chiaki has n integers s0,s1,…,sn−1. She has defined an infinite sequence S in the following way: Sk=skmodn+n⋅⌊k/n⌋, where k is a zero based index.
For a continuous subsequence S[l..r], let cntx be the number of occurrence of x in the subsequence S[l..r]. Then the value of S[l..r] is defined as follows
For two integers a and b (a≤b), Chiaki would like to find the value of
For a continuous subsequence S[l..r], let cntx be the number of occurrence of x in the subsequence S[l..r]. Then the value of S[l..r] is defined as follows
For two integers a and b (a≤b), Chiaki would like to find the value of
输入
There are multiple test cases. The first line of input contains an integer T, indicating the number of test cases. For each test case:
The first line contains three integers n, a and b (1≤n≤2000,0≤a≤b≤1018).
The second line contains n integers s0,s1,…,sn−1 (0≤si≤109).
It is guaranteed that the sum of all n does not exceed 20000.
The first line contains three integers n, a and b (1≤n≤2000,0≤a≤b≤1018).
The second line contains n integers s0,s1,…,sn−1 (0≤si≤109).
It is guaranteed that the sum of all n does not exceed 20000.
输出
For each test case, output an integer denoting the answer.
样例输入 复制
4
3 2 6
2 1 3
5 2 7
2 1 5 1 2
4 4 8
2 1 5 17
3 5 9
2 5 2样例输出 复制
179
268
369
437