杭电多校第八场 Isomorphic Strings（最小表示法，循环同构）

本文主要是介绍杭电多校第八场 Isomorphic Strings（最小表示法，循环同构），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Problem Description
It is preferrable to read the pdf statment.

Two strings are called cyclical isomorphic if one can rotate one string to get another one. ‘Rotate’ here means ‘‘to take some consecutive chars (maybe none) from the beginning of a string and put them back at the end of the string in the same order’’. For example, string ‘‘abcde’’ can be rotated to string ‘‘deabc’’.

Now that you know what cyclical isomorphic is, Cuber QQ wants to give you a little test.

Here is a string s of length n. Please check if s is a concatenation of k strings, s1,s2,⋯,sk (k>1), where,

k is a divisor of n;

s1,s2,…,sk are of equal length: nk;

There exists a string t, which is cyclical isomorphic with si for all 1≤i≤k.

Print ‘‘Yes’’ if the check is positive, or ‘‘No’’ otherwise.

Input
The first line contains an integer T (1≤T≤1000), denoting the number of test cases. T cases follow.

The first line of each test case contains an integer n (1≤n≤5⋅106).

The second line contains a string s of length n consists of lowercase letters only.

It is guaranteed that the sum of n does not exceed 2⋅107.

Output
For each test case, output one line containing ‘‘Yes’’ or ‘‘No’’ (without quotes).

Sample Input
6
1
a
2
aa
3
aab
4
abba
6
abcbcc
8
aaaaaaaa

Sample Output
No
Yes
No
Yes
No
Yes

Source
2020 Multi-University Training Contest 8

题意：
将一个字符串分成k组，要求每一组都是循环同构。问是否存在这样的分法（k≥2）

思路：
k为所有字母出现次数的gcd的因数。
然后k肯定只有几百，每次再剪枝判断一下每一组的个数是否符合要求就够了。
每一组判断是否循环同构可以用最小表示法。
理论复杂度至少有4e9吧，但是因为很容易就break掉所以复杂度不会那么多，所以水过了。

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <vector>
#include <queue>
#include <iostream>
#include <map>
#include <string>
#include <set>typedef long long ll;
using namespace std;const int maxn = 5e6 + 7;int sum[maxn][30];
char s[maxn];
char sta[maxn],ed[maxn];
int b[maxn]; //每个的最小表示int mini(int n,char *tmp) {// 最小表示法int ans = 1;for (int i = 1; i <= n; i++) tmp[n+i] = tmp[i];int i = 1, j = 2, k;while (i <= n && j <= n) {for (k = 0; k < n && tmp[i+k] == tmp[j+k]; k++);if (k == n) break; // s likes "aaaaa"if (tmp[i+k] > tmp[j+k]) {i = i + k + 1;if (i == j) i++;} else {j = j + k + 1;if (i == j) j++;}}ans = min(i, j); //tmp[ans]是最小表示return ans;
}bool equal(int p1,int p2,int len) {for(int i = 1;i <= len;i++) {int x = (i + p1 - 2) % len + 1;int y = (i + p2 - 2) % len + 1;if(sta[x] != ed[y]) return false;}return true;
}bool check(int n,int k) { //分了k组if(k == 1) return false;int len = n / k;for(int i = 0;i < 26;i++) {if(sum[n][i] == 0) continue;int dat = sum[n][i] / k;for(int j = 1;j <= k;j++) {int l = (j - 1) * len + 1;int r = j * len;int num = sum[r][i] - sum[l - 1][i];if(num != dat) return false;}}for(int i = 1;i <= len;i++) {sta[i] = s[i];}b[1] = mini(len,sta);for(int i = 2;i <= k;i++) {int l = (i - 1) * len + 1;int r = i * len;for(int j = l;j <= r;j++) {ed[j - l + 1] = s[j];}b[i] = mini(len,ed);if(!equal(b[1],b[i],len)) {return false;}}return true;
}int gcd(int x,int y) {return y == 0 ? x : gcd(y,x % y);
}vector<int>DIV(int x) { //质因数分解int t = sqrt(x) + 1;vector<int>ans;for(int i = 2;i <= t;i++) {if(x % i == 0) {ans.push_back(i);if(x / i != i) {ans.push_back(x / i);}}}return ans;
}int main() {int T;scanf("%d",&T);while(T--) {int n;scanf("%d",&n);scanf("%s",s + 1);for(int i = 1;i <= n;i++) {int ch = s[i] - 'a';for(int j = 0;j < 26;j++) sum[i][j] = sum[i - 1][j];sum[i][ch]++;}int now = 0;for(int i = 0;i < 26;i++) {if(sum[n][i]) {if(!now) now = sum[n][i];else now = gcd(now,sum[n][i]);}}vector<int>div = DIV(now);div.push_back(now);int flag = 0;for(int i = 0;i < div.size();i++) {int v = div[i];if(check(n,v)) {printf("Yes\n");flag = 1;break;}}if(!flag) {printf("No\n");}}return 0;
}