Problem Description

The ant Welly now dedicates himself to urban infrastructure. He came to the kingdom of numbers and solicited an audience with the king. He recounted how he had built a happy path in the kingdom of happiness. The king affirmed Welly’s talent and hoped that this talent can help him find the best infinite fraction path before the anniversary.
The kingdom has N cities numbered from 0 to N - 1 and you are given an array D[0 … N - 1] of decimal digits (0 ≤ D[i] ≤ 9, D[i] is an integer). The destination of the only one-way road start from the i-th city is the city labelled (i2 + 1)%N.
A path beginning from the i-th city would pass through the cities u1,u2,u3, and so on consecutively. The path constructs a real number A[i], called the relevant fraction such that the integer part of it is equal to zero and its fractional part is an infinite decimal fraction with digits D[i], D[u1], D[u2], and so on.
The best infinite fraction path is the one with the largest relevant fraction

Input
The input contains multiple test cases and the first line provides an integer up to 100 indicating to the total numberof test cases.
For each test case, the first line contains the integer N (1 ≤ N ≤ 150000). The second line contains an array ofdigits D, given without spaces.
The summation of N is smaller than 2000000.

Output
For each test case, you should output the label of the case first. Then you are to output exactly N characters which are the first N digits of the fractional part of the largest relevant fraction.

Sample Input

4
3
149
5
12345
7
3214567
9
261025520

Sample Output

Case #1: 999
Case #2: 53123
Case #3: 7166666
Case #4: 615015015

题目链接：HUD-6223

题目大意

这道题的意思是给你一串字符串长度为n，从0到n-1，然后第一个位置只能通往（i*i+1）%n，这个位置然后让你输出从一个位置开始跳然后链接每个位置上的字符形成一个长度为n的字符串的字典序最大；

解题思路

毫无疑问这个题肯等要从最大的字符看是跳，但是如果最大的数字有好几个呢？那我们只有一个一个的慢慢的遍历了，但是直接遍历的话肯定会超时的，那我们该如何做呢？
我们可以用BFS加上优先队列去解决
1.因为比较字符串的字典序肯定是由前到后一个个的比较，那么我们就刚好可以有BFS吧这些字符串 进行分层，
2.但是分层的是后肯定要借助优先队列了，我们首先把最大的字符串设为第一层放入优先队列，优先队列里面的元素先按照层数由小到大出队，当层数相同时按照谁大谁先出队，然后借助BFS进行分层 每次每次放入队列的元素的层数为当前的层数+1，这样就解决了。
大致的思路有了那么就是处理起来的细节了和外加优化，
1， 当遍历到的这个位置对应的字符比队列里面的小，那么我们就可以直接结束了，因为在遍历下去也没有意义了，只会浪费时间。
2， 但遍历同一层的时候对数组进行标记，一旦这个数组被标记过了那么这个也不用遍历了，因为一个一个位置能通往的下一个位置也是固定不变的，这个字符串已经和当前的这个状态重复了。
3， 当遍历到的这个位置对应的字符比队列里面的大，那么我们就把这个一层的这个位置给更新了然后直接结束了。
4， 每当更新到下一层的时候一定要把标记数组给清空了，防止不同层数的数都是不同位置的当前最大数，比如说第一层最大是9，但是这个位置通往的下一个位置对应的数还是9，下一层还是9，这样的话如果你不更行，就会出错；
5， 因为数据太大了如果用memset初始化数组的话肯定会超时的，所以自己初始化数组，还有个小坑点就是 i*i会爆 int 所以存的时候直接用 long long

代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
char s[200000];//初始化字符串数组 
int vis[200000];//是否被标记过 
char mm[200000];//结果答案字符数组 
int f[200000];//记录位置 
int ma=0;//当前记录位置的数组里面中有几个元素 
ll n,t;
struct Node{
	ll id;//这个节点对应的字符串的位置 
	int st;//层数 
	Node(ll x=0,int y=0)// 这个是为了在队列放元素的时候直接有 Node (x,y)；这样用 
	{
		id=x;
		st=y;
	}
	friend bool operator <(Node a,Node b)//定义 优先队列里面的排列顺序
	{
		if(a.st==b.st) return s[a.id]<s[b.id];
		return a.st>b.st;	
	}
};

priority_queue<Node>que;

void bfs()
{
	int flag=-1;//表示当前是第几层 
	while(!que.empty())
	{
		Node now=que.top();
		que.pop();
		if(now.st!=flag)//如果层数变化了，那么就要初始化标记数组了 
		{
			flag=now.st;//更新当前的位置 
			while(ma)
			{
				vis[f[--ma]]=0;//初始化为零 
			}
		}
		if(now.st<n&&mm[now.st]<=s[now.id]&&!vis[now.id ])//当前位置没被标记果 
		{												//且当前的位置和结果数组的当前层数相同时放入队列中 
			vis[now.id]=1;			// 防止重复处理，将该位置标记 
			f[ma++]=now.id;        //当前这一层的数别标记的个数加一，并且记录该位置，为了方便下次初始化 
			mm[now.st]=s[now.id];//该位置的字符满足了题目要求防如结果里面这样其实也是每次都会更新结果数组的值只是等新的值都是大于等于以前的值得 
			que.push(Node((now.id*now.id+1)%n,now.st+1));//将该位置放入队列中 
		}
	}
}

int main()
{
	
	scanf("%d",&t);
	int K=1;
	while(t--)
	{
		scanf("%d%s",&n,s);
		char maxn=0;
		for(int i=0;i<n;i++)
		{
			if(s[i]>maxn) maxn=s[i];//找出最大的元素 
		}
		for(int i=0;i<n;i++) que.push(Node(i,0));//把最大的元素全部作为第一层放入优先队列里 
		bfs();//开始搜索 
		printf("Case #%d: ",K++);
        for(ll i=0;i<n;i++)
            putchar(mm[i]);
        puts("");
        for(ll i=0;i<n;i++)//每次操作完以后都要把结果数组给初始化因为是多组输入，这样避免这次结果对下次的结果造成影响 
            mm[i]=0;
	}
	return 0;
}