本文共 1925 字，大约阅读时间需要 6 分钟。
（Nim博弈）
题目意思是说有n堆石子，Alice只能从中选出连续的几堆来玩,现在问Alice想要获胜有多少种方法（即有多少种选择方式）。
方法是这样的，由于Nim博弈必胜的条件是所有数的抑或值不为0，证明见 ，所以答案就转化为原序列有多少个区间的亦或值为0，用n*(n+1) / 2 减去这个值就可以了。
而求有多少个区间的亦或值为0，实际上就是求对于亦或值的前缀nim[i]，满足nim[i] == nim[j] 的对数，这时只要对nim数组排序就可以算了
详见代码：
1 #include 2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 #include 9 #include 10 #include 11 #include 12 #include 13 #include 14 using namespace std;15 #define INF 0x3f3f3f3f16 #define inf (-((LL)1<<40))17 #define lson k<<1, L, mid18 #define rson k<<1|1, mid+1, R19 #define mem0(a) memset(a,0,sizeof(a))20 #define mem1(a) memset(a,-1,sizeof(a))21 #define mem(a, b) memset(a, b, sizeof(a))22 #define FIN freopen("in.txt", "r", stdin)23 #define FOUT freopen("out.txt", "w", stdout)24 #define rep(i, a, b) for(int i = a; i <= b; i ++)25 26 template T CMP_MIN(T a, T b) { return a < b; }27 template T CMP_MAX(T a, T b) { return a > b; }28 template T MAX(T a, T b) { return a > b ? a : b; }29 template T MIN(T a, T b) { return a < b ? a : b; }30 template T GCD(T a, T b) { return b ? GCD(b, a%b) : a; }31 template T LCM(T a, T b) { return a / GCD(a,b) * b; }32 33 //typedef __int64 LL;34 typedef long long LL;35 const int MAXN = 110000;36 const int MAXM = 20010;37 const double eps = 1e-4;38 //LL MOD = 987654321;39 40 int n, a[MAXN], x, s, w, T;41 42 int main()43 {44 while(~scanf("%d", &T)) while(T--) {45 cin >> n >> s >> w;46 LL ans = (LL)n * (n + 1) / 2;47 int g = s;48 rep (i, 1, n) {49 x = g;50 if( x == 0 ) { x = g = w; }51 if( g%2 == 0 ) { g = (g/2); }52 else { g = (g/2) ^ w; }53 a[i] = a[i - 1] ^ x;54 if(a[i] == 0) ans --;55 }56 sort(a + 1, a + n + 1);57 int num = 1;58 rep (i, 2, n) {59 if(a[i] == a[i - 1]) {60 ans -= num;61 num++;62 }63 else num = 1;64 }65 cout << ans << endl;66 }67 return 0;68 }
转载于:https://www.cnblogs.com/gj-Acit/p/4492722.html