Description

一个串T是S的循环节，当且仅当存在正整数k，使得S是T^k(即T重复k次)的前缀，比如abcd是abcdabcdab的循环节

。给定一个长度为n的仅由小写字符构成的字符串S，请对于每个k(1<=k<=n)，求出S长度为k的前缀的最短循环节的

长度per_i。字符串大师小Q觉得这个问题过于简单，于是花了一分钟将其AC了，他想检验你是否也是字符串大师。

小Q告诉你n以及per_1,per_2,...,per_n，请找到一个长度为n的小写字符串S，使得S能对应上per。

解题报告:

用时:1h20min,2WA

一开始不敢相信直接取模就行，仔细一想发现只有这样才能合法，然后发现如果\(per_i=i\)那么又是一种情况，因为\(i-1\)已经是一个最小循环节，所以只要保证不和上一个位置的循环节重叠就行，所以我们就沿着上一个循环节往回走，把所有经过的都标记一遍，然后最后\(s[i]\)取最小合法即可，注意'a'在\(per_i=i\)时是什么时候都取不到的

#include <algorithm>

#include <iostream>

#include <cstdlib>

#include <cstring>

#include <cstdio>

#include <cmath>

#define RG register

#define il inline

#define iter iterator

#define Max(a,b) ((a)>(b)?(a):(b))

#define Min(a,b) ((a)<(b)?(a):(b))

using namespace std;

const int N=1e5+5;

int n,a[N];char s[N];bool v[30];

void work()

{

	scanf("%d",&n);

	for(int i=1;i<=n;i++)scanf("%d",&a[i]);

	int x;

	s[1]='a';

	if(a[2]==2)s[2]='b';

	else s[2]='a';

	for(int i=3;i<=n;i++){

		if(i!=a[i]){

			if(i%a[i])s[i]=s[i%a[i]];

			else s[i]=s[a[i]];

		}

		else{

			x=i-1;

			while(x!=a[x]){

				if(x%a[x])x%=a[x];

				else x=a[x];

				v[s[x+1]-'a']=true;

			}

			v[0]=true;

			for(int j=0;j<=25;j++){

				if(!v[j]){

					s[i]=j+'a';break;

				}

			}

			memset(v,0,sizeof(v));

		}

	}

	for(int i=1;i<=n;i++)printf("%c",s[i]);

	puts("");

}

int main()

{

	work();

	return 0;

}