-
首先最终的状态是所有堆都为0
$0$^$0$^$0$^$0$ = $0$
先手必败状态:$a1$ ^ $a2$ ^ $a3$ ^ … ^$an= 0$
先手必胜状态:$a1$ ^ $a2$ ^ $a3$ ^ … ^$an≠ 0$ -
$a_{1}$^$a_{2}$^…^$a_{i}$^$a_{i+1}$…^$a_{n}$非零时,总可以找到一个拿石子的方案使得拿完后异或$=0$
从$a_{i}$中拿走$a_{i}-(a_{i}$^$x)$堆石子
剩下$a_{i}-(a_{i}-(a_{i}$^$x))$ = $a_{i}$^$x$
$a_{i}$剩下的部分和其他的异或
=$a_{1}$^$a_{2}$^…^$a_{i}$^$x$^$a_{i+1}$…^$a_{n+1}$
=$x$^$x$
=$0$
所以 则证明了当$a_{1}$^$a_{2}$^…^$a_{i}$^$a_{i+1}$…^$a_{n+1}$非零时,总可以找到一个拿石子的方案使得拿完后异或$=0$可以走到让对手必败,则自己必胜
- 当$a_{1}$^$a_{2}$^…^$a_{i}$^$a_{i+1}$…^$a_{n+1}$为零时,不管怎么拿,剩下的所有数的异或一定不是0
当$a_{1}$^$a_{2}$^…^$a_{i}$^$a_{i+1}$…^$a_{n}$为零时,假设
$a_{i}$拿完后变成$a’_{i}$,拿完后的异或和==0
所有数异或变成$a_{1}$^$a_{2}$^…^$a_{i}’$ ^ $a_{i+1}$…^$a_{n+1}$
此时我们让拿之前的异或$a_{1}$^$a_{2}$^…^$a_{i}$^$a_{i+1}$…^$a_{n}$和拿之后的异或$a_{1}$^$a_{2}$^…^$a_{i}’$ ^ $a_{i+1}$…^$a_{n}$做异或,除$a_{i}’$外其他项两两消掉只剩下$a_{i}$^$a_{i}’$==0则需要$a_{i}$==$a_{i}’$,与$a_{i}’$是$a_{i}$拿走一部分后的数($a_{i}’$<$a_{i}$矛盾)
所以有 当$a_{1}$^$a_{2}$^…^$a_{i}$^$a_{i+1}$…^$a_{n+1}$为零时,不管怎么拿,剩下的所有数的异或一定不是0,即此时不管怎么走都是走到让对手必胜,则自己必败
blablabla