[BZOJ5372] 神仙的游戏

摘要

一道综合生成函数和多项式乘法的题

这道题提醒我,空间一定要开够!(记得双倍,尤其是计算长度的时候)

题意

定义字符串 的 border 是满足以下条件的

字符串本身由 01? 组成,其中?可以同时匹配 01.

求所有 border 的 的异或和。

分析

首先要知道 border 与循环节是一一对应的,因此需要我们找到合法的循环节长度。

对于长度为 的循环节,将 的字符按 的剩余类分组,那么该循环节合法的充要条件就是,同一组内不能同时出现 01.

由于判断合法的循环节复杂度过高,我们想办法求不合法的循环节。

考虑 ,如果 一个为 0 一个为 1,那么显然 的循环节是不合法的。除此之外, 的约数的循环节也是不合法的。

对于这样的关系,我们尝试构造生成函数:

上述生成函数分别表示当 时, 的系数有 1 的贡献。而两者的卷积

的系数显然表示当 的时候不合法循环节的截点数。利用这个系数,我们就可以确定每一个循环节是否合法(判断是否为 0)

但是这个多项式并不是普通意义下的多项式乘法。因为 的指数是负数。这个好办,我们指数同时加一个 即可。

这里我们不关心 的系数(因为这是我们要算的),只需要知道 的系数都对应长度 的截点数即可

那么 FFT 一下,现在我们知道每个循环节本身的合法性,又因为对于不合法的 ,其约数的循环节也是不合法的,那么我们 对整个序列筛一下倍数即可。

代码

#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#define PI M_PI
using namespace std;
const int N=(1<<20)+5;
struct cpx{
    double a,b;
    cpx(double _a=0,double _b=0){a=_a,b=_b;}
    cpx operator+(cpx c){return cpx(a+c.a,b+c.b);}
    cpx operator-(cpx c){return cpx(a-c.a,b-c.b);}
    cpx operator*(cpx c){return cpx(a*c.a-b*c.b,a*c.b+b*c.a);}
};
int tr[N],dgl;
void trans(cpx *y,int len){for(int i=1;i<len;i++)if(i<tr[i])swap(y[i],y[tr[i]]);}
void fft(cpx *y,int len,int tag){trans(y,len);
    for(int j=1;j<len;j<<=1){cpx wn(cos(PI/j),tag*sin(PI/j));
        for(int i=0;i<len;i+=j<<1){cpx w(1,0),u,v;
            for(int k=i;k<i+j;k++)u=y[k],v=y[k+j]*w,y[k]=u+v,y[k+j]=u-v,w=w*wn;
        }
    }
    if(tag==-1)for(int i=0;i<len;i++)y[i].a/=len;
}

char s[N];
int ls,len=1;
cpx A[N],B[N];
int f[N],g[N];
int main(){scanf("%s",s+1);
    ls=strlen(s+1);
    while(len<(ls<<1))len<<=1,dgl++;
    for(int i=1;i<len;i++)tr[i]=(tr[i>>1]>>1)|(i&1)<<(dgl-1);
    for(int i=1;i<=ls;i++)A[i].a=(s[i]=='1'),B[ls-i].a=(s[i]=='0');
    fft(A,len,1),fft(B,len,1);
    for(int i=0;i<len;i++)A[i]=A[i]*B[i];
    fft(A,len,-1);
    for(int i=0;i<ls;i++)f[i]=(int)(A[ls+i].a+0.1)+(int)(A[ls-i].a+0.1);
    f[ls]=0;
    for(int i=1;i<=ls;i++){
        bool fl=1;
        for(int j=1;i*j<=ls;j++)if(f[i*j]){fl=0;break;}
        g[ls-i]=fl;
    }
    g[ls]=1;
    long long ans=0;
    for(int i=0;i<=ls;i++)if(g[i])ans=ans^((long long)i*i);
    printf("%lld",ans);
    return 0;
}

 上一篇
金华 DAY2 自闭 金华 DAY2 自闭
摘要 菜板:ZROI 改名 XYOI 完美理论Sutask1 暴力即可 Subtask2树形 DP 即可 STD枚举起始点 抽象出最大权闭合子图模型 模型: 将点分两种,正权和负权 正负之间的边容量为正无穷 考虑最小割的意义:正
2019.02.16
下一篇 
多项式与多项式乘法 多项式与多项式乘法
摘要 鸽鸽给我们讲课啦 据说讲课前通宵玩了两天。早上灵车漂移。 多项式定义给定一个环 ,( 通常是交换环,可以是有理数、实数或者复数等等)以及一个未知数 x,则任何形同 \sum_{i=0}^na
2019.02.15
  目录