ARC089B 题解

problem & blog。

给一个比较暴躁的做法。

若要求 \((x,y)\) 的颜色为 White，等价于要求 \((x+k,y)\) 的颜色为 Black；要求 \((x,y)\) 的颜色为 Black，等价于要求 \((x\bmod 2k, y\bmod 2k)\) 为 Black。

于是将全部点以黑点的形式塞到左上角 \(2k\times2k\) 矩阵里。枚举黑白的「分界线」，挨个判断每个点所在格是否为 Black，\(O(nk^2)\)，寄。

优化很简单啊，\(2k\times2k\) 很小捏，二维前缀和直接做即可。

代码，时间复杂度 \(O(n+k^2)\)。