目录

[LOJ 6436][PKUSC2018] 神仙的游戏

迁移提示
本文迁移自博客园, 原文链接

[LOJ 6436][PKUSC2018] 神仙的游戏

题意

给定一个由 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$ 为定值的下标只要不同时存在 01 就可以了.

反过来说, 如果我们找到了一对下标差为 $d$ 的 01 , 那么所有满足 $k|d$ 的 $k$ 都不能是period了.

计算对于某个 $d$ 是否存在一对下标差为 $d$ 的 01, 我们可以设 $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;
}

https://pic.rvalue.moe/2021/08/02/5454132bd68c7.png