#P17829. [Ontak2022]LSQ
[Ontak2022]LSQ
题目描述
记 为将数组 中的每个元素加上 后对 取模,记 为数组拼接。
定义:
$$\operatorname{arr}(k+1,m)=\operatorname{inc}(A,0,m)\oplus\operatorname{inc}(A,1,m)\oplus\cdots\oplus\operatorname{inc}(A,m-1,m),\quad A=\operatorname{arr}(k,m).$$例如 时,前几项为:
arr(0,3) = [0]
arr(1,3) = [0,1,2]
arr(2,3) = [0,1,2,1,2,0,2,0,1]
arr(3,3) = [0,1,2,1,2,0,2,0,1,1,2,0,2,0,1,0,1,2,2,0,1,0,1,2,1,2,0]
令 ,并令 。
给定长度为 的数组 ,判断它是否作为连续子数组出现在 中。如果出现,求其第一次出现的起始下标;下标从0开始。
输入格式
第一行一个整数 ,表示测试组数。
每组第一行两个整数 ,第二行 个整数 。
输出格式
每组输出一行。如果不存在,输出 -1;否则先求真实的最小起始下标 ,再输出 。不能在取模后的下标中选最小值。
数据范围
;;;;所有测试组的 之和不超过500000。
原题说明:常数 足够大;对范围内的任意 ,它要么已经出现在 中,要么不会出现在任何层数的数组中。
子任务
| 子任务 | 附加限制 | 分值 |
|---|---|---|
| 1 | t≤20,n≤50,m≤3 | 10 |
| 2 | t≤20,m≤4,若存在则最小 x≤500000 | |
| 3 | m≤4 | |
| 4 | m≤5 | 30 |
| 5 | m≤n | |
| 6 | 无额外限制 | 10 |
样例 1
输入:
5
4 2
1 0 1 1
5 3
2 0 1 2 1
20 6
2 4 5 0 1 2 3 5 0 1 2 3 4 0 1 2 3 4 5 1
2 10000000
5 5
5 5
4 3 2 1 0
输出:
11
134
83
273492549
-1