「PKUSC2018」神仙的游戏

题目链接：Click here

Solution：

这道题感觉还是不太难的。。。

考虑若存在一个长度为\(len\)的\(border\)，那么对于\(\forall i\in [1,len]\)都有\(s[i]=s[n-len+i]\)

注意到下标之间的差值为\(n-len\)，也就是说，所有下标差为\(n-len\)的位置必须相同

这里的相同包括某一个是\(?\)的情况，也就是说\(?\)其实是没有影响的

有了上面的条件，我们可以发现若有一对\((0,1)\)的位置相差\(l\)，那么对于所有的\(x|l\)，都不存在长度为\(n-x\)的\(border\)

我们已经知道本题的关键就是\((0,1)\)对了，那么如何来找呢？

考虑构造两个生成函数\(A(x),B(x)\)

我们知道卷积的形式就是指数相加，和为定值，那么我们现在要的是差为定值，那么把其中一个生成函数\(reverse\)即可

现在我们得到了新的\(C(x)=A(x)B(x)\)，\(C(x)\)的第\(i\)系数即为下标差为\(i-n\)的\((0,1)\)对数

最后我们再枚举下标差即可，时间复杂度\(O(n \log n)\)

Code:

#include
#define Pi acos(-1.0)
#define int long long 
using namespace std;
const int N=2e6+10;
const double eps=1e-3;
char s[N];
int n,ans,len=1,tim,rtt[N],f[N];
struct cp{double x,y;}A[N*2],B[N];
cp operator + (cp a,cp b){return (cp){a.x+b.x,a.y+b.y};}
cp operator - (cp a,cp b){return (cp){a.x-b.x,a.y-b.y};}
cp operator * (cp a,cp b){return (cp){a.x*b.x-a.y*b.y,a.y*b.x+a.x*b.y};}
void FFT(cp *a,int flag){
    for(int i=0;i>1);u++,w=w*wn){
                cp x=a[u],y=w*a[u+(l>>1)];
                a[u]=x+y,a[u+(l>>1)]=x-y;
            }
        }
    }
}
signed main(){
    scanf("%s",s);n=strlen(s);
    while(len<=(2*n)) len<<=1,++tim;
    for(int i=0;i>1]>>1)|((i&1)<<(tim-1));
    for(int i=0;ieps) f[i]=1;
    for(int i=1;i