[PKUSC2018]神仙的游戏 题解

题目链接

题目大意

​ 给一个包含01?的串,求当?可能是0或者1时,有哪些长度可能成为这个串的border。

题目解法

​ 首先根据border引理,一个串有长度为 $len$ 的border当且仅当这个串模 $n-len$ 同构。

​ 当 $len \leq \frac{n}{2}$ 时,显然这个串会被分为两段,此时显然成立。另一种情况画个图看一下哪些段必须相等就会发现成立。

​ 因此,这个串有长度为 $k​$ 的border当且仅当这个串不存在任意一对 $0,1​$ 的位置差是 $n-k​$ 的倍数。

​ 可以类似万径人踪灭地构造两个多项式 $ A=\sum_{i=0}^{n-1} [s_i=0]x^i, B=\sum_{i=0}^{n-1} [s_i=1]x^i$。翻转B然后卷积即可计算出位置差,然后调和级数枚举倍数即可。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include <bits/stdc++.h>
#define maxn 2000005
#define ll long long
const int ouuan=167772161;
const int p=ouuan;
const int g=3;

int a[maxn],b[maxn],rev[maxn]={0};
char s[maxn];

int qpow(int a,int b){
if (b==0)return 1;
int d=qpow(a,b>>1);d=(ll)d*d%ouuan;
if (b&1)d=(ll)d*a%ouuan;
return d;
}

void NTT(int *a,int type,int lim){
for (int i=0;i<lim;++i)rev[i]=(rev[i>>1]>>1)|((i&1)*(lim>>1));
for (int i=0;i<lim;++i)if (i<rev[i])std::swap(a[i],a[rev[i]]);
for (int len=1;len<lim;len<<=1){
int wn=qpow(g,(ouuan-1)/(len<<1)),r=len<<1;
if (type==-1)wn=qpow(wn,ouuan-2);
for (int j=0;j<lim;j+=r)
for (int k=0,w=1;k<len;++k,w=(ll)w*wn%ouuan){
int x=a[j+k],y=(ll)w*a[j+k+len]%ouuan;
a[j+k]=(x+y)%ouuan;a[j+k+len]=(x-y+ouuan)%ouuan;
}
}if (type==-1)for (int i=0;i<lim;++i)a[i]=(ll)a[i]*qpow(lim,ouuan-2)%ouuan;
}

int main(){
scanf("%s",s+1);int n=std::strlen(s+1);
for (int i=1;i<=n;++i)a[i-1]=(s[i]=='0');
for (int i=1;i<=n;++i)b[i-1]=(s[n-i+1]=='1');
int lim=1;while(lim<=n*2)lim<<=1;
NTT(a,1,lim);NTT(b,1,lim);
for (int i=0;i<lim;++i)a[i]=(ll)a[i]*b[i]%ouuan;
NTT(a,-1,lim);
ll ans=(ll)n*n;
for (int i=1;i<n;++i){
int flag=0;
for (int j=i;j<=n+1;j+=i)flag|=a[j+n-1]|a[n-j-1];
if (!flag)ans^=(ll)(n-i)*(n-i);
}printf("%lld",ans);
return 0;
}