本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-11-14 17:27:04

:::::info[题目基本信息] 考察：贪心，哈希 Hashing，Ad-hoc（省选/NOI-）。
题目简介：
给定一个 $n\times m$ 的仅由小写英文字母组成的网格图，现在你需要构造一个任意长度的木板，上面每一个都有一个小写英文字母，你可以左右或上下放置该木板，但是不能调转该木板的方向，你现在需要用这个木板铺满网格图，问所有可能的木板长度有哪些。
数据范围：

• $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)$ 内维护。

这样我们就做完了这道题。
时间复杂度为 $\Theta(nm(\sqrt n+\sqrt m))$，空间复杂度为 $\Theta(nm)$。

code