【PKUSC2018】神仙的游戏
FFT
题目大意：
给定一个由0，1，?组成的字符串。
其中?可以代表0或1。
令 $f(i)$ 表示，是否存在一种?的填法，使得这个字符串存在长度为 $i$ 的 border。$f(i)$ 的值为 $0$ 或 $1$。
求 $\oplus_{i=1}^n i^2f(i)$。其中 $\oplus$ 表示求异或和。
题解：
考虑 border 的一些性质。
如果存在长度为 $i$ 的 border，那么这个字符串必然有长度为 $n-i$ 的循环节（最后一部分可能只有前缀满足循环节）。
那么对于一对0和1，如果它们距离为 $x$，那么循环节就不可能为 $x$ 的因数了，否则不匹配无法构成循环。
假如我们知道 $d_i$ 表示是否有一对0和1距离为 $i$，那么我们需要知道 $f(n-k)$ 的值，只需要枚举 $k$ 的倍数 ，看是否所有 $d_{kt}$ 都为 $0$ 即可。对所有 $k$ 枚举倍数的复杂度是 $O(n\log n)$。这里通配符的存在不会产生影响。
那么现在如何求 $d$ 呢？
以下考虑字符串时以 $0$ 为开始位置。
考虑构造多项式 $A(x)=\sum_{i=0}^{n-1}[s_i=0]x^i$，$B(x)=\sum_{i=0}^{n-1}[s_i=1]x^i$.
那么如果 $[p]A(x)\times [q]B(x)=1$，则 $d_{|p-q|}=1$。
考虑将 $B(x)$ 翻转，则如果 $[p]A(x)\times [n-1-q]B(x)=1$，则 $d_{|p-q|}=1$。
我们求出 $A(x)B(x)$ 的各项系数，则其第 $i$ 项系数为 $1$，那么 $d_{|i-n+1|}=1$。
用 FFT 即可。
时间复杂度 $O(n\log n)$。
Code：
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdlib>
using namespace std;
const int md=1004535809,g3=(md+1)/3;
typedef long long LL;
const int N=1<<20|1;
int A[N],B[N],n,rev[N],lim;
char s[N];
bool b[N],d[N];
inline void upd(int&a){a+=a>>31&md;}
inline int pow(int a,int b){
int ret=1;
for(;b;b>>=1,a=(LL)a*a%md)if(b&1)ret=(LL)ret*a%md;
return ret;
}
void init(int n){
int l=-1;
for(lim=1;lim<n;lim<<=1)++l;
for(int i=1;i<lim;++i)rev[i]=(rev[i>>1]>>1)|((i&1)<<l);
}
void NTT(int*a,int f){
for(int i=1;i<lim;++i)if(i<rev[i])swap(a[i],a[rev[i]]);
for(int i=1;i<lim;i<<=1){
const int gi=pow(f?3:g3,(md-1)/(i<<1));
for(int j=0;j<lim;j+=i<<1)
for(int k=0,g=1;k<i;++k,g=(LL)g*gi%md){
const int x=a[j+k],y=(LL)a[j+k+i]*g%md;
upd(a[j+k]+=y-md),upd(a[j+k+i]=x-y);
}
}
if(!f){
const int iv=pow(lim,md-2);
for(int i=0;i<lim;++i)a[i]=(LL)a[i]*iv%md;
}
}
int main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
cin>>s;
n=strlen(s);
for(int i=0;i<n;++i)A[i]=s[i]=='0',B[n-i-1]=s[i]=='1';
init(n<<1);
NTT(A,1),NTT(B,1);
for(int i=0;i<lim;++i)A[i]=(LL)A[i]*B[i]%md;
NTT(A,0);
for(int i=0;i<lim;++i)if(A[i])
d[abs(i-n+1)]=1;
for(int i=1;i<=n;++i){
b[n-i]=1;
for(int j=i;j<=n;j+=i)if(d[j]){
b[n-i]=0;break;
}
}
b[n]=1;
LL ans=0;
for(int i=1;i<=n;++i)
ans^=(LL)i*i*b[i];
cout<<ans<<'\n';
return 0;
}