测试47。
嗯。
题解懒得写了,我要去打FFT了。
(其实是不会写)。
没有看懂的T3代码
#include<bits/stdc++.h>
#define F(i,a,b) for(rg int i=a;i<=b;++i)
#define rg register
#define LL long long
#define il inline
#define pf(a) printf("%d ",a)
#define phn puts("")
using namespace std;
int read();
/*
1:为什么用next
2:>c*2时,完整循环节末尾不能是0是为了避免有新的循环节,但是如何保证避免的循环不在t集合
3:已有循环节,即t集合,是怎么保证的?
4:为何接后缀
对了,两个nxt不一样。
*/
#define N 200010
char a[N];
int n;
int nxt[N],c[N],tot,nex[N],b[N];
#define mem(a,x) memset(a,x,sizeof(a))
il void init(){
tot=0;
//mem(nxt,0);mem(nex,0);mem(b,0);mem(c,0);
}
il void work(){
init();
for(rg int i=2,j=0;i<=n;++i){
while(j&&a[j+1]!=a[i])j=nxt[j];
if(a[j+1]==a[i])++j;
nxt[i]=j;
}
rg int x=n;
while(x){c[++tot]=x;x=nxt[x];}
reverse(c+1,c+tot+1);
//F(i,1,tot)pf(c[i]);phn;
F(i,1,c[1]-1)b[i]=0;b[c[1]]=1;b[1]=0;
rg int p=0;
F(i,2,c[1]){
while(p&&b[p+1]!=b[i])p=nex[p];
if(b[p+1]==b[i])++p;
nex[i]=p;
}
F(i,2,tot){
if(c[i-1]*2>=c[i]){
F(j,c[i-1]+1,c[i]){
b[j]=b[j-(c[i]-c[i-1])];
while(p&&b[p+1]!=b[j])p=nex[p];
if(b[p+1]==b[j])++p;
nex[j]=p;
}
}
else{
F(j,c[i-1]+1,c[i]-c[i-1]-1){
b[j]=0;
while(p&&b[p+1]!=b[j])p=nex[p];
if(b[p+1]==b[j])++p;
nex[j]=p;
}
int ok=1,u=p,w=c[i]-c[i-1];
while(u){
if(b[u+1]==0){
if(w%(w-u-1)==0){
//nex重叠,构成循环节
ok=0;break;
}
}
u=nex[u];
}
if(b[u+1]==0){
if(w%(w-u-1)==0){
ok=0;
}
}
b[w]=!ok;
while(p&&b[p+1]!=b[w])p=nex[p];
if(b[p+1]==b[w])++p;
nex[w]=p;
F(j,w+1,c[i]){
b[j]=b[j-w];
while(p&&b[p+1]!=b[j])p=nex[p];
if(b[p+1]==b[j])++p;
nex[j]=p;
}
}
}
//F(i,1,n)pf(nxt[i]);phn;
//F(i,1,n)pf(nex[i]);phn;
F(i,1,n)putchar(b[i]+'0');phn;
}
int main(){
// freopen("1.in","r",stdin);
int T=read();
while(T--){
scanf("%s",a+1);
n=strlen(a+1);
work();
}
}
il int read(){
int s=0;rg char ch;
while(ch=getchar(),!isdigit(ch));
for(;isdigit(ch);s=s*10+(ch^48),ch=getchar());
return s;
}
/*
g++ 1.cpp -g
./a.out
3
YDYYDY
JRYJREJRYJR
YDYAKYDY
*/
知识兔View Code#include<bits/stdc++.h>
#define F(i,a,b) for(rg int i=a;i<=b;++i)
#define rg register
#define LL long long
#define il inline
#define pf(a) printf("%d ",a)
#define phn puts("")
using namespace std;
int read();
/*
1:为什么用next
2:>c*2时,完整循环节末尾不能是0是为了避免有新的循环节,但是如何保证避免的循环不在t集合
3:已有循环节,即t集合,是怎么保证的?
4:为何接后缀
对了,两个nxt不一样。
*/
#define N 200010
char a[N];
int n;
int nxt[N],c[N],tot,nex[N],b[N];
#define mem(a,x) memset(a,x,sizeof(a))
il void init(){
tot=0;
//mem(nxt,0);mem(nex,0);mem(b,0);mem(c,0);
}
il void work(){
init();
for(rg int i=2,j=0;i<=n;++i){
while(j&&a[j+1]!=a[i])j=nxt[j];
if(a[j+1]==a[i])++j;
nxt[i]=j;
}
rg int x=n;
while(x){c[++tot]=x;x=nxt[x];}
reverse(c+1,c+tot+1);
//F(i,1,tot)pf(c[i]);phn;
F(i,1,c[1]-1)b[i]=0;b[c[1]]=1;b[1]=0;
rg int p=0;
F(i,2,c[1]){
while(p&&b[p+1]!=b[i])p=nex[p];
if(b[p+1]==b[i])++p;
nex[i]=p;
}
F(i,2,tot){
if(c[i-1]*2>=c[i]){
F(j,c[i-1]+1,c[i]){
b[j]=b[j-(c[i]-c[i-1])];
while(p&&b[p+1]!=b[j])p=nex[p];
if(b[p+1]==b[j])++p;
nex[j]=p;
}
}
else{
F(j,c[i-1]+1,c[i]-c[i-1]-1){
b[j]=0;
while(p&&b[p+1]!=b[j])p=nex[p];
if(b[p+1]==b[j])++p;
nex[j]=p;
}
int ok=1,u=p,w=c[i]-c[i-1];
while(u){
if(b[u+1]==0){
if(w%(w-u-1)==0){
//nex重叠,构成循环节
ok=0;break;
}
}
u=nex[u];
}
if(b[u+1]==0){
if(w%(w-u-1)==0){
ok=0;
}
}
b[w]=!ok;
while(p&&b[p+1]!=b[w])p=nex[p];
if(b[p+1]==b[w])++p;
nex[w]=p;
F(j,w+1,c[i]){
b[j]=b[j-w];
while(p&&b[p+1]!=b[j])p=nex[p];
if(b[p+1]==b[j])++p;
nex[j]=p;
}
}
}
//F(i,1,n)pf(nxt[i]);phn;
//F(i,1,n)pf(nex[i]);phn;
F(i,1,n)putchar(b[i]+'0');phn;
}
int main(){
// freopen("1.in","r",stdin);
int T=read();
while(T--){
scanf("%s",a+1);
n=strlen(a+1);
work();
}
}
il int read(){
int s=0;rg char ch;
while(ch=getchar(),!isdigit(ch));
for(;isdigit(ch);s=s*10+(ch^48),ch=getchar());
return s;
}
/*
g++ 1.cpp -g
./a.out
3
YDYYDY
JRYJREJRYJR
YDYAKYDY
*/