题目大意：
有两个人，
n
n
n堆石子。每个人轮流取，每次可以取1~
x
x
x个，最后没得取的人输，两人都采取最优策略。
问对于
x
x
x从1到
i
(
i
≤
n
)
i(i\leq n)
i(i≤n)，问谁会赢。
思路：
首先想出
S
G
SG
SG函数，取石子这样的一般都是先算出
a
i
m
o
d
(
x
+
1
)
a_i~ mod~(x + 1)
ai mod (x+1)，然后异或起来等不等于0。
考虑另一种算答案的方法。
a
i
m
o
d
y
=
a
i
−
⌊
a
i
y
⌋
a_i~mod~y=a_i-⌊\frac{a_i}{y}⌋
ai mod y=ai−⌊yai⌋，然后枚举
y
(
y
≤
n
+
1
)
y(y\leq n+1)
y(y≤n+1)，再枚举
k
(
k
≤
⌊
n
y
⌋
)
k(k\leq ⌊\frac{n}{y}⌋)
k(k≤⌊yn⌋)，然后求出
a
i
a_i
ai在
k
∗
y
k*y
k∗y到
(
k
+
1
)
∗
y
−
1
(k+1)*y-1
(k+1)∗y−1之间减去
k
∗
y
k*y
k∗y的异或和。
然后考虑DP，设
f
i
,
j
f_{i,j}
fi,j表示所有大于等于
i
i
i的数减
i
i
i之后第
j
j
j位的异或和，转移就是：
f
i
,
j
=
o
(
i
+
2
j
,
i
+
2
j
+
1
−
1
)
x
o
r
f
i
+
2
j
+
1
,
j
f_{i,j}=o(i +2^j,i+2^{j+1}-1)~xor ~f_{i+2^{j+1},j}
fi,j=o(i+2j,i+2j+1−1) xor fi+2j+1,j
其中
o
(
l
,
r
)
o(l,r)
o(l,r)代表
a
i
∈
[
l
,
r
]
a_i∈[l,r]
ai∈[l,r]的
a
i
a_i
ai个数的奇偶性。
计算答案，用
l
l
l表示
k
∗
y
k*y
k∗y，用
r
r
r表式
(
k
+
1
)
∗
y
−
1
(k+1)*y-1
(k+1)∗y−1，那么异或的东西可以表式为
f
l
,
j
x
o
r
f
l
+
2
j
+
1
∗
(
z
+
1
)
,
j
x
o
r
o
(
m
a
x
(
r
,
l
+
2
j
+
1
∗
(
z
+
1
)
−
1
)
,
l
+
2
j
+
1
∗
(
z
+
1
)
−
1
)
f_{l,j}~xor~f_{l+2^{j+1}*(z+1),j}~xor~o(max(r,l+2^{j+1}*(z+1)-1),l+2^{j+1}*(z+1)-1)
fl,j xor fl+2j+1∗(z+1),j xor o(max(r,l+2j+1∗(z+1)−1),l+2j+1∗(z+1)−1)
其中
z
z
z是满足
z
≤
r
−
l
2
j
+
1
z\leq \frac{r-l}{2^{j+1}}
z≤2j+1r−l的最大正整数。
然后每次异或起来判断是否为0。
c
o
d
e
code
code
#include<iostream>
#include<cstdio>
using namespace std;
const int MAXN = 1 << 24;
int n;
int a[MAXN], num[MAXN];
int f[MAXN][25], ans[MAXN];
int o(int l, int r) {
if(r < 1) return 0;
if(l > n) return 0;
if(r > n) r = n;
if(l < 1) l = 1;
return num[r] ^ num[l - 1];
}
int main() {
// freopen("stone.in", "r", stdin);
// freopen("stone.out", "w", stdout);
scanf("%d", &n);
for(int i = 1; i <= n; i ++) {
scanf("%d", &a[i]);
num[a[i]] ^= 1;
}
for(int i = 1; i <= n; i ++) num[i] ^= num[i - 1];
for(int i = n; i >= 0; i --)
for(int j = 0; (1 << j) <= n + 1; j ++)
f[i][j] = o(i + (1 << j), i + (1 << j + 1) - 1) ^ f[i + (1 << j + 1)][j];
for(int y = 2; y <= n + 1; y ++) {
for(int j = 0; (1 << j) <= y; j ++) {
ans[y] = 0;
for(int k = 0; k <= n / y; k ++) {
int l = y * k, r = (k + 1) * y - 1;
int z = (r - l) / (1 << j + 1);
ans[y] ^= f[l][j] ^ f[l + (1 << j + 1) * (z + 1)][j] ^ o(max(r, l + (1 << j + 1) * z + (1 << j) - 1) + 1, l + (1 << j + 1) * (z + 1) - 1);
}
if(ans[y]) break;
}
}
for(int i = 2; i <= n + 1; i ++) if(ans[i] == 0) printf("Bob "); else printf("Alice ");
return 0;
}
