P9417 [POI 2021/2022 R1] Druk 题解
:::::info[题目基本信息]
考察：贪心，哈希 Hashing，Ad-hoc（省选/NOI-）。
题目简介：
给定一个
数据范围：
-
1\le n,m\le 1000 ::::: 容易发现所有可能的木板长度
l 必须满足l\mid n 或l\mid m 。
为方便和符合个人习惯本命题证明内使用0 开始的编号，本命题证明后实现使用1 开始的编号。
:::::success[证明] 考虑将格子(i,j) 染色成(i+j)\bmod l ，那么这些木板每一个都覆盖l 个不同的颜色，那么每种颜色都应该有\dfrac{nm}{l} 种，那么l\nmid nm 时显然不合法。
设现在我们要求颜色c 的格子数量（c\in[0,l) ），我们容易列出式子：F(c)=\sum_{i=0}^{n-1}\sum_{j=0}^{m-1}[i+j\equiv c\pmod l] 容易发现这个函数在
[0,l) 内单调不升，那么我们现在只需证明：\sum_{i=0}^{n-1}\sum_{j=0}^{m-1}[i+j\equiv 0\pmod l]=\sum_{i=0}^{n-1}\sum_{j=0}^{m-1}[i+j\equiv l-1\pmod l]\\\Leftrightarrow\sum_{i=0}^{n-1}\lfloor\frac{m-i\bmod l}{l}\rfloor+1=\sum_{i=0}^{n-1}\lfloor\frac{m-(l-1-i\bmod l)}{l}\rfloor+1\\\Leftrightarrow\sum_{i=0}^{n-1}\lfloor\frac{m-i\bmod l}{l}\rfloor=\sum_{i=0}^{n-1}\lfloor\frac{m-(l-1-i\bmod l)}{l}\rfloor 这个式子容易发现只在
l\mid n 或l\mid m 时成立，证毕。
::::: 现在我们考虑对于格子(1,1) ，它被覆盖时要么向下覆盖要么向右覆盖，那么可能的木板样式只有\Theta(\sqrt n+\sqrt m) 种，我们可以尝试在\Theta(nm) 的时间复杂度内判定一个木板样式是否合法。 - 当整个网格字符都相同时，任意
n 或m 的因数长度都满足条件。 - 否则木板样式内的字符一定互不相同，这时我们考虑贪心地让每个木板向右扩展，具体地，在一个格子左侧格子和上侧格子已经被扩展的基础上，能向右扩展就向右扩展。
:::::success[证明]
如果设
(x,y) 为当前处理的格子，然后(x,y) 到(x,y+k) 都向下扩展了（k\in [0,l) ），同时(x,y+k+1) 往后会向右扩展，那么木板样式会有长度为k+1 的 border，且前k+1 格字符均相同，故木板样式内的字符均相同，与假设矛盾。 ::::: 这样我们就证明完毕了我们贪心策略的正确性，现在我们需要通过一种方式\Theta(nm) 解决这个问题，这个比较简单，考虑记vis_{i,j} 表示(i,j) 是否被扩展过，flag_{i,j} 表示(i,j) 的右侧一定距离内是否有被扩展过的点，容易在\Theta(nm) 内维护。
这样我们就做完了这道题。
时间复杂度为
code