题解 P9417

· · 题解

考虑枚举长度 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;
}