#P17829. [Ontak2022]LSQ

    ID: 16772 传统题 500~5000ms 512MiB 尝试: 1 已通过: 1 难度: 8 上传者: 标签>字符串CF2500递归数学构造算法基础模拟

[Ontak2022]LSQ

题目描述

记 inc⁡(A,d,m)\operatorname{inc}(A,d,m) 为将数组 AA 中的每个元素加上 dd 后对 mm 取模,记 ⊕\oplus 为数组拼接。

定义:

arr⁡(0,m)=[0],\operatorname{arr}(0,m)=[0], $$\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).$$

例如 m=3m=3 时,前几项为:

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]

令 H=101010100+1H=10^{10^{10^{100}}}+1,并令 S=arr⁡(H,m)S=\operatorname{arr}(H,m)。

给定长度为 nn 的数组 VV,判断它是否作为连续子数组出现在 SS 中。如果出现,求其第一次出现的起始下标;下标从0开始。

输入格式

第一行一个整数 tt,表示测试组数。

每组第一行两个整数 n,mn,m,第二行 nn 个整数 v0,…,vn−1v_0,\ldots,v_{n-1}。

输出格式

每组输出一行。如果不存在,输出 -1;否则先求真实的最小起始下标 xx,再输出 x mod (109+7)x\bmod(10^9+7)。不能在取模后的下标中选最小值。

数据范围

1≤t≤5000001\le t\le500000;1≤n≤5000001\le n\le500000;1≤m≤1091\le m\le10^9;0≤vi<m0\le v_i<m;所有测试组的 nn 之和不超过500000。

原题说明:常数 HH 足够大;对范围内的任意 VV,它要么已经出现在 arr⁡(H,m)\operatorname{arr}(H,m) 中,要么不会出现在任何层数的数组中。

子任务

子任务 附加限制 分值
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