给 n n n个非负数，两个人轮流玩游戏，如果玩家擦出一个数后，剩下的数字异或为0，则该玩家输，也就是说当前玩家黑板上的数字异或为0，则该玩家赢，比如1，2，3，先手赢。
1 ≤ n ≤ 1 0 6 1 leq n leq 10^6 1≤n≤106
题解注意到：一个玩家面临的初始数字个数是奇数（偶数）个的话，那么一直到游戏结束，他面临的数字个数仍然是奇数（偶数）个。 故从奇偶性角度考虑。假设先手面临的数字是偶数个，记
a
1
⊕
a
2
⊕
⋯
⊕
a
n
=
S
a_1 oplus a_2 oplus cdots oplus a_n = S
a1⊕a2⊕⋯⊕an=S；如果
S
=
0
S = 0
S=0，先手赢；如果
S
≠
0
S neq 0
S=0，考虑先手在什么情况下必输？只有当任意擦除一个数后，剩下的数字异或为0，即擦除任意一个数
a
i
a_i
ai，都有：
a
1
⊕
a
2
⊕
⋯
⊕
a
i
−
1
⊕
a
i
+
1
⋯
⊕
a
n
=
0
a_1 oplus a_2 oplus cdots oplus a_{i - 1} oplus a_{i + 1} cdots oplus a_n = 0
a1⊕a2⊕⋯⊕ai−1⊕ai+1⋯⊕an=0用
S
S
S表示：
S
⊕
a
i
=
0
S oplus a_i = 0
S⊕ai=0。进一步有：
( S ⊕ a 1 ) ⊕ ( S ⊕ a 2 ) ⊕ ( S ⊕ a 3 ) ⋯ ⊕ ( S ⊕ a n ) = 0 (1) (S oplus a_1) oplus (S oplus a_2) oplus (S oplus a_3) cdots oplus (S oplus a_n) = 0 tag{1} (S⊕a1)⊕(S⊕a2)⊕(S⊕a3)⋯⊕(S⊕an)=0(1)而
( S ⊕ a 1 ) ⊕ ( S ⊕ a 2 ) ⊕ ( S ⊕ a 3 ) ⋯ ⊕ ( S ⊕ a n ) = ( S ⊕ S ⊕ ⋯ ⊕ S ) ⊕ ( a 1 ⊕ a 2 ⊕ ⋯ ⊕ a n ) = S (2) (S oplus a_1) oplus (S oplus a_2) oplus (S oplus a_3) cdots oplus (S oplus a_n) = (S oplus S oplus cdots oplus S) oplus (a_1 oplus a_2 oplus cdots oplus a_n) = S tag{2} (S⊕a1)⊕(S⊕a2)⊕(S⊕a3)⋯⊕(S⊕an)=(S⊕S⊕⋯⊕S)⊕(a1⊕a2⊕⋯⊕an)=S(2) 结合(1)，(2)，有：
S = 0 S = 0 S=0 这与 S ≠ 0 S neq 0 S=0矛盾，故任意擦除一个数后，剩下的数字异或为0不成立，即先手面临的数字个数是偶数个时，总能找到一个数，擦除后其异或不为0。综上所述：
- a 1 ⊕ a 2 ⊕ ⋯ ⊕ a n = 0 a_1 oplus a_2 oplus cdots oplus a_n = 0 a1⊕a2⊕⋯⊕an=0，先手必胜
- n n n 为偶数，先手必胜
赛车
一辆车初始位置为 0 0 0，初始速度为 1 1 1，有两种指令：
- 指令 A A A， p o s = p o s + s p e e d pos = pos + speed pos=pos+speed， s p e e d = s p e e d ∗ 2 speed = speed * 2 speed=speed∗2
- 指令 R R R， p o s = p o s pos = pos pos=pos， s p e e d = ( s p e e d > 0 ? − 1 : 1 ) speed = (speed > 0 quad ? -1 : 1) speed=(speed>0?−1:1)
给出目标地址 t a r g e t target target，问到达该位置的最短指令长度？
1 ≤ t a r g e t ≤ 1 0 5 1 leq target leq 10^5 1≤target≤105
题解如果
t
a
r
g
e
t
=
2
k
−
1
target = 2^k - 1
target=2k−1，则最短指令长度为
k
k
k；如果不等则必然存在一个
k
k
k使得：
2
k
−
1
−
1
<
t
a
r
g
e
t
<
2
k
−
1
2 ^ {k - 1} - 1 < target < 2^k - 1
2k−1−1 第二种情况需要枚举后退时使用了几个
A
A
A指令。 对于
n
n
n个点的简单连通无向图，问走完所有点的最短路径长度？
1
≤
n
≤
12
1 leq n leq 12
1≤n≤12 有个很直观的思路，计算每一个排列对应最短路径，然后取最小值，复杂度
O
(
n
!
)
O(n!)
O(n!)。还有个想法，枚举已经走过的点的集合，假设令
d
p
[
S
]
dp[S]
dp[S]表示走完
S
S
S中所有点对应的最短路径长度，现在新假如一个点
v
v
v ，怎么更新
d
p
dp
dp呢？很容易观察到，还缺少了信息，即
d
p
[
S
]
dp[S]
dp[S]对应了最小的走法，但该走法的信息我们一点都不知道。故增加一个维度，令
d
p
[
u
]
[
S
]
dp[u][S]
dp[u][S]表示走完所有点且最后停在点
u
u
u 的最小路径长度，有：
为什么可以复用之前的
d
p
[
]
dp[]
dp[]呢？因为每次使用
R
R
R指令后相当于初始状态
访问所有节点的最短路径
d
p
[
v
]
[
S
∣
v
]
=
m
i
n
u
∈
S
(
d
p
[
u
]
[
S
]
+
d
i
s
t
a
n
c
e
[
u
]
[
v
]
)
dp[v][S | v] = min_{u in S}(dp[u][S] + distance[u][v])
dp[v][S∣v]=minu∈S(dp[u][S]+distance[u][v])
复杂度
O
(
n
2
2
n
)
O(n^22^n)
O(n22n)
