题意
给定一个由 01? 三种字符组成的字符串, 对于所有 $k\in[1,n]$ 求是否有一种把 ? 替换为 01 的方案使得 $k$ 成为原串的一个border长度. 输出合法的 $k$ 的平方的异或和.
题解
设 $B$ 为合法border长度集合, $P$ 为合法period长度集合.
首先我们根据字符串的常识, $k\in B\Leftrightarrow n-k\in P$. 所以只要找到合法period长度集合就行了. 现在我们的问题在如何验证 $k$ 是否可以是一个period. 验证 $k$ 是否是period比较简单, 只要能有一种方案使得所有 $p\bmod k$ 为某个定值的所有下标都一样就行了.
因为有通配符的存在, 也就是说对于所有 $p\bmod k$ 为定值的下标只要不同时存在 0 和 1 就可以了.
反过来说, 如果我们找到了一对下标差为 $d$ 的 0 和 1 , 那么所有满足 $k|d$ 的 $k$ 都不能是period了.
计算对于某个 $d$ 是否存在一对下标差为 $d$ 的 0 和 1, 我们可以设 $a_i=[s_i=0],b_i=[s_i=1]$, 然后求下面式子:
$$
r_d=\sum_{|i-j|=d} a_ib_j
$$
容易发现是个差卷积的形式, 我们翻转 $b$ 之后NTT来 $O(n\log n)$ 算一下就行了.
最后判断border的时候可以枚举倍数, 由调和级数结论可知复杂度也是 $O(n\log n)$ 的.
代码比较好写. 注意差卷积底下是个绝对值, 所以差是正负都要验一下.
参考代码
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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
|
#include <bits/stdc++.h>
const int G=3;
const int DFT=1;
const int IDFT=-1;
const int MAXN=2e6+10;
const int MOD=998244353;
const int PHI=MOD-1;
typedef long long intEx;
int n;
int a[MAXN];
int b[MAXN];
char s[MAXN];
int rev[MAXN];
bool blk[MAXN];
int Pow(int,int,int);
void NTT(int*,int,int);
int main(){
scanf("%s",s);
n=strlen(s);
for(int i=0;i<n;i++)
if(s[i]=='0')
a[i]=1;
else if(s[i]=='1')
b[i]=1;
int bct=0,bln=1;
std::reverse(b,b+n);
while(bln<2*n){
bln<<=1;
++bct;
}
for(int i=0;i<bln;i++)
rev[i]=(rev[i>>1]>>1)|((i&1)<<(bct-1));
NTT(a,bln,DFT);
NTT(b,bln,DFT);
for(int i=0;i<bln;i++)
a[i]=1ll*a[i]*b[i]%MOD;
NTT(a,bln,IDFT);
intEx ans=1ll*n*n;
for(int i=1;i<=n;i++){
ans^=1ll*(n-i)*(n-i);
for(int j=i;j<=n;j+=i)
if(a[n-1-j]!=0||a[n-1+j]!=0){
ans^=1ll*(n-i)*(n-i);
break;
}
}
printf("%lld\n",ans);
return 0;
}
void NTT(int* a,int len,int opt){
for(int i=0;i<len;i++)
if(rev[i]>i)
std::swap(a[i],a[rev[i]]);
for(int i=1;i<len;i<<=1){
int step=i<<1;
int wn=Pow(G,(opt*PHI/step+PHI)%PHI,MOD);
for(int j=0;j<len;j+=step){
int w=1;
for(int k=0;k<i;k++,w=1ll*w*wn%MOD){
int x=a[j+k];
int y=1ll*w*a[j+k+i]%MOD;
a[j+k]=(x+y)%MOD;
a[j+k+i]=(x-y+MOD)%MOD;
}
}
}
if(opt==IDFT){
int inv=Pow(len,MOD-2,MOD);
for(int i=0;i<len;i++)
a[i]=1ll*a[i]*inv%MOD;
}
}
inline int Pow(int a,int n,int p){
int ans=1;
while(n>0){
if(n&1)
ans=1ll*a*ans%p;
a=1ll*a*a%p;
n>>=1;
}
return ans;
}
|
