luoguP3185 [HNOI2007]分裂游戏 枚举 + 博弈论

---

每个位置的瓶子中的每个石子是一个独立的游戏

只要计算出他们的\(sg\)值即可

至于方案数，反正不多\(n^3\)暴力枚举即可

反正怎么暴力都能过啊

复杂度\(O(Tn^3)\)

---

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

using namespace std;

#define ll long long

#define ri register int

#define rep(io, st, ed) for(ri io = st; io <= ed; io ++)

#define drep(io, ed, st) for(ri io = ed; io >= st; io --)

#define gc getchar

inline int read() {

	int p = 0, w = 1; char c = gc();

	while(c < '0' || c > '9') { if(c == '-') w = -1; c = gc(); }

	while(c >= '0' && c <= '9') p = p * 10 + c - '0', c = gc();

	return p * w;

}

int n, sg[25], mex[105];

inline void get_sg() {

	sg[n] = 0;

	drep(i, n - 1, 1) {

		memset(mex, 0, sizeof(mex));

		rep(j, i + 1, n) rep(k, j, n)

		mex[sg[j] ^ sg[k]] = 1;

		rep(j, 0, 100)

		if(!mex[j]) { sg[i] = j; break; }

	}

}

int main() {

	int T = read();

	while(T --) {

		n = read(); get_sg();

		int SG = 0;

		rep(i, 1, n) SG ^= (read() & 1) * sg[i];

		if(!SG) {

			printf("-1 -1 -1\n");

			printf("0\n"); continue;

		}

		int ans = 0, flag = 0;

		rep(i, 1, n) rep(j, i + 1, n) rep(k, j, n)

			if((SG ^ sg[i] ^ sg[j] ^ sg[k]) == 0) {

				if(!flag) { printf("%d %d %d\n", i - 1, j - 1, k - 1); flag = 1; }

				ans ++;

			}

		printf("%d\n", ans);

	}

	return 0;

}