CF1451F 题解

problem & blog。

这题原本的题解满是废话，让我写一篇（

这边直接给结论了。令 \(val_p = \oplus_{x+y=p}\ a_{x,y}\)，设 \(S=\Big[\normalsize \forall val_i=0\Big]\)，当 \(S=\text{true}\) 时，后手必胜；否则先手必胜。

证明也是典中典。证两个条件即可。

• 证明 \(\forall S \Rightarrow \neg S\)：起点那里强制操作，并且你无法从 \((x,y)\to(s,t) (s<x \vee t<y)\)，所以起点那一斜行的 \(\oplus a_{x,y}\) 是不可能维持 \(0\) 了。
• 证明 \(\exists \neg S \Rightarrow S\)：找到最小的 \(i\) 满足 \(val_i\ne 0\)，它对应的斜行是 \(i\)。取这一斜行二进制最高位所在的那个 \(a_{x,y}\) 作为起点，终点取右下角。
  • 对于起点：\(a_{x,y}\gets(a_{x,y}\oplus val_i)\) 显然可以使 \(val_{i}'=0\)。由于 \(a_{x,y}\) 最高位在手，必定有 \(a_{x,y}\ge(a_{x,y}\oplus val_i)\)。
  • 对于路径上的其他斜行：由于可以加，直接变成 \((a_{i,j}\oplus val_{i+j})\) 当然有正确性。

注意到先手必输态（全为 \(0\)）对应 \(S=\text{true}\)，也就有了一开始的结论。综上我们完成证明。

代码，时间复杂度 \(O(Tnm)\)。