CF1451F 题解

liangbowen · 2023-07-06 23:15:25 · 题解

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)。