int n,m,k,a[MAXN],t[MAXN][MAXN];
int f(int x,int y);
int g(int x,int y){
if(!x||!y)return 1<<(x|y);
if(~t[x][y])return t[x][y];
int res=1;
for(int i=0;i<=N;i++)if((1ll<<i)&(x^y))res<<=1ll<<i;
for(int i=0;i<=N;i++)if((1ll<<i)&(x&y))res=f(res,3ll<<((1ll<<i)-1));
return t[x][y]=t[y][x]=res;
}
int f(int x,int y){
if(!x||!y)return x|y;
if(x==1||y==1)return x^y^1;
int res=0;
for(int i=0;i<=N;i++)if((1ll<<i)&x)for(int j=0;j<=N;j++)if((1ll<<j)&y)res^=g(i,j);
return res;
}
三维 Nim 积
上述问题换成三维。
解法
三个数积起来即可。
博弈论相关题目
CF1704F Colouring Game
题目大意
Alice 和 Bob 在玩游戏。有 n 个格子排成一行，每个格子被涂成了红色或蓝色。 Alice 每次操作选择两个相邻的格子，要求其中至少有一个是红色，然后把这两个格子涂成白色。 Bob 每次操作选择两个相邻的格子，要求其中至少有一个是蓝色，然后把这两个格子涂成白色。 他们轮流进行操作（Alice 先手），不能操作的人就输了。 现在给定初始局面，请问在他们都足够聪明的前提下，谁会获得胜利？
题解
博弈论题目，可以先考虑其规则有哪些性质，玩家的策略是怎样的。
对于此题，就考虑，如果我是 Alice，我的策略是什么。
我希望尽可能多的操作，也就是说，我希望我的操作次数尽量多。对应的，我希望对方的操作次数尽量少。
观察题目，发现对于两人而言，每次操作一定会减少至少一个自己代表色的颜色块，同时颜色块数量不会增加。
那么为了尽可能增加我的操作次数，减少对方的操作次数，我应该优先取走形如 RB 或 BR 的颜色块。
对应的，对方的策略也相同。也就是说，Alice 和 Bob 在场上存在 RB 或 BR 块时，一定优先取这些块。
那么当场上不存在这些块时怎么办？
此时，因为场上不存在 RB 或 BR，那么每个连续非白颜色块将只有一种颜色。
任何人都无法减少对方的操作次数，只能增加自己的操作次数。
那么此时的策略应该是从两侧开始取，每次操作一个颜色块和一个白块。
于是，每个人的操作次数便是剩余的自己代表色色块数量。
假设某个时刻，场上已经不存在 RB 或 BR，此时有 x 个 R，y 个 B。
如果 x>y，那么 Alice 将获胜。
如果 x=y，那么后手获胜。
如果 x<y，那么 Bob 将获胜。
也就是说，当 x\ne y 时，获胜方是不由谁是先手而决定的。
同时，注意到每次取走一个 RB 或 BR 段时，R 和 B 的差并不会改变。综上可以得到，当场上 R 和 B 数量不相等时，胜者已经确定了。
## 题解
操作本质上相当于：先手选择一个点，后手选择一个方向，之后两人交替着取完剩下的部分，之后再选让我们称这个过程为一轮。
那么考虑什么时候先后手会交换：选择的方向上有奇数个石子。
因为与奇偶性相关，于是我们考虑分讨 $n$ 的奇偶性。
当 $n$ 是偶数时：
首先，Alice 至少可以取到所有奇数或者所有偶数。这对应了初始选 $1$ 或 $n$。
这同时也使 Bob 取到答案最大值。
如果 Alice 没有选 $1$ 或 $n$，说明通过操作可以使取到的石子数量更多。
Bob 希望 Bob 取得尽量多，相当于 Bob 希望 Alice 取得尽量少。
那么 Bob 如果存在方案使 Alice 取不到比全奇或全偶更优的，Bob 便取到了 Bob 的最大值。
假设 Alice 先选择了某个点，因为 $n$ 是偶数，Bob 一定可以选择一个方向使下一轮 Bob 变为先手。
既然 Bob 变成了先手，他可以选一个边上的使得 Alice 只能取到全奇或者全偶，这是 Bob 的最优答案。
即 ${XXXXX}\red{A}{BA}\to {XXXX}\red{B}{ABA}\to {BABABABA}$。
也就是说 Bob 总有方案使得 Alice 只能取全奇或全偶，那么 Alice 便只能取奇偶中较大者。
当 $n$ 是奇数时：
此时 Bob 不一定有方案使自己取到先手。
还是考虑 Alice 答案的最小值，全奇显然有，全偶也可以有，因为选择任意偶数后先后手不会改变。
由此，会发现 Alice 始终不会将先手权让给 Bob，因为 Bob 为了最小化 Alice 的收益一定会立马选全奇或者全偶，那还不如让 Alice 自己来选。
在 $n$ 是奇数时，Alice 一直保持先手权的方法就是每次选的点都是偶数。
但这样答案相当于全偶，为了让答案更大，Alice 应该选选奇数。
因为始终不能交出先手权，所以只有最后一轮 Alice 可以选择奇数点，并且对于剩下部分的奇数全取。
这段区间应当是一个连续的区间，我们只需考虑它在哪以及如何取到。
为了方便考虑，我们重新定义权值，定义奇数位置的权值是正的，偶数位置的权值是负的。
而 Alice 初始拥有所有偶数，它可以选择一个区间并得到区间内的权值和（舍弃部分偶数取奇数）。
但区间并不能随意选择，因为 Bob 会最小化这个值。
当 Alice 每次选完点后，Bob 都会选择这个点两侧的一个区间并禁止 Alice 去选。
注意到，这些决策形成一个类似线段树的结构，Alice 最后会停在一个叶子上，而 Bob 每次删掉一个区间，那么 Bob 一定能促使 Alice 最后选的区间是最小的叶子区间。
考虑最小的叶子区间最大会是多少，一个标准的二分答案的形式，检查是否存在若干个大于等于 $x$ 的区间即可。
具体的，维护最小合法点前缀和，每次判断当前点是否是合法点，如果 $n$ 合法即存在合法划分。