CC BY 4.0 （除特别声明或转载文章外）
如果这篇博客帮助到你，可以请我喝一杯咖啡~
题意：对一张像素图可以执行旋转、翻转、div、mix 等操作，现在给出一个操作序列，问重复进行多少次这个操作序列，可以使得任意 n*n 的像素图变回原样。
转换一下就是：设操作序列为置换$A$，则求 m 使得$A^m$为全等置换（所有元素都映射到自己）
对于每个长度为$L$的循环$B$，当$m$为$B$的整数倍时，$B^m$为全等置换，所以只需要把操作序列对应的置换拆解成多个循环，求所有循环长度的 LCM 即可，然后题目就变成了模拟。
#include <bits/stdc++.h>
#define ID(x, y) ((x)*n + (y))
using namespace std;
struct Permutation : vector<int>
{
Permutation(int n = 0) : vector<int>(n) {}
friend Permutation operator*(const Permutation &f, const Permutation &g)
{
Permutation ans(f.size());
for (int i = 0; i < f.size(); ++i)
ans[i] = g[f[i]];
return ans;
}
friend Permutation inv(const Permutation &f)
{
Permutation ans(f.size());
for (int i = 0; i < f.size(); ++i)
ans[f[i]] = i;
return ans;
}
friend vector<vector<int>> cycle(const Permutation &f)
{
vector<int> vis(f.size(), 0);
vector<vector<int>> ans;
for (int i = 0; i < f.size(); ++i)
if (!vis[i])
{
ans.push_back(vector<int>());
for (int j = i; !vis[j]; j = f[j])
vis[j] = 1, ans.back().push_back(j);
}
return ans;
}
};
int main()
{
int t, n;
char s[255] = " ";
for (scanf("%d", &t); t--;)
{
scanf("%d", &n), gets(s + 1), gets(s + 1);
Permutation f(n * n), g(n * n);
for (int i = 0; i < n; ++i)
for (int j = 0; j < n; ++j)
f[ID(i, j)] = ID(i, j);
int b = strlen(s);
for (s[b] = ' '; b; --b)
if (s[b] == ' ' && s[b - 1] != ' ')
{
int flag = s[b--] = 0;
if (s[b] == '-')
flag = 1, s[b--] = 0;
while (s[b - 1] != ' ')
--b;
for (int i = 0; i < n; ++i)
for (int j = 0; j < n; ++j)
g[ID(i, j)] =
s[b] == 'r' ? ID(n - j - 1, i) :
s[b] == 's' ? ID(i, n - j - 1) :
s[b + 1] == 'h' ? ID(i, i * 2 < n ? j : n - j - 1) :
s[b + 1] == 'v' ? ID(i * 2 < n ? i : n + n / 2 - i - 1, j) :
s[b] == 'd' ? ID(i % 2 ? i / 2 + n / 2 : i / 2, j) :
s[b] == 'm' ? ID(i / 2 * 2 + j / (n / 2), j % (n / 2) * 2 + i % 2) :
ID(i, j);
f = flag ? f * inv(g) : f * g;
}
n = 1;
vector<vector<int>> c = cycle(f);
for (int i = 0; i < c.size(); ++i)
n *= c[i].size() / __gcd((int)c[i].size(), n);
printf("%d\n", n);
if (t)
printf("\n");
}
}