传送门

Sol

自己还是太 \(naive\) 了，上来就构造多项式和通配符直接匹配，然后遇到 \(border\) 相交的时候就 \(gg\) 了

神仙的游戏蒟蒻还是玩不来

一个小小的性质：

存在长度为 \(len\) 的 \(border\) 的充要条件是 \(\forall i,s_i=s_{n-len+i}\)

等价于按照 \(n-len\) 的剩余系分类，那么每一类都要求不同时含有 \(0,1\)

考虑两个位置 \(i,j\) 分别为 \(0,1\) 会对于哪一些长度的 \(border\) 有影响

显然是满足 \(|i-j|\equiv 0 (mod~n-len)\) 的 \(len\)，即 \((n-len)|(|i-j|)\)

设 \(f_x\) 表示 \(|i-j|=x\) 是否存在 \(s_i,s_j\) 分别为 \(0,1\)

这个是一个经典套路

只要对于 \(s_i=1\) 和 \(s_i=0\) 分别构造函数，\(FFT\) 一下就好了

# include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int maxn(4e6 + 5);

const double pi(acos(-1));

struct Complex {

	double a, b;

	inline Complex() {

		a = b = 0;

	}

	inline Complex(double x, double y) {

		a = x, b = y;

	}

	inline Complex operator +(Complex x) const {

		return Complex(a + x.a, b + x.b);

	}

	inline Complex operator -(Complex x) const {

		return Complex(a - x.a, b - x.b);

	}

	inline Complex operator *(Complex x) const {

		return Complex(a * x.a - b * x.b, a * x.b + b * x.a);

	}

} a[maxn], b[maxn], w[maxn];

int deg, r[maxn], l;

inline void Init(int n) {

	register int i, k;

	for (deg = 1, l = 0; deg < n; deg <<= 1) ++l;

	for (i = 0; i < deg; ++i) r[i] = (r[i >> 1] >> 1) | ((i & 1) << (l - 1));

	for (i = 1; i < deg; i <<= 1)

		for (k = 0; k < i; ++k) w[deg / i * k] = Complex(cos(pi / i * k), sin(pi / i * k));

}

inline void FFT(Complex *p, int opt) {

	register int i, j, k, t;

	register Complex wn, x, y;

	for (i = 0; i < deg; ++i) if (r[i] < i) swap(p[r[i]], p[i]);

	for (i = 1; i < deg; i <<= 1)

		for(t = i << 1, j = 0; j < deg; j += t)

			for (k = 0; k < i; ++k) {

				wn = w[deg / i * k];

				if (opt == -1) wn.b *= -1;

				x = p[j + k], y = wn * p[i + j + k];

				p[j + k] = x + y, p[i + j + k] = x - y;

			}

}

int n, len, f[maxn], g[maxn];

ll ans;

char s[maxn];

int main() {

	register int i, j;

	scanf(" %s", s + 1), n = strlen(s + 1);

	for (i = 1; i <= n; ++i) f[i] = s[i] == '0', g[i] = s[n - i + 1] == '1';

	for (len = 1; len <= n + n; len <<= 1);

	for (i = 1; i <= n; ++i) a[i].a = f[i], b[i].a = g[i];

	Init(len), FFT(a, 1), FFT(b, 1);

	for (i = 0; i < len; ++i) a[i] = a[i] * b[i];

	FFT(a, -1);

	for (i = 0; i <= n + n; ++i) f[i] = (int)(a[i].a / len + 0.5);

	for (i = 1; i <= n; ++i) g[i] = f[n + 1 - i] + f[n + 1 + i];

	for (i = 1; i <= n; ++i)

		for (j = i; j <= n; j += i) g[i] |= g[j];

	for (i = 1; i <= n; ++i) if (!g[n - i]) ans ^= 1LL * i * i;

	printf("%lld\n", ans);

    return 0;

}