传送门：洛谷 CF2194C Secret message | Codeforces C. Secret message

更佳的阅读体验：CF2194C 题解

简要题意：给你 $k$ 个长度为 $n$ 的字符串，你需要构造一个新字符串，使得每个字符都与至少一个给定字符串的相同位置的字符相同，并最小化该字符串的最小循环节长度。

首先来考虑如何处理循环节的长度。既然构造出来的字符串是由几个字符串循环而来的，那也就是说，最小循环节一定是 $n$ 的约数。因此，我们可以先找出 $n$ 的所有约数，从小到大挨个枚举是否合法。

如何判断一个最小循环节长度 $d$ 是否合法呢？

我们需要构造一个长度为 $d$ 的模式串 $t$，使得整个答案字符串由 $t$ 重复 $\dfrac{n}{d}$ 次组成。也就是说，$t$ 中的每一个位置，所选的字符都必须同时存在于给定字符串中对应的位置上。也就是说，对于一个位置 $1 \le i \le d$，所选字符必须同时存在于给定字符串的 $i, i + d, i + 2d, \cdots, i + \left ( \dfrac{n}{d} - 1 \right ) d$ 的位置上。

因为给定字符串只有小写字母的 $26$ 个字符，为了方便处理，我们对字符串进行状态压缩，$mask_i$ 存储位置 $i$ 可以使用的字符集。此时，$t_i$ 可用的字符集就一定是 $mask_i, mask_{i + d}, mask_{i + 2d}, \cdots, mask_{i + \left ( \frac{n}{d} - 1 \right ) d}$ 的交集。如果这个交集为空，意味着当前的这个 $d$ 不合法，我们直接尝试枚举下一个 $d$。

如果交集全都不为空，那么就可以直接构造答案。我们使用 __builtin_ctz 函数来获取一个数从最低位开始 $0$ 的个数，得到可用的字符，构造字符串即可。

单组数据时间复杂度 $O \left (nk + n \cdot d(n) \right )$，其中 $d(n)$ 表示 $n$ 的约数个数。

#include <iostream>
using namespace std;

const int N = 5e4 + 10;
int t, n, k, mask[N];
string s[N], ans;
vector<int> v;
bool flag;

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    for (cin >> t; t; --t) {
        v.clear();
        fill(mask + 1, mask + n + 1, 0);
        cin >> n >> k;
        for (int i = 1; i <= k; ++i) {
            cin >> s[i];
            for (int j = 1; j <= n; ++j) mask[j] |= (1 << s[i][j - 1] - 'a');
        } for (int i = 1; i <= n; ++i) if (!(n % i)) v.push_back(i);
        for (auto d : v) {
            flag = false;
            ans.clear();
            for (int i = 1; i <= d; ++i) {
                int tmp = mask[i];
                for (int j = i + d; j <= n; j += d) tmp &= mask[j];
                ans.push_back(__builtin_ctz(tmp) + 'a');
                if (!tmp) {
                    flag = true;
                    break;
                }
            } if (!flag) {
                for (int i = d; i <= n; i += d) cout << ans;
                cout << '\n';
                break;
            }
        }
    } return 0;
}