F. Shifting String - 题解
比赛与标签
比赛: Codeforces Round 797 (Div. 3) 标签: graphs, math, number theory, strings 难度: *1700
小猫咪的题目解读喵~
主人你好呀~！这道题是关于字符串和排列变换的，听起来就很有趣，对吧？喵~
是这样的：我们有一个长度为 n 的字符串 s 和一个长度为 n 的排列 p。
每一次操作，我们都会根据排列 p 来重新排列字符串 s。具体来说，新字符串的第 i 个字符，会变成原字符串的第 p[i] 个字符。注意哦，题目里是1-based的，我们写代码的时候要换成0-based，也就是 new_s[i] = s[p[i]-1]。
我们的任务就是，计算一下最少需要多少次这样的操作，才能让字符串 s 变回它最初的样子呢？题目保证了答案总是存在的，而且可能会很大，所以要用64位整数（long long）来存放结果哦。
解题思路大揭秘！
这道题的核心在于看透这个变换的本质，喵~！
1. 发现置换中的“小圈子”——置换环
我们可以把这个变换想象成 n 个位置上的字符在跳舞。排列 p 就是舞步指南：位置 i 上的字符，下一步要跳到位置 p[i]-1 上去。
如果我们一直跟着一个位置上的字符，比如从位置 0 开始，它会跳到 p[0]-1，再跳到 p[p[0]-1]-1... 这样一直跳下去，因为它总是在这 n 个位置里打转，所以总有一天会跳回原点 0。这就形成了一个封闭的“小圈子”，在数学上我们叫它 置换环 (Cycle)。
整个排列 p 可以被分解成若干个这样互不相干的置换环。一个环里的字符只会在这个环内的位置上移动，永远不会跑到别的环里去。这真是个好消息呀！因为这意味着我们可以把一个大问题分解成几个独立的小问题来解决！
2. 每个小圈子变回去要多久？
对于每一个置换环，我们想知道，环里的这些字符经过多少次操作能回到初始位置。
假设一个环的长度是 L，它包含了 L 个位置。环内的字符每次操作都会在这个环上前进一个位置（就像时钟的指针一样）。所以，经过 L 次操作，每个字符肯定都回到了自己出发的地方。
但是！有时候用不了 L 次操作哦。 我们把这个环上的字符按顺序取出来，组成一个新的临时字符串，比如叫 c_str。c_str 的长度就是 L。每次操作，c_str 都会进行一次循环移位。 我们想让 c_str 变回它自己，需要多少次移位呢？这取决于 c_str 本身的结构！
举个例子喵~
- 如果
c_str是"abcabc"，它的长度L=6。它是由"abc"重复两次构成的。我们发现只要循环移位3次，它就变回原样了！这个3就是它的 最小周期。 - 如果
c_str是"abac"，它的长度L=4。它不是由更短的子串重复构成的，所以必须移位4次才能变回来。它的最小周期就是4。
所以，对于一个长度为 L 的置换环，它恢复原状需要的最少操作次数，就是它对应字符串 c_str 的最小周期 k。这个 k 一定是 L 的一个因子。我们可以从小到大枚举 L 的所有因子 d，第一个满足 c_str 是以 d 为周期的，那 d 就是最小周期啦！
3. 让所有小圈子同时变回去！
好啦，现在我们对每个置换环，都计算出了它恢复原状的最小操作次数 k_1, k_2, k_3, ...。
我们最终的目标是让 整个字符串 s 变回初始状态。这需要 所有 的置换环 同时 恢复原状。这是一个经典的数学问题，答案就是所有这些 k_i 的 最小公倍数 (LCM)！
所以，我们的最终算法就是：
- 找出所有置换环：用一个
visited数组，遍历所有位置，如果没访问过，就从它出发找到一个完整的环。 - 计算每个环的周期：对每个环，提取出对应的字符串，并计算它的最小周期。
- 求最终答案：计算所有这些最小周期的最小公倍数。
这样一步步分析下来，是不是感觉思路清晰多啦？喵~
代码实现喵~
#include <iostream>
#include <vector>
#include <string>
#include <numeric> // C++17 for std::lcm, but here we implement it manually
// 计算两个数的最大公约数 (Greatest Common Divisor)
long long gcd(long long a, long long b) {
if (b == 0) return a;
return gcd(b, a % b);
}
// 计算两个数的最小公倍数 (Least Common Multiple)
// lcm(a, b) = (a * b) / gcd(a, b)
// 为了防止溢出，我们先做除法：(a / gcd(a, b)) * b
long long lcm(long long a, long long b) {
if (a == 0 || b == 0) return 0;
return (a / gcd(a, b)) * b;
}
void solve() {
int n;
cin >> n;
string s;
cin >> s;
vector<int> p(n);
for (int i = 0; i < n; i++) {
cin >> p[i];
p[i]--; // 转换为0-based索引，方便数组操作喵~
}
vector<bool> visited(n, false);
long long total_lcm = 1;
// 1. 找出所有置换环
for (int i = 0; i < n; i++) {
if (!visited[i]) {
vector<int> current_cycle_indices;
string cycle_str = "";
int current_node = i;
// 从当前节点出发，找到一个完整的环
while (!visited[current_node]) {
visited[current_node] = true;
current_cycle_indices.push_back(current_node);
cycle_str += s[current_node];
current_node = p[current_node];
}
// 2. 计算当前环的最小周期
int L = cycle_str.length();
long long min_period = L;
// 检查L的所有因子，找到最小的那个作为周期
for (int k = 1; k * k <= L; ++k) {
if (L % k == 0) {
// 检查因子 k
bool is_period = true;
for (int j = 0; j < L; ++j) {
if (cycle_str[j] != cycle_str[(j + k) % L]) {
is_period = false;
break;
}
}
if (is_period) {
min_period = k;
goto found_period; // 找到最小的就跳出，喵~
}
// 检查因子 L/k
if (k*k != L) {
int other_divisor = L / k;
is_period = true;
for (int j = 0; j < L; ++j) {
if (cycle_str[j] != cycle_str[(j + other_divisor) % L]) {
is_period = false;
break;
}
}
if (is_period) {
// 虽然找到了，但我们还要继续找更小的，所以这里不直接break
// 更好的方式是把所有因子存起来排序，或者像原AC代码那样
// 这里为了逻辑简单，就先这样写，原AC代码的实现更优
}
}
}
}
// 原AC代码的查找方式更标准，我们来注释它
// 它先把所有因子找出来，再从小到大检查
vector<int> divisors;
for (int d = 1; d * d <= L; d++) {
if (L % d == 0) {
divisors.push_back(d);
if (d * d != L) divisors.push_back(L / d);
}
}
sort(divisors.begin(), divisors.end()); // 从小到大检查
for (int d : divisors) {
bool valid = true;
for (int j = 0; j < L; j++) {
if (cycle_str[j] != cycle_str[(j + d) % L]) {
valid = false;
break;
}
}
if (valid) {
min_period = d;
break; // 找到第一个（也就是最小的）就跳出
}
}
found_period:;
// 3. 将当前环的周期计入总的LCM
total_lcm = lcm(total_lcm, min_period);
}
}
cout << total_lcm << endl;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t;
cin >> t;
while (t--) {
// 为了保持AC代码的原始结构，我们将逻辑放入main函数中
int n;
cin >> n;
string s;
cin >> s;
vector<int> p(n);
for (int i = 0; i < n; i++) {
cin >> p[i];
p[i]--; // 转换为0-based索引
}
vector<bool> visited(n, false);
vector<vector<int>> cycles; // 存储所有环的索引
// 步骤1：找出所有置换环
for (int i = 0; i < n; i++) {
if (!visited[i]) {
vector<int> cycle;
int cur = i;
while (!visited[cur]) {
visited[cur] = true;
cycle.push_back(cur);
cur = p[cur];
}
cycles.push_back(cycle);
}
}
vector<long long> periods; // 存储每个环的最小周期
// 步骤2：计算每个环的最小周期
for (const auto& cycle : cycles) {
int L = cycle.size();
string c = "";
for (int idx : cycle) {
c += s[idx]; // 构建环对应的字符串
}
// 找出环长L的所有因子
vector<int> divisors;
for (int d = 1; d * d <= L; d++) {
if (L % d == 0) {
divisors.push_back(d);
if (d*d != L) divisors.push_back(L/d);
}
}
sort(divisors.begin(), divisors.end()); // 排序，保证从小到大检查
long long min_period = L;
for (int d : divisors) {
bool valid = true;
for (int j = 0; j < L; j++) {
// 检查字符串c是否以d为周期
if (c[j] != c[(j + d) % L]) {
valid = false;
break;
}
}
if (valid) {
min_period = d; // 找到的第一个就是最小的
break;
}
}
periods.push_back(min_period);
}
// 步骤3：计算所有周期的最小公倍数
long long ans = 1;
for (long long d : periods) {
ans = lcm(ans, d);
}
cout << ans << endl;
}
return 0;
}复杂度分析的说
时间复杂度: O(T * N * sqrt(N)) 的说。 对于每个测试用例
T：- 寻找所有置换环是 O(N) 的，因为每个节点和边只访问一次。
- 对于每个环，我们设其长度为
L。
- 找
L的因子需要 O(sqrt(L))。 - 对每个因子
d，我们需要 O(L) 的时间来验证周期性。 - 一个数
L的因子数量d(L)相对较小。最坏情况下，对一个环的处理时间近似为 O(d(L) * L)。
- 所有环长的总和是
N。所以总时间是所有环处理时间的总和。一个宽松的上界是 O(N * sqrt(N))，因为d(L)远小于sqrt(L)。对于N <= 200，这个速度是绰绰有余的！
空间复杂度: O(N) 的说。 我们需要
p数组、s字符串、visited数组来存储基本信息，这些都是 O(N) 的。存储所有环的cycles向量，所有索引加起来也是 O(N) 的。所以总空间是 O(N) 级别。
知识点大总结！
这道题真是个结合了多种知识点的美味大餐呀，喵~
- 置换环分解 (Permutation Cycle Decomposition): 这是解决涉及排列变换问题的一个超级有用的工具！把复杂的整体变换拆解成若干个独立的环，问题就变得简单多啦。
- 最小公倍数 (LCM): 当你需要多个独立的、周期性的事件同时发生时，想到的第一个数学工具就应该是LCM！
lcm(a, b) = (a * b) / gcd(a, b)是标准公式。 - 字符串最小周期: 寻找一个字符串的最小重复单元。除了本题解中使用的枚举因子的方法，还可以使用KMP算法中的
next数组来 O(L) 求解哦！最小周期k = L - next[L](如果L能被L - next[L]整除的话)。不过对于这道题，枚举因子的方法更直观，也足够快了。 - 问题分解思想: 这道题最核心的思维方式就是“分而治之”。将一个大问题分解为互不影响的子问题，分别解决后再合并结果。这是算法竞赛中非常重要的能力呐！
希望这篇题解能帮到你哦！继续加油，享受解题的乐趣吧，喵~！