NIM 博弈 牛客小白月赛2 E-是是非非

题目链接

分析：一个裸的NIM博弈

对于一个Nim游戏的局面(a1,a2,...,an)，它是P-position(即当前局面先手必败)当且仅当a1^a2^...^an=0，其中^表示异或(xor)运算。

一个常识：异或自己两次，相当于没有异或，即异或的消去律，可用这种方式避免T

#include <bits/stdc++.h>
using namespace std;
const int inf=1<<30;
typedef long long ll;
const double pi=acos(-1);
const int mod=1e9+7;
const int maxn=1e5+1;
int a[maxn];
int main(){
    int n,q,x,y;scanf("%d%d",&n,&q);
    int sum=0;
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        sum^=a[i];
    }
    while(q--){
        scanf("%d%d",&x,&y);
        sum^=a[x];
        a[x]=y;
        sum^=a[x];
        if(sum) cout<<"Kan
";
        else cout<<"Li
";
    }
    return 0;
}