CF 494E Sharti
题意:一个\(n \times n\)的棋盘,共有m个矩形中的格子为白色。两个人需要博弈,每次操作选择一个边长不超过k的正方形并翻转颜色,每次翻转需要正方形的右下角为白色,轮流操作,不能操作者输。
题解:
这个题显然是满足翻硬币游戏的定理,只是将一维改成了二维。
\(sg_{i,j}= \min\{ lowbit(i),lowbit(j),maxbit(k) \}\)。
lowbit(x)是把x看成2进制数的最低位,maxbit(x)时最高位。
接下来证明这个结论。
接下来给出几个引理。
定义
\(pre_x = \bigoplus_{i=1}^{x} \text{lowbit(i)}\)
\(f(l,r)= \bigoplus_{i=l}^{r} \text{lowbit(i)}\)
引理1: \(\forall k \geq 1\),\(pre_{2^k} = 2^{k-1}\)
证明:考虑各位的贡献易证。
引理2: \(\forall k \geq 1\),令集合\(S_k=\{ pre_x | x\in [0,2^k-1] \}\) ,可以证明\(S_k=[0,2^k-1]\)
证明:归纳,k=1时显然成立,当k>1时,$$S_k={ pre_x | x\in [0,2^{k-1}-1] } \bigcup \
{ (2^{k-1} + 2^{k-2}) pre_x | x\in [0,2^{k-1}-1] }
\
=[0,2^{k}-1]$$
引理3:\(\forall x \neq y,pre_x \neq pre_y\)
证明:由引理2可知。
先讨论\(k=n\)的情况,即翻转的正方形没有长度限制。
我们考虑归纳证明。
首先对于\(i \leq 1\)或\(j \leq 1\)的情况,显然\(sg_{i,j}=1\)。
接下来对于\(i \leq x , j \leq y , (i,j) \neq (a,b)\)的情况都满足结论,我们需要证明\(sg_{a,b}=\min\{lowbit(a),lowbit(b)\}\)
不妨设\(lowbit(a) \leq lowbit(b)\),\(k=lowbit(a)\)
对于小于2^k的数必定都在S中,因为显然对于\(i < 2^k, lowbit(a-i)=lowbit(b-i)=lowbit(i)\),
于是对于\(x < 2^k,pre_x \in S\)。
只需证明\(2^k \notin S\)
我们要找\(2^k\),不妨放弱一点条件,我们只要找值在\([2^k,2^{k+1}-1]\)的即可。
令\(t=a-2^k\),\(k'=lowbit(t)\)
如果\(a-2^k\)或\(b-2^k\)为0,那么一定找不到。
\(lowbit(a)<lowbit(b)\)时,在矩阵的\((a-2^k,b)\)这个位置有一个 \(2^{k'}\)
\(lowbit(a)=lowbit(b)\)时,在矩阵的\((a-2^k,b-2^k)\)这个位置有一个 \(2^{k'}\)
并且显然,以\(2^k\)为边长的正方形只有一个值为\(2^{k'}\)
把这个位置记为\((a',b')\),不管在哪,我们都得把这个\(2^{k'}\)给消掉
那么新的问题是要在(a',b')为右下角,找到一个值为\([2^{k'},2^{k'+1}-1]\)的正方形。
(为什么是正方形呢,因为多出来的右边那一部分或者是上面一部分的值域一定在\([0,2^{k'}-1]\)),所以不会影响答案。
不难发现这个问题跟原来是一样的,而且做有限次之后a,b一定有一个会变为0,所以\(2^k \notin S\),\(\text{mex}\{S\}=2^k\)
这样我们就解决了\(k=n\)的问题,当\(k < n\)时,显然,k只会对\(\min\{lowbit(a),lowbit(b)\} > maxbit(k)\)的\(sg_{a,b}\)造成影响,
设\(t=2^{maxbit(k)}\)
不难发现,在边长k以内,以(a,b)为右下角和以(2t,2t)为右下角的值是一样的。
\(S=\{f(x,2t-1)|x\in[2t-k+1,2t]\}\)
又\(2t>x,lowbit(x)=lowbit(2t-x)\)
所以\(S= \{pre_x | x\in[0,k-1]\}\)
而\(pre_{2^{k+1}-1}=2^{k}\),由引理3可知\(2^k \notin S\)
既然知道了sg函数,我们直接扫描线+线段树,由于lowbit的种数很少,枚举每个lowbit进行维护即可。