自动搬运

查看原文

来自洛谷，原作者为

	asuldb 哭晕了喵

搬运于2025-08-24 22:11:03，当前版本为作者最后更新于2019-08-15 20:04:44，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题目

画一画就会发现一些奇诡的性质

首先如果$len$为一个$\operatorname{border}$，那么必然对于$\forall i\in [1,len]$，都会有$s_i=s_{n-len+i}$

我们大力扩展一下这个性质，发现当$len$为一个$\operatorname{border}$时，我们把这个整个字符串按照$n-len$来分段，每一段都是完全相等的，最后的不完整的一段也肯定是之前的某一个前缀

换句话说，任取$i,j$在$\operatorname{mod}\ (n-len)$意义下相等，那么$s_i$和$s_j$也必须相等

于是我们发现通配符变得没有意义了，我们把$0,1$分别位于那些位置求出来，如果有一个$1$位于$i$位置，有一个$0$位于$j$位置，那么如果存在$i\equiv j(mod\ x)$，那么$n-x$不可能成为一个$\operatorname{border}$

显然如果$x|\operatorname{abs}(i-j)$，那么$i\equiv j(mod\ x)$

也就是说我们处理出$0,1$位置两两之差的绝对值，之后调和级数一下就能判断出那些不是$\operatorname{border}$了

显然现在问题被转化成了一道$\operatorname{FFT}$板子题

代码

#include<bits/stdc++.h>
#define re register
#define LL long long
const int mod=998244353;
const int maxn=1<<20;
int n,len,Inv;char S[500005];
int rev[maxn],a[maxn],b[maxn],c[maxn];
inline int ksm(int a,int b) {
	int S=1;
	for(;b;b>>=1,a=1ll*a*a%mod) if(b&1) S=1ll*S*a%mod;
	return S;
}
inline void NTT(int *f,int *g) {
	for(re int i=0;i<len;i++) 
		if(i<rev[i]) std::swap(g[i],g[rev[i]]),std::swap(f[i],f[rev[i]]);
	for(re int i=2;i<=len;i<<=1) {
		int ln=i>>1,og1=ksm(3,(mod-1)/i);
		for(re int t,og=1,l=0;l<len;l+=i,og=1)
			for(re int x=l;x<l+ln;++x,og=1ll*og*og1%mod) 
				t=1ll*f[x+ln]*og%mod,f[x+ln]=(f[x]-t+mod)%mod,f[x]=(f[x]+t)%mod,
				t=1ll*g[x+ln]*og%mod,g[x+ln]=(g[x]-t+mod)%mod,g[x]=(g[x]+t)%mod;
	}
	for(re int i=0;i<len;i++) f[i]=1ll*f[i]*g[i]%mod;
	for(re int i=0;i<len;i++) if(i<rev[i]) std::swap(f[i],f[rev[i]]);
	for(re int i=2;i<=len;i<<=1) {
		int ln=i>>1,og1=ksm((mod+1)/3,(mod-1)/i);
		for(re int t,og=1,l=0;l<len;l+=i,og=1)
			for(re int x=l;x<l+ln;++x,og=1ll*og*og1%mod) 
				t=1ll*f[x+ln]*og%mod,f[x+ln]=(f[x]-t+mod)%mod,f[x]=(f[x]+t)%mod;
	}
	for(re int i=0;i<len;i++) f[i]=1ll*f[i]*Inv%mod;
}
inline int abs(int x) {return x>=0?x:-x;}
int main() {
	scanf("%s",S);n=strlen(S);
	for(re int i=0;i<n;i++) {
		if(S[i]=='0') a[n-i]++;
		if(S[i]=='1') b[i]++;
	}
	len=1;while(len<n+n+1) len<<=1;Inv=ksm(len,mod-2);
	for(re int i=0;i<len;i++) rev[i]=rev[i>>1]>>1|((i&1)?len>>1:0);
	NTT(a,b);
	for(re int i=1;i<n+n;i++) c[abs(i-n)]+=a[i];
	LL ans=0;
	for(re int i=1;i<n;i++) {
		int flag=0;
		for(re int j=i;j<=n;j+=i) flag|=(c[j]>0);
		if(!flag)  ans^=1ll*(n-i)*(n-i);
	}
	ans^=1ll*n*n;std::cout<<ans;
	return 0;
}