#P12470. [2025年福建省队集训]trans

    ID: 11633 传统题 1000ms 1024MiB 尝试: 5 已通过: 1 难度: 9 上传者: 标签>CF2800省选/NOI-一维前缀和前后缀最值一维差分延迟决策交换论证

[2025年福建省队集训]trans

题目描述

给定一个长度为 nn 的整数序列 aa(下标从 11 开始),你可以进行以下操作若干次:

  • 选择一个区间 [l,r][l,r],对于所有 i∈N,x∈{0,1},l+3i+x≤ri \in N,x \in \{0,1\},l+3i+x \le r,将 al+3i+xa_{l+3i+x} 增加 (−1)x(−1)^x。
    问至少需要多少次操作,才能使 aa 序列的所有位置值均为0,若无解,则输出 −1−1。

输入格式

第一行两个正整数 T,nT,n,表示数据组数以及每组数据的序列长度。
接下来 TT 行,每行一个长度为 nn 的整数序列 aa。

输出格式

T 行,每行一个数,表示对应的数据的答案。

样例输入 #1

4 5
-1 0 1 -1 1
-1 -2 -3 -4 5
-11 -45 14 -1919 810
-1 -2 3 4 -5

样例输出 #1

2
11
1975
-1

样例解释 #1

对于第一组数据,进行操作 [1,5],[2,3][1,5],[2,3] 即可。

样例 2,3,4,5

见附加文件。

数据范围

对于所有测试数据,保证 T=30T =30。

测试点编号 n=n= ∣ai∣≤\lvert a_i\rvert\le
11 55
22 2020 1010
33 7070 100100
4,54,5 200200 101010^{10}
6,76,7 2×1032\times 10^3
8,9,108,9,10 3×1043\times 10^4 101010^{10}

提示

题目顺序是瞎排的。