CF1572B Xor of 3
做多了这种题，感觉好套路。。
首先观察操作性质，有一个有解的必要条件：所有值异或和为 \(0\)，因为每次操作不会改变 \(1\) 的个数的奇偶性。然后再观察一下，发现如果从前缀异或和的角度看待这个操作会变得非常简单，大概就是
\[s_{k-1}, s_k, s_{k+1}, s_{k + 2} \rightarrow s_{k - 1}, s_{k + 2}, s_{k - 1}, s_{k + 2}
\]
注意到偶数位置和奇数位置的值互不影响的，所以考虑奇偶性。
首先来看 \(n\) 为奇数的情况。这时候不难看出偶数位置可以通过操作 \(1,3,5......,(n-2)\) 来全部变成零，所以现在只需考虑奇数位，由上面的必要条件有 \(s_n = 0\)，所以可以操作 \((n-2),(n-4)......,1\) 全部变成 \(0\)。
然后是 \(n\) 为偶数的情况。我们希望沿用上面的做法，结果发现充要条件在样例就假掉了。思考这是为什么。考察这种情况和 \(n\) 为奇数的情况有何区别：就是我们没有办法通过 \(1,3,5......\) 把偶数位全部消成 \(0\)，但是可以通过 \((n-2),(n-4)......\) 把偶数位全部消成 \(0\)，相应的，奇数位就寄掉了。所以需要考虑奇数位，这时候就很明显了：有解还需满足奇数位存在 \(0\)，我们可以通过两边的操作把剩下的奇数位消成 \(0\)，这样这道题就做完了。
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
namespace IO {
#define isdigit(x) (x >= '0' && x <= '9')
template<typename T>
inline void read(T &x) {
x = 0; char ch = getchar(); int f = 0;
for(; !isdigit(ch); ch = getchar()) if(ch == '-') f = 1;
for(; isdigit(ch); ch = getchar()) x = x * 10 + ch - '0';
if(f) x = -x;
}
template<typename T>
inline void write(T x) {
if(x < 0) putchar('-'), x = -x;
if(x > 9) write(x / 10);
putchar(x % 10 + '0');
}
#undef isdigit
}
using namespace IO;
const int N = 2e5 + 10;
int n, a[N], s[N];
int ans[N];
void solve() {
read(n);
for(int i = 1; i <= n; ++i)
read(a[i]), s[i] = s[i - 1] ^ a[i];
int tot = 0;
if(n & 1) {
if(s[n] == 1) {
puts("NO");
return;
}
for(int i = n - 2; i >= 1; i -= 2)
ans[++tot] = i;
for(int i = 3; i + 2 <= n; i += 2)
ans[++tot] = i;
}
else {
int pos = 0;
for(int i = 1; i <= n; i += 2)
if(s[i] == 0) {
pos = i;
break;
}
if(!pos || s[n] == 1) {
puts("NO");
return ;
}
for(int i = pos + 1; i + 2 <= n; i += 2)
ans[++tot] = i;
for(int i = pos - 2; i >= 1; i -= 2)
ans[++tot] = i;
for(int i = n - 2; i >= 1; i -= 2)
ans[++tot] = i;
}
puts("YES");
printf("%d\n",tot);
for(int i = 1; i <= tot; ++i)
printf("%d ",ans[i]);
puts("");
}
int main() {
int T; read(T);
while(T--) solve();
}