#P16713. Tspin double

Tspin double

题目描述

给定正整数 n,mn,m、非负整数 xx,以及序列 a1,a2,…,ana_1,a_2,\ldots,a_n。

每次操作可以选择序列中的一个数,将它加 11 或减 11;操作后该数不能变为负数。

请求出至少需要进行多少次操作,才能使序列中所有数的异或和等于 xx。

输入格式

第一行一个正整数 TT,表示数据组数。

对于每组数据:

  • 第一行两个正整数 n,mn,m 和一个非负整数 xx;
  • 第二行 nn 个非负整数 a1,a2,…,ana_1,a_2,\ldots,a_n。

输出格式

输出 TT 行,每行一个整数,表示对应数据的答案。

数据范围

测试点编号 ∑n≤\sum n\le m≤m\le
1∼31\sim 3 10310^3 1010
4∼64\sim 6 10510^5
7∼107\sim 10 6060

对于所有数据:

T≤104,0≤x,a1,a2,…,an<2m.T\le 10^4,\qquad 0\le x,a_1,a_2,\ldots,a_n<2^m.