异或高斯消元
题干概述
在一片古老遗迹的深处，两位旅人发现了一排排风化的石块，相邻的石块之间用生锈的金属环连接。每一排都形成一条链，而墙上模糊的刻文将这种游戏称为「链上 Nim」。
一条长度为 LL 的链包含 LL 个顶点和 L−1L−1 条连边。玩家 11 先手，之后两位玩家轮流行动。在每一回合，当前玩家选择一条链，并按照固定的游戏规则在其中进行一次合法操作。这是一个公平组合游戏：可以选择的操作只取决于当前局面，而与轮到了哪位玩家无关。无法继续行动的玩家判负。
可惜，刻文中记载具体操作规则的部分已经损坏。两位旅人只知道，根据 Sprague--Grundy 定理，每条链仍然有唯一的非负整数SG 值。对于每个可能的链长 LL，记一条该长度链的 SG 值为 GLGL。
一场游戏可以在若干条非空、彼此独立的链上同时进行。每次行动只会影响玩家选中的那一条链。因此，若一个局面中各条链的长度为 L1,L2,…,LCL1,L2,…,LC，那么整个局面的 SG 值等于各条链 SG 值的Nim 和，也就是按位异或和：
GL1xorGL2xor⋯xorGLC.GL1xorGL2xor⋯xorGLC.
一位新人曾经旁观了 KK 个历史局面。对于每场过去的游戏，他记下了局面中所有链的长度，并向熟悉游戏的玩家询问了整个局面的 SG 值。然而，他并不知道每个 GLGL 分别是多少。
现在，他又遇到了 QQ 个新局面，并想知道：
「只使用笔记中的历史记录，能否唯一确定这个局面的 SG 值？」
如果根据历史记录能够唯一确定这个局面的 SG 值，就输出这个值；如果无法确定，就输出 −1−1。
Input
第一行包含一个整数 TT（1≤T≤101≤T≤10），表示测试用例的数量。
接下来依次描述 TT 组测试用例。对于每组测试用例：
第一行包含一个整数 KK（1≤K≤1001≤K≤100），表示历史局面数量。
接下来的 KK 个历史局面均恰好用两行描述：
- 第一行包含两个整数 CC 和 SS（1≤C≤1001≤C≤100，0≤S≤1040≤S≤104），分别表示链的数量和该局面的已知 SG 值。
- 第二行恰好包含 CC 个整数 L1,L2,…,LCL1,L2,…,LC（1≤Li≤1001≤Li≤100），表示以顶点数计算的各条链的长度。
接下来一行包含一个整数 QQ（1≤Q≤1001≤Q≤100），表示询问数量。
接下来的 QQ 个询问均恰好用两行描述：
- 第一行包含一个整数 DD（1≤D≤1001≤D≤100），表示链的数量。
- 第二行恰好包含 DD 个整数 R1,R2,…,RDR1,R2,…,RD（1≤Ri≤1001≤Ri≤100），表示以顶点数计算的各条链的长度。
链长可以以任意顺序给出，也可以重复。所有被描述的局面都不为空。
Output
对于每组测试用例中的每个询问，输出一行一个整数。
Sample Input
1 2 2 5 1 2 2 6 2 3 5 2 1 2 2 1 3 1 1 2 4 4 1 4
Sample Output
5 3 -1 0 -1
对于这个题，可以理解为，在可能有1-100个未知量，我给出若干个异或线性方程组，最后给出一个查询方程，看这个方程能不能由之前的方程组给出，那么和高斯消元（线性代数解有唯一解的方程组）类似，我们可以把每个方程当作一个基向量，每次保留未出现过的当前方程位最高的未知量，对于异或方程，我们计算基向量要减去当前向量，（__int128）mask^=r[i]即可,对应的sg值相当于增广矩阵的右值，s^=sg[i],找到第一个非0位更新返回，之后查询即可（100位要从1-100，不是0-99），简要代码如下：
#include <bits/stdc++.h> using namespace std; __int128 ini = 0; long long had[101], sg[101]; __int128 r[101]; void insert(__int128 mask, int s) { for (int i = 100; i >= 0; i--) { if (!((mask >> i & 1))) continue; if (!had[i]) { had[i] = true; r[i] = mask; sg[i] = s; return; } mask ^= r[i]; // 基向量相消 s ^= sg[i]; } } long long query(__int128 mask, long long s) { for (int i = 100; i >= 0; i--) { if (!(mask >> i & 1)) continue; if (!had[i]) return -1; mask ^= r[i]; // 消去当前 s ^= sg[i]; } return s; } int main() { int t; cin >> t; while (t--) { memset(had, 0, sizeof(had)); memset(sg, 0, sizeof(sg)); memset(r, 0, sizeof(r)); int n; cin >> n; while (n--) { int c, s; cin >> c >> s; __int128 mask = 0; while (c--) { int l; cin >> l; mask ^= ((__int128)1 << l); } insert(mask, s); } int q; cin >> q; while (q--) { __int128 mask = 0; int len; cin >> len; while (len--) { int ri; cin >> ri; mask ^= (__int128)1 << ri; } cout << query(mask, 0) << "\n"; } } }