← 返回题目列表

AtCoder · abc454_f

I. 让它回文 2

中文机器翻译题面 查看原题

分数: 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.