分数: 525 点
问题陈述
给你一个正整数 N,一个正整数 M,以及一个整数序列 A=(A_1,A_2,\ldots,A_N) 长度 N。保证每个元素 A 介于 0 和 M-1,包括在内。
可以对整数序列执行以下操作 A 任意次数,可能为零:
- 选择一对整数 (l,r) 满意 1\le l\le r\le N,并替换 A_i 与 (A_i+1) \bmod M 对于每个 i=l,l+1,\ldots,r.
找出完成该操作所需的最少操作数 A 回文。
在这里, A 是一个回文,如果 A_i=A_{N+1-i} 成立 i=1,2,\ldots,N.
你被给予 T 测试用例;解决它们中的每一个。
约束
- 1\le T
- 1\le N\le 2\times 10^5
- 1\le M\le 10^9
- 0\le A_i < M
- 总和 N 所有测试用例最多 2\times 10^5.
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
T
\text{case}_1
\text{case}_2
\vdots
\text{case}_T
每个测试用例均按以下格式给出:
N M A_1 A_2 \ldots A_N
输出
按顺序输出测试用例的答案,以换行符分隔。
示例输入 1
3 4 5 0 3 1 2 1 20260418 454 7 12 3 1 4 1 5 9 2
示例输出 1
3 0 5
考虑第一个测试用例。
你可以使 A 回文的三个操作如下:
- 选择 (l,r)=(2,4). A 变为 (0,4,2,3).
- 选择 (l,r)=(3,4). A 变为 (0,4,3,4).
- 选择 (l,r)=(3,4). A 变为 (0,4,4,0).
不可能使 A 回文数少于三个操作,因此输出 3.