A-加减_2023年“华为”杯广东工业大学第十七届程序设计竞赛（同步赛）

加减

比赛主页

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

给定一个长度为 n 的序列 $a=(a_1,\cdots,a_n)$ ，一个正整数 m，以及一个非负整数 k，下标从 0 开始的无穷序列 b 如下所示： $b_i=\begin{cases}(-1)^i\binom{k}{i}&0\leq i\leq k\\ 0&i>k\end{cases}$

你可以对序列 a 执行以下操作：

选择两个后缀，其中一个在模 m 意义下加上序列 b，另一个在模 m 意义下减去序列 b，形式化描述如下：

选择两个整数 x, y 满足 $1 \le x,y \le n$ ，注意可以 x = y；
将 $a_x,a_{x+1},\cdots ,a_n$ 修改为 $(a_x+b_0)\mod m, (a_{x+1}+b_1)\mod m,\cdots,(a_n+b_{n-x})\mod m$ ；
将 $a_y,a_{y+1},\cdots ,a_n$ 修改为 $(a_y-b_0)\mod m,(a_{y+1}-b_1)\mod m,\cdots,(a_n-b_{n-y}) \mod m$ 。

注意操作3.是在操作2.修改完后的数组上进行，执行以上三步算一次操作。要求操作结束后序列 a 为全0序列，输出最少操作次数，若无解输出-1。

符号说明：

$\binom{k}{i}$ : k 个不同的球里取 i 个的取法方案数。

$a \mod b=a - \lfloor\frac{a}{b}\rfloor b$ ，其中 $\lfloor x\rfloor$ 表示对 x 下取整，例如：

$\lfloor -0.1\rfloor=-1$ ；

$\lfloor 0.1\rfloor=0$ ；

$5 \mod 3=2$ ；

$-5 \mod 3=1$

输入描述:

每个测试点包含多个测试用例；

第一行一个整数 T ( $1 \le T \le 10^5$ )---表示测试用例的数量。每个测试用例的格式如下：

第一行三个整数 n, k, m ( $1 \le n \le 10^5$ , $1\le k \le 200$ ， $1 \le m \le 10^9$ )---分别表示序列长度以及给定的 k 和模数；

第二行 n 个整数 $a_1,\cdots,a_n$ ( $0\le a_i < m$ )---表示给定的序列；

保证所有测试用例的 n 之和不超过 $10^5$ 。

输出描述:

有 T 组输出，每组输出的格式如下：

第一行如果答案存在则输出最少操作次数，否则输出-1；

示例1

输入

复制

输出

复制

1
-1