考场上写炸了FFT的zzs事野蛮人（确信）

兄啊这题怎么还卡常啊！

不妨设\(n = |S|\)。那么如果串有一个长度为$i$的border，就意味着串有一个长度为\(n - i\)的循环节。

那么考虑有两个非?的位置\(i\)和\(j\)（不妨设\(i < j\)），且\(S_i\neq S_j\)。那么我们设\(l = j - i\)，则\(l\)的约数都不能成为循环节的长度，否则会出现矛盾（一个位置又要是0又要是1）。

那么考虑对于所有可能的\(l\)判定是否存在这种不合法的\(i\)与\(j\)。我们利用编辑距离函数：

\[f_l = \sum_{i} A_i A_{i + l}(A_i - A_{i + l})^2\]

这里\(A_i\)相当于\(S_i\)的一个重编码，\(S_i\)为?时应当为0，其他情况一种为1一种为2。这个函数不方便我们卷积，所以我们考虑把\(A\)翻转一下（新的序列称为\(B\)）：

\[
\begin{aligned}
f_l &= \sum_{i} B_{n - i - 1} A_{i + l}(B_{n - i - 1} A_{i + l})^2\\
&= \sum_{i} B_{n - i - 1}^3 A_{i + l} - 2B_{n - i - 1}^2 A_{i + l}^2 + B_{n - i - 1}A_{i + l}^3
\end{aligned}\]

然后问题变成了三个卷积。FFT一下就行了（请注意IDFT只需要一次……否则会被卡常）。

代码：

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <utility>
#include <cmath>
#include <complex>
#include <vector>
using R = double;
struct C {
  R x, y;
  C(R xx = 0.00, R yy = 0.00) {
    x = xx; y = yy;
  }
  R real() {
    return x;
  }
};
C operator +(const C &a, const C &b) {
  return C(a.x + b.x, a.y + b.y);
}
C operator -(const C &a, const C &b) {
  return C(a.x - b.x, a.y - b.y);
}
C operator *(const C &a, const C &b) {
  return C(a.x * b.x - a.y * b.y, a.x * b.y + a.y * b.x);
}

using ll = long long;
constexpr R pi = acos(-1);
int flip(int bi, int x) {
  int ret = 0;
  for(int i = 0; i < bi; i ++) {
    if(x & (1 << i)) {
      ret += (1 << (bi - i - 1));
    }
  }
  return ret;
}
void FFT(C *A, int bi, R flag = 1.00) {
  int n = 1 << bi;
  for(int i = 0; i < n; i ++) {
    int v = flip(bi, i);
    if(i < v) std::swap(A[v], A[i]);
  }
  for(int L = 1; L < n; L <<= 1) {
    R rd = pi / (R(L));
    C xi_n(cos(rd), sin(flag * rd));
    for(int j = 0; j < n; j += (L << 1)) {
      C xi(1.00, 0.00);
      for(int i = j; i < j + L; i ++) {
        C x = A[i], y = A[i + L];
        A[i] = x + xi * y;
        A[i + L] = x - xi * y;
        xi = xi * xi_n;
      }
    }
  }
}

const int maxn = 500005;
R tot[maxn];
C T[maxn << 2], TT[maxn << 2], D[maxn << 2];

char S[maxn];
inline int conv(char c) {
  if(c == '1') return 2;
  if(c == '0') return 1;
  return 0;
}
int A[maxn], B[maxn];
bool boom[maxn];
int main() {
  scanf("%s", S); int n = strlen(S);
  for(int i = 0; i < n; i ++) {
    A[i] = B[n - 1 - i] = conv(S[i]);
  }
  
  int len = 1, bi = 0;
  while(len < (2 * n)) {
    len <<= 1; bi ++;
  }
  
  C z(0.00, 0.00);
  // std::fill(T, T + len, z);
  // std::fill(TT, TT + len, z);
  for(int i = 0; i < n; i ++) {
    T[i] = A[i] * A[i] * A[i]; TT[i] = B[i];
  }
  FFT(T, bi); FFT(TT, bi);
  for(int i = 0; i < len; i ++) {
    D[i] = D[i] + (T[i] * TT[i]);
  }
  
  std::fill(T, T + len, z);
  std::fill(TT, TT + len, z);
  for(int i = 0; i < n; i ++) {
    T[i] = A[i] * A[i]; TT[i] = B[i] * B[i];
  }
  FFT(T, bi); FFT(TT, bi);
  for(int i = 0; i < len; i ++) {
    D[i] = D[i] + C(-2.00, 0.00) * (T[i] * TT[i]);
  }
  
  std::fill(T, T + len, z);
  std::fill(TT, TT + len, z);
  for(int i = 0; i < n; i ++) {
    T[i] = A[i]; TT[i] = B[i] * B[i] * B[i];
  }
  FFT(T, bi); FFT(TT, bi);
  for(int i = 0; i < len; i ++) {
    D[i] = D[i] + (T[i] * TT[i]);
  }
  FFT(D, bi, -1.00);
  
  for(int i = 1; i < n; i ++) {
    if(fabs(D[n - 1 + i].real() / (R(len))) > 0.99) {
      boom[i] = true;
    }
  }
  for(int i = 1; i <= n; i ++) {
    for(int j = i * 2; j <= n; j += i) {
      boom[i] = (boom[i] || boom[j]);
    }
  }
  ll ret = 0LL;
  for(int i = 1; i <= n; i ++) {
    if(!boom[n - i]) {
      ret ^= (ll(i)) * (ll(i));
    }
  }
  printf("%lld\n", ret);
  return 0;
}

• 相关文章
• 全局相关文章