蔚来多校第七场K题（博弈论）

博弈论部分：

有$nn$堆石子，第$ii$堆有$a_{i}a\_i$个，每次可以选择一堆石子取走若干个（不能不取），然后选择不动或者将这堆石子剩余部分与另外一堆石子个数大于0的石子合并，问先手是否存在必胜策略。

solution ：

（1）首先，当堆数为$11$时，显然先手必胜。

（2）当有偶数堆时

<1> 可以选择将偶数堆变为奇数堆

<2> 当 $(a_1-1)xor(a_2-1)xor\mathrm{.}\mathrm{.}\mathrm{.}xor(a_n-1)=0(a\_1-1)\; \backslash \; xor\; \backslash \; (a\_2-1)\backslash \; xor...xor\backslash \; (a\_n-1)=0$ 时，经过一系列步骤在石子堆数变为奇数堆时后手，反之若异或和不为0，可以先/后手。

（3）当有奇数堆（堆数>2）时，先手可以将堆数变为偶数，且使 $(a_1-1)xor(a_2-1)xor\mathrm{.}\mathrm{.}\mathrm{.}xor(a_{n-1}-1)=0(a\_1-1)\; \backslash \; xor\; \backslash \; (a\_2-1)\backslash \; xor...xor\backslash \; (a\_\{n-1\}-1)=0$

下面给出（3）的证明：

假设当前有$(a_1-1)xor(a_2-1)xor\mathrm{.}\mathrm{.}\mathrm{.}xor(a_n-1)=k(a\_1-1)\; \backslash \; xor\; \backslash \; (a\_2-1)\backslash \; xor...xor\backslash \; (a\_\{n\}-1)=k$

我们希望将某个$a_{i}a\_i$拿取一部分并进行调整，某个$a_j-1a\_j-1$变为$(a_j-1)xor(a_i-1)xork(a\_j-1)\backslash \; xor\backslash \; (a\_i-1)\backslash \; xor\backslash \; k$，且有$(a_j-1)xork>a_j-1(a\_j-1)\backslash \; xor\backslash \; k>a\_j-1$和$(a_j-1)xork-(a_j-1)\le a_i-1(a\_j-1)\backslash \; xor\backslash \; k-(a\_j-1)\backslash le\; a\_i-1$

为了方便，接下来的讨论默认每个$a_{i}a\_i$减一

针对题解的取石子堆数的最大值操作，给出反例

26 25 22 17 3
假设我们对26这一堆进行操作
每个石子堆均-1可得：
25 24 21 16 2
我们可以将[0,25]个石子放到某一堆上
观察到24^21^16^2=31
24^31=7
21^31=10
16^31=15
2^31=29
所以只能将[0,25]个石子加到2这一堆
但是2+25<29所以不能将异或和变为0

我们假设$kk$的第$tt$位（最高位）为1，则一定存在至少1个$a_{i}a\_i$的第t位为1，我们选出某个第$tt$位为1的$a_{i}a\_i$，此时 $kxor{a}_{i}k\backslash \; xor\backslash \; a\_i$的第t位为0。

<1>若$a_{i}xork=0a\_i\backslash \; xor\backslash \; k=0$，则直接全部取空即可。

<2>若$a_{i}a\_i$的前$t-1t-1$位不都为0，则$a_{i}xorka\_i\backslash \; xor\backslash \; k$的最高位在前$t-1t-1$位（假设为第$ss$位，$a_{i}a\_i$的第$ss$位也为1）出现，则此时剩余的石子堆数有奇数堆第$ss$位为1。

• 若第t位为1的堆数均在前面所述的奇数堆出现（偶数次），则存在第$ss$位为0且第$tt$位为0的石子堆$jj$且$a_{j}xor{a}_{i}xork>a_{j}a\_j\backslash \; xor\backslash \; a\_i\backslash \; xor\backslash \; k>\; a\_j$，因为$a_{i}a\_i$的第$tt$位为1，所以有$a_{j}xor{a}_{i}xork-a_j\le a_{i}a\_j\backslash \; xor\backslash \; a\_i\backslash \; xor\backslash \; k-\; a\_j\backslash le\; a\_i$。

• 若第t为为1的堆数不都出现在前面所述的奇数堆，则存在第$ss$位为0且第$tt$位为1的石子堆$jj$且$a_{j}xor{a}_{i}xork>a_{j}a\_j\backslash \; xor\backslash \; a\_i\backslash \; xor\backslash \; k>\; a\_j$，显然此时$a_{j}xor{a}_{i}xork-a_j\le a_{i}a\_j\backslash \; xor\backslash \; a\_i\backslash \; xor\backslash \; k-\; a\_j\backslash le\; a\_i$。

<3>若$a_{i}a\_i$的前$t-1t-1$位都为0，则剩下的石子堆里若 $a_{j}xor{a}_{i}xork>a_{j}a\_j\backslash \; xor\backslash \; a\_i\backslash \; xor\backslash \; k>\; a\_j$，该石子堆可以调整至 $a_{j}xor{a}_{i}xorka\_j\backslash \; xor\backslash \; a\_i\backslash \; xor\backslash \; k$，这是因为$a_{i}a\_i$的第$tt$位为1，而$a_{j}a\_j$第$tt$为0时，$a_{j}xor{a}_{i}xorka\_j\backslash \; xor\backslash \; a\_i\backslash \; xor\backslash \; k$第$tt$位也为0，$a_{j}a\_j$第$tt$位为1时，$a_{j}xor{a}_{i}xorka\_j\backslash \; xor\backslash \; a\_i\backslash \; xor\backslash \; k$第$tt$位也为1，怎么调整石子都是够的。

• 因此只需证明$\mathrm{\exists }j,a_{j}xor{a}_{i}xork>a_j\backslash exist\; j,a\_j\backslash \; xor\backslash \; a\_i\backslash \; xor\backslash \; k>\; a\_j$，假设$a_{i}xorka\_i\backslash \; xor\backslash \; k$最高的为1的位为第$rr$位（一定存在），所以该位为1的有奇数堆，因为总共有偶数堆，则存在某个堆的石子个数第$rr$位为0，得证。

综上所述，当石子堆数为偶数且$(a_1-1)xor(a_2-1)xor\mathrm{.}\mathrm{.}\mathrm{.}xor(a_n-1)=0(a\_1-1)\; \backslash \; xor\; \backslash \; (a\_2-1)\backslash \; xor...xor\backslash \; (a\_n-1)=0$时先手必败，否则先手必胜。