苏州做网站哪家专业,wordpress换模板,旅游类作业网站,泰安房产管理局官网解析
我的做法#xff1a;打表#xff0c;哦…过了。 打表观察的结论#xff1a;只要不全是1#xff0c;答案和正常Nim游戏相同#xff0c;全是1简单讨论奇偶性即可。 证明#xff1a; 全是1的正确性显然#xff0c;现在考虑不全是1的时候为什么直接看异或和就行。 关键…解析
我的做法打表哦…过了。 打表观察的结论只要不全是1答案和正常Nim游戏相同全是1简单讨论奇偶性即可。 证明 全是1的正确性显然现在考虑不全是1的时候为什么直接看异或和就行。 关键性质当仅有一堆大于1的时候必胜。 因为我可以随意的调控接下来权值为1的个数的奇偶性。
同时只要一开始不全是1无论如何拿这个状态都是必然要经历的。 因此我们可以把它作为一个获胜的终止状态。 此时显然异或和不为0。 那么就和传统Nim的证明一样了胜方只需要一直保证到自己走时异或和不为0即可。
bonus
很有启发性的一点是由于Nim游戏和SG函数本质的相通性这个结论可以推广到所有类似的Anti-SG游戏中。Anti-SG游戏的定义决策集合为空的状态视为胜利状态。
把SG函数当成石子数即可。 这个玩意好像叫 Sprague Grundy - Jia Zhihao 定理
代码
附打表程序
#includebits/stdc.h
using namespace std;
#define ll long long
#define ull unsigned long long
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define ok debug(OK\n)
using namespace std;const int N2e5100;
const int mod1e99;
inline ll read(){ll x(0),f(1);char cgetchar();while(!isdigit(c)) {if(c-)f-1;cgetchar();}while(isdigit(c)) {x(x1)(x3)c-0;cgetchar();}return x*f;
}inline ll ksm(ll x,ll k){ll res(1);while(k){if(k1) resres*x%mod;xx*x%mod;k1;}return res;
}
int n,m;
int a[20];
int bas31;
inline ull Hash(int *a,int n){ull res0;for(int i1;in;i) resres*basa[i];return res;
}
mapull,intmp;
bool cmp(int x,int y){return xy;}
int find(const int *x,int n){int a[20];memcpy(a,x,sizeof(int)*(n1));sort(a1,a1n,cmp);while(!a[n]n) --n;if(n0) return 1;ull hHash(a,n);if(mp.count(h)) return mp[h];int res0;int b[20];memcpy(b,a,sizeof(int)*(n1));for(int i1;in;i){for(int j0;ja[i];j){b[i]j;res|find(b,n)0;b[i]a[i];}}return mp[h]res;
}
int op;
int now[20];
inline int calc(int *a,int n){int res(0);for(int i1;in;i) res^a[i];return res;
}
void dfs(int k){if(km){int opfind(now,m);if(op0calc(now,m)){for(int i1;im;i) printf(%d ,now[i]);printf((%d) op%d,calc(now,m),op);puts();}if(op1calc(now,m)0){for(int i1;im;i) printf(%d ,now[i]);printf((%d) op%d,calc(now,m),op);puts();}return;}for(int inow[k-1];in;i){now[k]i;dfs(k1);}return;
}
void work(){nread();int res(0),flag1;for(int i1;in;i){int xread();res^x;flag(x1);}if((res0)^flag) puts(Brother);else puts(John);
}signed main(){#ifndef ONLINE_JUDGEfreopen(a.in,r,stdin);freopen(a.out,w,stdout);#endif//nread();int limread();//now[0]1;//for(m1;mlim;m) dfs(1);//return 0;int Tread();while(T--) work();return 0;
}
//288 125 189 111 229
