Description：

给一个 $01$ 带通配符的字符串，求出每个长度 $l$ 是否是一个 $border$ 。

$1\leqslant n\leqslant 5\times 10^5$

Solution：

一眼看上去 $01$ 串通配符那不就是把串反转一下然后推个式子 $FFT$ 就没了？但是并没有那么简单，因为这样在 $border$ 互相重叠的时候是错的，因为这时不仅要让通配符匹配，还要让对应位置相同。

所以我们就需要研究一下这个题目的性质，存在一个长度为 $len$ 的 $border$ 当且仅当满足 $\forall i\in[1,n-len]$ 有 $s[i]=s[i+len]$ ，这个时候有一步重要的转化是可以枚举所有的 $01$ 对，设它们的下标之差是 $x$ ，那么所有 $y|x$ 的 $y$ 都是不合法的，我们只要把它标记出来，然后在最后求解时枚举所有的可能长度，并枚举所有它的倍数依次判断是否打过标记。

这时的复杂度瓶颈落在了 $O(n^2)$ 枚举 $01$ 对上，优化这个过程，这个时候就要用到 $FFT$ 了，构造两个生成函数： $$ A(x)=\sum_{i=0}^{n-1}[s_i=0]x^i\ \ B(x)=\sum_{i=0}^{n-1}[s_i=1]x^i $$ 我们知道多项式卷积计算的是下标和为一定的乘积的和，但是这里要统计下标差为一定的乘积的和，那就把一个多项式倒过来，然后计算卷积，就可以得到每个长度是否被标记过了。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

#define MAXN 2000010

#define R register

char s[MAXN];

#define P 998244353

int power(int a,int b)

{

	R int res = 1;

	while(b > 0)

	{

		if(b & 1)res = 1ll * res * a % P;

		a = 1ll * a * a % P;

		b = b >> 1;

	}

	return res;

}

int ww[MAXN << 1],*g = ww + MAXN;

int a[MAXN],b[MAXN];

int rev[MAXN];

void NTT(int f[],int l,int type)

{

	for(R int i = 0;i < l;++i)

	{

		if(i < rev[i])swap(f[i],f[rev[i]]);

	}

	for(R int i = 2;i <= l;i = i << 1)

	{

		R int wn = g[type * l / i];

		for(R int j = 0;j < l;j += i)

		{

			R int w = 1;

			for(R int k = j;k < j + i / 2;++k)

			{

				R int u = f[k],t = 1ll * w * f[k + i / 2] % P;

				f[k] = (u + t) % P;

				f[k + i / 2] = (u - t + P) % P;

				w = 1ll * w * wn % P;

			}

		}

	}

	if(type == -1)

	{

		for(R int i = 0;i < l;++i)f[i] = 1ll * f[i] * power(l,P - 2) % P;

	}

	return;

}

int main()

{

	scanf("%s",s);

	R int ls = strlen(s);

	for(R int i = 0;i < ls;++i)a[i] = (s[i] == '0' ? 1 : 0);

	for(R int i = 0;i < ls;++i)b[i] = (s[ls - 1 - i] == '1' ? 1 : 0);

	R int l = 0,len = 1;

	for(;len <= 2 * ls;len = len << 1,++l);

	for(R int i = 0;i < len;++i)rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (l - 1));

	g[0] = g[-len] = 1;g[1] = g[1 - len] = power(3,(P - 1) / len);

	for(R int i = 2;i < len;++i)g[i] = g[i - len] = 1ll * g[i - 1] * g[1] % P;

	NTT(a,len,1);NTT(b,len,1);

	for(R int i = 0;i < len;++i)a[i] = 1ll * a[i] * b[i] % P;

	NTT(a,len,-1);

	R long long ans = 1ll * ls * ls;

	for(R int i = 1;i < ls;++i)

	{

		R bool tag = true;

		for(R int j = i;j < ls;j += i)

		{

			if(a[ls - j - 1] || a[ls + j - 1])

			{

				tag = false;

				break;

			}

		}

		if(tag)

		{

			ans = ans ^ (1ll * (ls - i) * (ls - i));

		}

	}

	cout << ans << endl;

	return 0;

}