CF1438D Powerful Ksenia

题目来源：Codeforces, Codeforces Round #682 (Div. 2)，CF1438D Powerful Ksenia

题目大意

题目链接

给出 (n) 个正整数 (a_1,a_2,dots,a_n)。

在一次操作中，你可以：

选择三个不同的下标 (i), (j), (k)。
将 (a_i), (a_j), (a_k) 三个值，全部置为 ((a_ioperatorname{xor} a_joperatorname{xor} a_k))。

请通过不超过 (n) 次操作，使得序列里所有数都相等。注意：不需要最小化操作数量。

数据范围：(1leq nleq 10^5)，(1leq a_ileq 10^9)。

本题题解

首先，当 (n) 为奇数时，不论 (a) 中的数是什么，我们一定可以构造出一组解。具体方法如下：

考虑，如果序列里，除某个数 (a_p) 外，其他（剩下偶数个数）数能两两配对，使得每对数相等。设配出的 (frac{n-1}{2}) 对下标分别为 ((u_1,v_1),(u_2,v_2),dots,(u_{frac{n-1}{2}},v_{frac{n-1}{2}}))。则我们接下来只需要依次操作：

((p,u_1,v_1))
((p,u_2,v_2))
(dots)
((p,u_{frac{n-1}{2}},v_{frac{n-1}{2}}))

就能使得序列里所有数都等于 (a_p)。这是因为 (a_{u_i}=a_{v_i})，所以每次三个数异或起来时，(a_{u_i},a_{v_i}) 就会自己抵消掉，剩下 (a_p)。即：(forall i:(a_{u_i}operatorname{xor}a_{v_i}operatorname{xor}a_p)=a_p)。这部分一共需要 (frac{n-1}{2}) 次操作。

思考如何达到这种 (frac{n-1}{2}) 对数两两相等的局面。可以依次对所有 (i=1,3,5,dots ,n-2)，做操作 ((i,i+1,i+2))。这样，就能使所有 ((i,i+1)) 相等（(i=1,3,5,dots,n-2)）。最后剩下 (p=n)。然后进行上述操作即可。

总共需要 (frac{n-1}{2}+frac{n-1}{2} = n-1) 次操作。

当 (n) 是偶数时，首先要观察到，一次操作不会改变序列里所有数的异或和。而最终序列中要求所有数都相等，异或和一定是 (0)，所以原序列的异或和也一定要是 (0)。

那么首先判断，如果原序列异或和不为 (0)，则直接输出 ( ext{NO})。

否则我们随便拿出一个数，不妨拿出 (a_n)。剩下奇数个数 (a_1,a_2,dots,a_{n-1})，通过上述的构造，一定能变成所有数都相等的情况，设这个相等的值为 (x)。那么这 (n-1) 个数的异或和也为 (x)。因为序列里所有数异或和为 (0)，所以一定有 (x=a_n)。于是我们根本不需要考虑 (a_n)，直接对前 (n-1) 个数用奇数的方法构造即可。

时间复杂度 (O(n))。

总结

(n) 是奇数的情况，是比较简单的构造。自己手玩一会应该就能看出来。

(n) 是偶数时，用到一个技巧：观察每次操作不变的量（例如本题中是异或和。其他题目有时是奇偶性等等）。那么，开始局面的这个量，必须和目标局面相等。也就是说，我们找到一个必要条件。然后思考这个必要条件是否充分。如果充分，我们也就构造出了操作的方法。

参考代码

// problem: CF1438D
#include <bits/stdc++.h>
using namespace std;

#define pb push_back
#define mk make_pair
#define lob lower_bound
#define upb upper_bound
#define fi first
#define se second
#define SZ(x) ((int)(x).size())

typedef unsigned int uint;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;

template<typename T> inline void ckmax(T& x, T y) { x = (y > x ? y : x); }
template<typename T> inline void ckmin(T& x, T y) { x = (y < x ? y : x); }

const int MAXN = 1e5;
int n, a[MAXN + 5];
struct Oper_t {
	int i, j, k;
	Oper_t() {}
	Oper_t(int _i, int _j, int _k) { i = _i, j = _j, k = _k; }
};
void solve_odd() {
	cout << "YES" << endl;
	vector<Oper_t> ans;
	for (int i = 1; i <= n - 2; i += 2) {
		ans.pb(Oper_t(i, i + 1, i + 2));
	}
	for (int i = 1; i <= n - 2; i += 2) {
		ans.pb(Oper_t(i, i + 1, n));
	}
	cout << SZ(ans) << endl;
	for (int i = 0; i < SZ(ans); ++i) {
		cout << ans[i].i << " " << ans[i].j << " " << ans[i].k << endl;
	}
}
void solve_even() {
	int xorsum = 0;
	for (int i = 1; i <= n; ++i) xorsum ^= a[i];
	if (xorsum) {
		cout << "NO" << endl;
		return;
	}
	--n;
	solve_odd();
}
int main() {
	cin >> n;
	for (int i = 1; i <= n; ++i) cin >> a[i];
	if (n % 2 == 0) {
		solve_even();
	} else {
		solve_odd();
	}
	return 0;
}