NIM游戏

nim游戏的原型是这样的，有n堆石子，每次可以任意从某一堆中取任意的石子数，最后不能取的判负。

这种问题的通解是异或和，把所有堆的石子数异或起来，等于0是必败，反之必胜。

所谓必胜是能找到一种拿石子的方法，使得后手面对的是必败的状态。
所谓必败是不管怎么拿，后手都是一种必胜的状态。
以上结论已被证明必成立，证明过程略。

本题是nim游戏的一个变种

很容易可以发现本题与原型nim游戏之间最大的区别在于，先手第一次只能从第k堆取，之后就可以从任意一堆取。
那么，我们考虑两种情况：

  1. 所有堆的石子异或和为0，那么不管先手怎么拿都是必败的;
  2. 所有堆的石子数异或和不为0，那么就要考虑先手从第k堆中能不能拿到一些石子，使得后手面对的是一个异或和为0的情况(也就是必败态)。否则先手就是必败的。

我们详细来说第二种情况，什么情况下能拿到一些石子使得剩下的石子异或和为0呢？显然暴力的话时间会比较长。
假设有n堆石子，石子个数分别是a1,a2...an，第k堆个数为ak
那么此时应该有，a1^a2^...^an!=0，设异或和为x，从第k堆拿走bk个石子，那么我们就需要令 (ak-bk)=ak^x,
这样就会出现x^x = 0。
那么如何实现ak-bk = ak^x呢，其实只需要判断一下ak>ak^x就可以了

代码如下：

#include<iostream>
#include<cmath>
using namespace std;
typedef long long LL;
int main() {
    int T;
    cin >> T;

    while (T--) {
        int n , k ;
        cin>>n>>k;//n堆石子，从第k堆开始取
        int ak = 0;
        int res = 0 ;
        int ans  ;//必败
        for(int i = 0 ;i<n;i++){
            int temp ;
            cin>>temp ;
            res^=temp ;//所有石子数的异或和
            
            if(i==k-1) ak = temp;
        }
        
        if(res==0) ans = 0; //如果开始时异或和为0 先手必败
        else{
            if((ak^res) < ak) ans = 1;
            else ans = 0 ;
        }
        
        if(ans == 1) puts("Yes");
        else puts("No") ;
    }
    return 0;
}