记录编号	520630	评测结果	WAAWTTTTTT
题目名称	AACC(无题面)	最终得分	20
用户昵称	胡嘉兴	是否通过	未通过
代码语言	C++	运行时间	6.168 s
提交时间	2018-11-04 20:45:17	内存使用	0.60 MiB

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 1e5+7, p1 = 1e9+7, p2 = 1e9+9;
struct node
{
	int v1;
	int v2;
	int pos;
	bool operator < (const node & an)const
	{
		if(v1==an.v1)
		{
			return v2 < an.v2;
		}
		return v1 < an.v1;
	}
};
set<node> ss;
char s[N], ch[N], tmp[N];
void add1(int & a, int b)
{
	a += b;
	if(a>=p1)
	{
		a -= p1;
	}
	return;
}
void add2(int & a, int b)
{
	a += b;
	if(a>=p2)
	{
		a -= p2;
	}
	return;
}
int hash1(int n)
{
	int res = 0;
	for(int i = 1; i <= n; i++)
	{
		add1(res, res);
		add1(res, tmp[i]-'0');
	}
	return res;
}
int hash2(int n)
{
	int res = 0;
	for(int i = 1; i <= n; i++)
	{
		add2(res, res);
		add2(res, tmp[i]-'0');
	}
	return res;
}
int main()
{
	ll t;
	int n, beg1, beg2, c = 0, d = 0;
	beg1 = beg2 = 0;
	freopen("AACC.in", "r", stdin);
    freopen("AACC.out", "w", stdout);
	scanf("%d%lld%s", &n, &t, s+1);
	memcpy(ch, s, (n+2)*sizeof(s[0]));
	memcpy(tmp, s, (n+2)*sizeof(s[0]));
	ss.insert((node){hash1(n), hash2(n), 0});
	for(int i = 1; i <= t; i++)
	{
		tmp[1] = s[2];
		tmp[n] = s[n-1];
		for(int j = 2; j < n; j++)
		{
			tmp[j] = s[j-1]==s[j+1]?'0':'1';
		}
		int val1 = hash1(n);
		int val2 = hash2(n);
		set<node>::iterator it = ss.find((node){val1, val2, 0});
		if(it!=ss.end())
		{
			d = it->pos;
			c = i-it->pos;
			break;
		}
		else
		{
			ss.insert((node){val1, val2, i});
		}
		memcpy(s, tmp, (n+2)*sizeof(s[0]));
	}
	if(!c)
	{
		for(int i = 1; i <= n; i++)
		{
			printf("%c", s[i]);
		}
		puts("");
		return 0;
	}
	t -= d;
	t %= c;
	for(int i = 1; i < d; i++)
	{
		tmp[1] = ch[2];
		tmp[n] = ch[n-1];
		for(int j = 2; j < n; j++)
		{
			tmp[j] = ch[j-1]==ch[j+1]?'0':'1';
		}
		memcpy(ch, tmp, (n+2)*sizeof(s[0]));
	}
	for(int i = 1; i <= t; i++)
	{
		tmp[1] = ch[2];
		tmp[n] = ch[n-1];
		for(int j = 2; j < n; j++)
		{
			tmp[j] = ch[j-1]==ch[j+1]?'0':'1';
		}
		memcpy(ch, tmp, (n+2)*sizeof(s[0]));
	}
	for(int i = 1; i <= n; i++)
	{
		printf("%c", ch[i]);
	}
	puts("");
	return 0;
}