题目链接
https://codeforces.com/contest/1942/problem/E
题目大意
小 N 和小 J 各有 \(n\) 头奶牛，小 N 的奶牛位置为 \(a_1, a_2, \cdots, a_n\)，小 J 的奶牛位置为 \(b_1, b_2, \cdots, b_n\)。其中小 N 和小 J 的奶牛交替出现，且位置在 \(1\) 与 \(l\) 之间，即满足 \(0 < a_1 < b_1 < a_2 < b_2 < \cdots < a_n < b_n < l + 1\) 或 \(0 < b_1 < a_1 < b_2 < a_2 < \cdots < b_n < a_n < l + 1\)。
现在小 J 和小 N 轮流进行以下操作，小 J 先手：
- 当前操作的人任意选中自己的 \(k(1 \le k \le n)\) 头奶牛，并且让这些奶牛一起向左或向右移动一格。移动后，位置不能与另外一个人的奶牛重合，也不能超出边界（即位置不能小于 \(1\) 也不能大于 \(n\)）。
- 若无法进行上述操作，当前操作的人判负。
问有多少种合法的序列组合 \((a, b)\)，使得小 J 必胜（两人均足够聪明）。
数据范围
多组测试数据，保证
- \(2 \le l \le 10^6 , \sum l \le 10^{6}\)
- \(1 \le n \le \left\lfloor\frac{l}{2}\right\rfloor\)
解题思路
十分有意思的小清新博弈和组合数学题。
Step 1
这题要求我们对先手必胜态进行计数，要计数我们必须要先搞清楚先手必胜态长什么样子。
先考虑比较简单的情况，如果 \(n = 1\)，此时发现如果小 J 的奶牛与小 N 的奶牛贴贴，那么小 J 必败；否则，小 J 和小 N 要尽量避免自己的奶牛被对方贴贴。
我们又发现，操作的人把自己的奶牛向使相对距离变远的方向移动是没有意义的，因为下一个操作的人模仿相同的动作总能把相对距离变回原来的状态。
所以 \(n = 1\) 时小 J 是否必胜只与两头奶牛的相对距离的奇偶性有关。
Step 2
我们 \(n\) 为任意正整数时上述结论仍然成立，即
- 小 J 和小 N 的奶牛两两贴贴时先手必败。
- 操作的人把自己的奶牛向使相对距离变远的方向移动是没有意义的。
所以两两配对的奶牛之间的距离只会一直缩小至 \(0\)。
问题可以转化为给定 \(n\) 堆石子，每次选取任意个（不能不选）剩余石子个数大于 \(0\) 的堆，从这些堆的每一堆中都取走 \(1\) 个石子，问先手是否必胜。
Step 3
分析上一步转化的问题，发现先手必败的充要条件是所有堆的石子数均为偶数。
证明：如果石子堆中有奇数的堆，先手可以通过一次操作使得所有的堆中石子数均为偶数；否则，先手操作后至少会有一个奇数的堆。又因为最终不能操作的状态为全 \(0\)，都是偶数。所以如果有奇数的堆，先手每次操作后都能控制所有堆中的石子都是偶数，以此把后手逼迫到全 \(0\)。
Step 4
经过上述分析，问题变为统计从长为 \(l\) 的段中截取出若干个不相交的长度不全为偶数的子段的方案数。
不妨先统计总方案，再减去长度全为偶数的方案。
每一部分的方案使用乘法原理和隔板法计算即可。
最后答案别忘记乘 \(2\)，因为可以把小 J 的奶牛放在前面，也可以把小 N 的奶牛放在前面。