画一画就会发现一些奇诡的性质
首先如果(len)为一个(operatorname{border})，那么必然对于(forall iin [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)位置，那么如果存在(iequiv j(mod x))，那么(n-x)不可能成为一个(operatorname{border})
显然如果(x|operatorname{abs}(i-j))，那么(iequiv 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;
}