CheckerExpansion

作者：高睿泉 汪乐平

关键字：数学

题目大意

A和B两人在方格上轮流放检验器。第一次操作A在$(0,0)$放上一个检验器。之后每次操作中，对于空方格$(x,y)$，满足下列某一条件时在$(x,y)$放上一枚检验器：

1.$(x-2,y)$上有一个对方的检验器，且$(x-1,y-1)$上没有检验器

2.$(x-1,y-1)$上有一个对方的检验器，且$(x-2,y)$上没有检验器

现在双方轮流一共操作$t$次，问左下角为$(x_{0},y_{0})$,右上角为$(x_{0}+w-1,y_{0}+h-1)$的矩形中的每个方格的状态(空，A的检验器或B的检验器)。

数据范围

$0\leq t,x_{0},y_{0}\leq 10^{12}$

$0 \leq w,h\leq 50$

算法一

容易发现对于方格$(x,y)$，如果这个方格上有检验器则$x+y$可以被$2$整除，其中如果上面放着A的检验器则$x+y$为4倍数的，如果上面放着B的检验器则$x+y$不为$4$倍数；因为只有对方上一次刚放的检验器会影响这一次放置的位置，则第$i$次放置的每个位置$x+y$都为第$i-1$次放置的每个位置的$x+y$加$2$，所以第i次操作放置位置的$x+y$为$2(i-1)$。

设$(x,y)$上有无检验器情况$a_{x,y}$，若有检验器为$1$，没有为$0$。所以可以推出：

$a_{x,y}=a_{x-2,y} \; xor \; a_{x-1,y-1}=(a_{x-2,y}+a_{x-1,y-1}) \;mod\; 2$

取$b_{\frac{x+y}{2},y}=a_{x,y}$,则$b_{0,0}=1$,$b_{\frac{x+y}{2},y}=(b_{\frac{x+y}{2}-1,y}+b_{\frac{x+y}{2}-1,y-1}) \; mod \; 2$

发现$b_{\frac{x+y}{2},y}$相当于模$2$意义下的杨辉三角形，枚举每个矩形内$x+y\leq 2(t-1)$的格子，由于$\binom{n}{m}\equiv1(mod\;2)$当且仅当$n\&m=m$（按位与），所以可以$O(1)$检验是否存在检验器，再由$x+y$的值决定每个格子上是谁放的检验器。

时间复杂度$O(wh)$