Solution. Codeforces Round #832

C. Swap Game

为了让游戏过程更直观，我们将游戏过程修改一下：$a_{1\dots n}$ 中有且仅有一个数 $a_t$ 被锁定，初始为 $a_1$，两人轮流从未被锁定的数中选择一个 $a_i$，如果 $a_i=0$ 则获胜，否则 $a_t\leftarrow a_t-1$ 且被锁定的数改为 $a_i$。

将 $a_{2\dots n}$ 从小到大排序，我们的结论是，先手必胜当且仅当 $a_2\le\min\{a_1-1,a_3\}$。

接下来考虑证明。

我们先来证 $a_2\le\min\{a_1-1,a_3\}$ 时先手有必胜策略。

先手只要每次都选择 $a_2$ 即可，$a_2$ 在后手操作时被锁定，所以先手一定可以选到 $a_2$，同时不难发现 $a_2$ 永远不大于后手操作集合中的任何一个数，那么先能选到 $0$ 的一定是先手。

反之，先手必败，我们可以类似的说明后手有必胜策略，注意先手不选 $a_2$ 只会让后手更优。

D. Yet Another Problem

我们只能对长度为奇数的段进行操作，不难发现一次操作不会改变整个区间的异或和，所以整个区间异或和不为 $0$ 的话直接判定无解。

接下来，区间长为奇数是 trivial 的，直接对整个区间操作即可。

如果区间长为偶数，我断言有解当且仅当区间可以被划分为两个长度为奇数、异或和为 $0$ 的子区间。

充分性是显然的，接下来证明必要性。

如果我们把所有「长度为奇数的前缀的异或和」记作集合 $S$。

最终区间中所有数都为 $0$，那么一定存在一次操作，包含区间开头且操作的子区间异或和为 $0$，即 $S$ 中应当有 $0$。

考虑一次操作对 $S$ 的影响。

A. 如果一个前缀包含操作区间或与操作区间不交，则这次操作对该前缀异或和没有影响。
除去 A，如果一个前缀与操作区间相交，我们可以将前缀缩短或延长偶数长度得到一个 A 前缀，且异或和不变，于是新得到的异或和一定本来就在 $S$ 中。

所以，$S$ 中不会出现新元素。我们知道 $S$ 最开始没有 $0$，则 $S$ 中永远不会有 $0$，这样就说明了此时无解。

E. List Generation

国人的数学科技还是太强了。我不配 chinese boy。

这题可以按照官方题解的方法转化成网格图上的问题，相当于找一个点集使得存在只向右或向下的路径能够经过所有点，这样其实很难计数，考虑钦定相邻两点间的路径是先向下走再向右走，这样每个点集就会唯一对应一条路径。

一条路径可以由若干向右变为向下的拐点确定，这些拐点是必选的，其余路径上的点都可选可不选，这样即可对点集计数。

先枚举拐点，然后其余点任选。
$$
\sum_{i=0}^{\min\{n,m\}}\binom ni\binom mi{\color{yellow}\sum_{j=0}^{n+m-1-i}(i+j+2)\binom{n+m-1-i}{j}}
$$
对后面一部分展开，记 $k=n+m-1-i$，实际上 $k$ 表示的是路径上除 $(0,0),(n+1,m+1)$ 和拐点之外的点数，即我们可选的点数：
$$
(i+2)\sum_{j=0}^{k}\binom kj+\sum_{j=0}^k j\binom kj
$$
这是两个组合恒等式。

考虑 $f(x)=(x+1)^k$，取 $x=1$ 二项式展开得 $\sum_{j=0}^k\binom kj=2^k$。

求导，$f'(x)=k(x+1)^{k-1}=\sum_{j=0}^k\binom kj(x^j)'=\sum_{j=0}^kj\binom kjx^{j-1}$，取 $x=1$ 有 $\sum_{j=0}^kj\binom kj=k2^{k-1}$。

还可以求二阶导得到 $\sum_{j=0}^k j^2\binom kj$ 的值。

最后，原式化为：
$$
\sum_{i=0}^{\min\{n,m\}}\binom ni\binom mi\left((i+2)2^k+k2^{k-1}\right)
$$
实现很简单。

本作品采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。