博弈杂题选做
最近遇到了过量的博弈问题，先手和后手都很聪明，但是我不聪明/youl
Christmas Game
传送门
容易发现只有深度模 kkk 同余的点之间是相关的，而相关点之间是一个阶梯博弈的模型，即一个人移动偶数位置上的石子，另一个人一定可以将这些石子再移回奇数位置。于是偶数位置全部等价于根，变成了奇数位置上的 Nim 博弈问题。
于是设 f[x][i][0/1]f[x][i][0/1]f[x][i][0/1] 表示在 xxx 子树里与 xxx 距离 dismodk=idis\bmod k=idismodk=i 且 ⌊disk⌋mod2=0/1\left\lfloor\frac{dis}{k}\right\rfloor\bmod 2=0/1⌊kdis⌋mod2=0/1 的点的权值异或和，可以换根 dp 求出以每个点为根的答案，注意一些神秘写法需要特判 k=1k=1k=1。
总的胜负就是判断余数为 000 到 k−1k-1k−1 的异或和是否为 000。
Future Failure
传送门
考虑一个字符串有偶数种不同排列的情况，若先手删去某个字符可以使自己必胜，那就删；否则先手可以对字符串进行重排，后手也只能选择重排，最后一定是后手找不到下一种排列，先手必胜。
那奇数种的情况呢？排列数 =n!∏ai!=\dfrac{n!}{\prod a_i!}=∏ai!n!，其中 aia_iai 为第 iii 种字母出现的次数，排列数为奇数即 ∏ai!\prod a_i!∏ai! 中因子 222 的个数等于 n!n!n! 中 222 的个数。若选含 222 最少的 aia_iai（设它含 kkk 个 222）并将其和 nnn 同时减 111，由于 ∑ai=n\sum a_i=n∑ai=n，则 2k∣n2^k\mid n2k∣n，分子分母损失的 222 的个数一样，排列数依然为奇数。
排列数为奇数的时候显然重排操作是没有意义的。若 nnn 为奇数，每人轮流删一个字符，最后后手没字符可删，先手必胜；反之先手必败。
不会子集卷积，可以选择很神奇的 dp，详见第一篇题解，懒得再敲一遍了/qd
未完待续pap