张家港百度网站推广,国外展览展示设计网站,手机网站不支持下载的视频怎么下载,网站建设创业书Nim or not Nim?
结论 Mult−NimMult-NimMult−Nim博弈#xff1a;有nnn堆石子#xff0c;两个人可以从任意一堆石子中拿任意多个石子(不能不拿)或把一堆数量不少于22石子分为两堆不为空的石子#xff0c;没法拿的人失败#xff0c;问谁会胜利。
结论SG(x)x−1[xmod40],…Nim or not Nim?
结论
Mult−NimMult-NimMult−Nim博弈有nnn堆石子两个人可以从任意一堆石子中拿任意多个石子(不能不拿)或把一堆数量不少于22石子分为两堆不为空的石子没法拿的人失败问谁会胜利。
结论SG(x)x−1[xmod40],x1[xmod43],x[others]SG(x) x - 1[x \bmod 4 0], x 1[x \bmod 4 3], x[others]SG(x)x−1[xmod40],x1[xmod43],x[others]
代码
/*Author : lifehappy
*/
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include bits/stdc.h#define mp make_pair
#define pb push_back
#define endl \n
#define mid (l r 1)
#define lson rt 1, l, mid
#define rson rt 1 | 1, mid 1, r
#define ls rt 1
#define rs rt 1 | 1using namespace std;typedef long long ll;
typedef unsigned long long ull;
typedef pairint, int pii;const double pi acos(-1.0);
const double eps 1e-7;
const int inf 0x3f3f3f3f;inline ll read() {ll f 1, x 0;char c getchar();while(c 0 || c 9) {if(c -) f -1;c getchar();}while(c 0 c 9) {x (x 1) (x 3) (c ^ 48);c getchar();}return f * x;
}int sg(int x) {if(x % 4 0) return x - 1;else if(x % 4 3) return x 1;return x;
}int main() {// freopen(in.txt, r, stdin);// freopen(out.txt, w, stdout);// ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);int T read();while(T--) {int n read(), ans 0;for(int i 1; i n; i) {ans ^ sg(read());}puts(ans ? Alice : Bob);}return 0;
}
