Solution：AT_utpc2022_c Nim is Time-consuming

· · 题解

三年前钦定不可做的 idea 现在发现是四年前的原/xk

以下令 V=9 为最小的满足 2^V\geq M 的整数。

翻译一下题目条件，就是赢的人想让回合数最小，输的想让回合数最大。首先当然要会算单个局面的回合数，但是这真的能算吗？？

令 S=\sum_i A_i，显然 T\leq S。观察样例解释，立刻猜测总回合数 T=S。

Key Observation: 若初始局面先手必输，那么总回合数 T=S。

证明非常简单：先手每次从 \operatorname{lowbit}(A_i) 最小的堆里取一个石子。不难发现后手此时唯一的选择就是选另一堆 \operatorname{lowbit} 和 A_i 相同的堆再取一个石子，这就使回合数达到了 S。

先手必胜时的操作方案也是显然的，显然先手会尝试在第一回合取尽可能多的石子。

令 X 为所有 A_i 的异或和。若 X\neq 0 先手第一次取的石子数为 f(A)=\max_i\{A_i-(A_i\oplus X)\}，则 T=S-f(A)+1。

由于 f(A)=1 并不影响总回合数，接下来我们只关心先手必胜的局面。我们希望对于 1\leq i\leq M 能算出 f(A)=i 的方案数，也就是要算 f(A)\leq i 的方案数。f(A)\leq i 也就意味着对于每一堆石子都有 A_j-(A_j\oplus X)\leq i，那么我们枚举 X，算一下哪些 A_j 可以选，接下来直接异或卷积快速幂即可，这样直接暴力就得到了一个 \Omicron(16^V\log N) 的做法，显然是过不去的。

考虑优化。首先异或卷积快速幂可以 FWT 之后把点值 N 次方再 IFWT 回去。我们先枚举 X，再从小到大枚举 i，在枚举 i 的同时加入可选的 A_j，加入 A_j 时直接按照 xor-FWT 的定义更新点值，一次更新点值是线性的。接下来因为我们只需要求 FWT 后一个位置的值，考虑直接按照定义计算，显然每个 FWT 点值都在 [-M,M] 之间，所以预处理一下 i^N 这一部分也可以线性。

综上我们得到了一个 \Omicron(8^V) 的做法。Code.

注意这是个远古题所以记得结尾换行。