【题解】Codeforces 1942E - Farm Game

题目链接：https://codeforces.com/contest/1942/problem/E

题目大意：输入一个 \(l\) 和一个 \(n\) ，其中 \((1\leq l \leq 10^6, 2n <= l)\) ，表示有 \(l\) 个不同的空位（分别是 \([1, l]\) ）和 \(2n\) 头完全一样的牛。Alice 和 Bob 分别有 \(n\) 头牛，并且他们的牛是间隔排列的。每一次操作，玩家可以选择任意头自己的牛，然后选择一个方向（左或者右），然后被选择的牛统一移动到该方向上距离为1的一个空位上。注意牛不能超过边界也不能穿过另一个人的牛。求有多少种排列牛的方式使得 Alice 必胜。

题目分析：一般来说，这一类组合博弈的游戏先手都是有巨大优势的，因为如果能找到一个必败状态，先手可以有机会通过一次操作把当前状态转化成必败状态然后交给后手。一般来说，必败状态必定满足某一些特殊的恒等式，先手玩家破坏这个必败状态，而后手玩家必定能找到一个方法回到必败状态（一般来说是直接模仿对方操作，举例来说对于NIM游戏，先手必败的状态的异或和为0，先手从任意堆中取若干石子之后异或和从0变成非0，后手要构造一种方法让异或和重新变成0，要做的是证明后手总能如此构造）。对于这道题来说，可以只关心对应的两头牛之间的距离，因为如果不对应的两头牛之间的距离影响答案的话，如果是先手必败，并且先手任选了其中的一些牛往扩大对应的牛之间的距离的方向移动，那么后手只需要重复该操作使得牛之间的距离恢复成原貌即可；如果是先手必胜，那么先手不去移动两头牛之间的距离，只去做一些别的（容易证明只有对应牛之间的距离都为0才不能去做别的，这种情况由模仿策略可知先手必败，与假设先手必胜矛盾），然后把当前状态转移给后手就可以维持必胜。

所以只考虑对应的牛之间的距离，并且只能减少。

问题变成了：有n堆可能为空的石子，先手可以选其中任意堆各取1颗石子，如果所以堆都是空的则先手败。由于每个堆互相独立并且先后手交替操作并且每次只能减少至多1，很容易往奇偶性去想。首先全部都是空的时候是先手必败，然后如果有若干堆是1的其他都是0，那么先手把他们拿走就必胜了，故如果有1的堆就是必胜态，维持必胜的策略是不是让每一堆都变成偶数呢？简单想了想如果当前所有的堆都是偶数，那么进行操作之后至少有一堆是奇数，然后另一个人肯定可以操作回来让所有的堆维持回偶数，直到变成全部为0的必败态。所以全部为偶数容易知道是先手必败态。那么其他的一定是先手必胜态吗？只需要证明其他的状态（有至少一堆为奇数）进行一次操作就能回到必败态即可，结果是显然的。

所以问题就是对牛和空位进行排列，让对应的牛之间的距离至少有一个为奇数。

至少有一个为奇数这个不好求，容易想到可以用总方案数减去全部为偶数的方案数。

总方案数显然是隔板法，l个空位中选2n个放牛，然后从左到右依次分配给Alice和Bob，或者反过来先Bob后Alice，所以要乘以2。

距离全部为偶数的解法，先把问题抽象成x个球和y个盒子。一个显然的思路是用二进制分解，由于每个数的二进制分解是完全固定且一一对应的，枚举某个二进制位（至少表示2），那么每个盒子要么有这个二进制位要么没有，完全对应。这个方法也可以处理诸如异或和为0（每一个二进制位是互相独立的所以只需要每次都选偶数个1，并且每个盒子至多拥有1个1即可），剩下枚举到表示1的二进制位（第0位）的时候，不能放在盒子里，只能放在盒子之间和最两端的总共y+1个空位上，由于空位可以重复放球所以这时候要用隔板法。但可惜过不了这一道题，这道题l是1e6，如果是2e5的话应该是可以通过的。那有没有办法直接保障所有盒子的球都是偶数呢？其实就是把2个球打包成一组，然后用隔板法把他们放在不同的盒子里，记得把没用完的继续放在盒子外面。