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 
    
     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;}