自动搬运

查看原文

来自洛谷，原作者为

	kyEEcccccc 输不了的

搬运于2025-08-24 22:48:11，当前版本为作者最后更新于2023-09-15 16:32:27，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

考虑枚举长度 $L$：显然 $L | n,L | m$ 必须至少有一条成立，这样的 $L$ 不超过 $d(n) + d(m)$ 种；对于每个 $L$ 只有两种可能的模板串，判定即可。通过对矩阵用 $(i + j)\bmod L$ 为颜色进行染色容易证明这一结论。

如果字符矩阵全同，则唯一的模板串必然合法，这是朴素的。

接下来假设字符矩阵并不全同，我们断言：若某个位置 $(x, y)$ 左方和上方的位置都不存在或已经被填满，且可以以这个位置为起点横向填充，则它必须被横向填充。这一断言基于这样的观察：如果有一种合法方案，$(x, y)$ 被纵向填充，则模板串必须全同，而这与字符矩阵不全同相矛盾。

下面考虑证明：从 $(x, y)$ 开始的 $L$ 个位置恰为模板串，如果它们都被竖着填充，则显然模板串全同；而如果存在一个 $1\le t\le L - 1$，从 $(x, y+t)$ 开始被横向填充，前面都被纵向填充，则 $L-t$ 是模板串的一个 border，根据 border 理论我们知道 $t$ 是模板串的一个（非严格）周期，而前 $t$ 个元素都被纵向填充，显然全同；一个串的周期全同，它必然全同，所以模板串全同。

所以我们得出了这样的做法：枚举模板串以后从上往下、从左往右遍历每个位置，通过字符串哈希判定一个位置是否可以横向覆盖，如果可以直接暴力标记，否则暴力纵向标记，同时判定纵向覆盖是否合法。一个位置不会被标记两次，所以判定的过程总复杂度是 $\mathrm O(nm)$。$1000$ 以内约数个数不会太多，而且判定过程很难跑满，可以通过。

现在给出代码。写的时候发现需要一些神秘处理才能让判定复杂度不退化，但是实在比较简单，大家自己看着办吧。

// Author: kyEEcccccc

#include <bits/stdc++.h>

using namespace std;

using LL = long long;
using ULL = unsigned long long;

#define F(i, l, r) for (int i = (l); i <= (r); ++i)
#define FF(i, r, l) for (int i = (r); i >= (l); --i)
#define MAX(a, b) ((a) = max(a, b))
#define MIN(a, b) ((a) = min(a, b))
#define SZ(a) ((int)((a).size()) - 1)

constexpr int N = 1005;
constexpr ULL BS = 1145141;

int n, m;
string s[N];
ULL hsh[N][N], pw_bs[N];

ULL get_hash(int x, int y, int L)
{
	return hsh[x][y + L - 1] - hsh[x][y - 1] * pw_bs[L];
}

bool vis[N][N], nok[N][N];

bool check(int len)
{
	if (n % len != 0 && m % len != 0) return false;

	auto f = [len] (string ss, ULL hh) -> bool
	{
		memset(vis, 0, sizeof (vis));
		memset(nok, 0, sizeof (nok));
		F(i, 1, n) F(j, 1, m)
		{
			if (vis[i][j]) continue;
			if (j + len - 1 <= m && get_hash(i, j, len) == hh && !nok[i][j])
			{
				bool eq = true;
				F(k, 0, len - 1)
				{
					if (vis[i][j + k])
					{
						nok[i][j] = true;
						break;
					}
					if (s[i][j + k] != ss[k])
					{
						eq = false;
						break;
					}
				}
				if (eq)
				{
					if (nok[i][j])
					{
						F(k, 1, len - 1)
						{
							if (vis[i][j + k]) break;
							nok[i][j + k] = true;
						}
					}
					else
					{
						F(k, 0, len - 1) vis[i][j + k] = true;
						continue;
					}
				}
			}
			if (i + len - 1 > n) return false;
			F(k, 0, len - 1)
			{
				if (s[i + k][j] != ss[k]) return false;
				vis[i + k][j] = true;
			}
		}
		return true;
	};

	string x = "";
	ULL h = 0;
	if (len <= m)
	{
		F(i, 1, len) x += s[1][i], h = h * BS + s[1][i];
		if (f(x, h)) return true;
		x = "", h = 0;
	}
	if (len <= n)
	{
		F(i, 1, len) x += s[i][1], h = h * BS + s[i][1];
		if (f(x, h)) return true;
	}
	return false;
}

signed main(void)
{
	// freopen(".in", "r", stdin);
	// freopen(".out", "w", stdout);
	ios::sync_with_stdio(0), cin.tie(nullptr);

	cin >> n >> m;
	F(i, 1, n) cin >> s[i], s[i] = '#' + s[i];

	pw_bs[0] = 1;
	F(i, 1, m) pw_bs[i] = pw_bs[i - 1] * BS;

	F(i, 1, n)
	{
		hsh[i][0] = 0;
		F(j, 1, m) hsh[i][j] = hsh[i][j - 1] * BS + (ULL)s[i][j];
	}

	vector<int> ans;
	F(len, 1, max(n, m)) if (check(len)) ans.push_back(len);

	cout << ans.size() << '\n';
	for (auto x : ans) cout << x << ' ';
	cout << endl;
	
	return 0;
}