题意：

给出一串只有a和b的字符串，这个字符串是首尾相连的，同时给出如果位置为i-2为c1位置i为c2位置i+1为c3时，进行变换的话，位置i会变成c4， 每一步变换是根据该串目前的情况直接把这整个串进行改变，然后输入一个s次变换，求最终变换得到的串的序列，要求最小的（a<b）

思路：

s非常大，2x10^9 不可能一步一步的来啦。 我们注意到n<16 那么对于一个串来讲最多只有2^15中情况，也就是说如果变换的次数超过2^15次方，肯定会回到之前出现过的状态，那么这里就是一个环，那么就可以根据环的大小，环的起始位置，以及要求的变换次数，得出最终的位置。我们用一个状态数组记录得到某一个状态的第一步是多少，然后再用一个数组记录第几步是什么状态，那么当出现环的时候就很快能输出答案了，输出答案的时候要求输出最小的，于是我们分别把每一个位置作为头的串是什么都分出来，然后排一下序就行了

代码分析

状态表示： zero_one 数组存储当前字符串的每个字符（0 表示 a，1 表示 b）。 getState 函数将 zero_one 数组转换为一个整数状态，用于唯一标识当前字符串。 状态转换： changeState 函数根据重写规则更新 zero_one 数组。 重写规则通过 oper 数组存储，每个状态对应一个输出字符。 循环检测： 使用 State 数组记录每个状态出现的次数。 如果某个状态重复出现，说明进入了循环，此时可以通过数学方法快速跳过剩余的步骤。 最小字典序： 生成所有可能的循环移位形式，排序后选择字典序最小的输出。

原理

状态哈希：通过将字符串转换为整数状态，可以高效地检测状态是否重复。 循环检测：利用状态哈希值检测循环，避免重复计算。 字典序最小：通过生成所有循环移位形式并排序，找到字典序最小的字符串。

实现步骤

输入处理： 读取输入的字符串长度 n 和初始字符串。 读取 8 条重写规则，存储在 oper 数组中。 状态初始化： 将初始字符串转换为状态整数，并记录在 State 数组中。 状态转换与循环检测： 模拟每一步的状态转换。 检测是否进入循环状态，如果是，则通过数学方法快速计算最终状态。 结果输出： 生成所有可能的循环移位形式。 排序后选择字典序最小的字符串输出。

#include<iostream>
#include<cstdio>
#include<string.h>
#include<algorithm>
#include<string>
#include<deque>
#include<queue>
#include<math.h>
#include<vector>
using namespace std;
#define MAX (1<<16)+10
#define MOD 99997
const int inf = 0xfffffff;

int State[MAX];
int Index[MAX];

int zero_one[20];
int oper[20];
int tem[20];
char ans[20][20];

int n;
int getState() {
	int ret = 0;
	for (int i = 0 ; i < n ; ++i)
		ret += (zero_one[i] << i);
	return ret;
}

void changeState() {
	int state;
	for (int i = 0 ; i < n ; ++i) {
		state = (zero_one[i] << 1) + (zero_one[(i - 2 + n) % n] << 0) + (zero_one[(i + 1) % n] << 2);
		tem[i] = oper[state];
	}
	for (int i = 0 ; i < n;  ++i)
		zero_one[i] = tem[i];
}


int cmp(const void* s1, const void*s2) {
	return strcmp((char*)s1, (char*)s2);
}

void output(int state) {
	for (int i = 0 ; i < n;  ++i) {
		if (state & (1 << i)) ans[0][i] = 'b';
		else ans[0][i] = 'a';
	}
	ans[0][n] = 0;
	for (int i = 1 ; i < n ; ++i) {
		strcpy(ans[i], ans[i - 1] + 1);
		ans[i][n - 1] = ans[i - 1][0];
		ans[i][n] = 0;
	}

	qsort(ans, n, sizeof(ans[0]), cmp);
	printf("%s\n", ans[0]);
}
int main() {
	while (scanf("%d", &n) == 1) {
		char buffer[100];
		scanf("%s", buffer);
		for (int i = 0 ; i < n ; ++i)
			zero_one[i] = buffer[i] - 'a';

		memset(State, -1, sizeof(State));
		memset(Index, -1, sizeof(Index));
		State[getState()] = 0;
		Index[0] = getState();
		for (int i = 0 ; i < 8 ; ++i) {
			int state = 0;
			scanf("%s", buffer);
			state += (buffer[0] - 'a') << 0;
			state += (buffer[1] - 'a') << 1;
			state += (buffer[2] - 'a') << 2;
			oper[state] = buffer[3] - 'a';
		}

		int s;
		scanf("%d", &s);
		int tem;
		bool flag = true;
		for (int i = 1 ; i <= s ; ++i) {
			changeState();
			if (State[tem = getState()] == -1) {
				Index[i] = tem;
				State[tem] = i;
			} else {
				flag = false;

				output(Index[(s - State[tem]) % (i - State[tem]) + State[tem]]);
				break;
			}
		}
		if (flag)
			output(getState());
	}
}