比赛 |
NOIP水题赛2 |
评测结果 |
AAATTTTTTT |
题目名称 |
AACC(无题面) |
最终得分 |
30 |
用户昵称 |
胡嘉兴 |
运行时间 |
7.687 s |
代码语言 |
C++ |
内存使用 |
3.56 MiB |
提交时间 |
2018-11-02 18:37:52 |
显示代码纯文本
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 1e5+7, p1 = 1e9+7, p2 = 1e9+9;
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;
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]));
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);
if(i==1)
{
beg1 = val1;
beg2 = val2;
}
else if(beg1==val1&&beg2==val2)
{
c = i-1;
break;
}
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 = t%c+c;
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;
}