[PKUSC2018]神仙的游戏

﹏ヽ暗。殇╰゛Y 2023-10-11 11:16 42阅读 0赞

[题目][Link 1]

画一画就会发现一些奇诡的性质

首先如果\\(len\\)为一个\\(\\operatorname\{border\}\\)，那么必然对于\\(\\forall i\\in \[1,len\]\\)，都会有\\(s\_i=s\_\{n-len+i\}\\)

我们大力扩展一下这个性质，发现当\\(len\\)为一个\\(\\operatorname\{border\}\\)时，我们把这个整个字符串按照\\(n-len\\)来分段，每一段都是完全相等的，最后的不完整的一段也肯定是之前的某一个前缀

换句话说，任取\\(i,j\\)在\\(\\operatorname\{mod\}\\ (n-len)\\)意义下相等，那么\\(s\_i\\)和\\(s\_j\\)也必须相等

于是我们发现通配符变得没有意义了，我们把\\(0,1\\)分别位于那些位置求出来，如果有一个\\(1\\)位于\\(i\\)位置，有一个\\(0\\)位于\\(j\\)位置，那么如果存在\\(i\\equiv j(mod\\ x)\\)，那么\\(n-x\\)不可能成为一个\\(\\operatorname\{border\}\\)

显然如果\\(x|\\operatorname\{abs\}(i-j)\\)，那么\\(i\\equiv j(mod\\ x)\\)

也就是说我们处理出\\(0,1\\)位置两两之差的绝对值，之后调和级数一下就能判断出那些不是\\(\\operatorname\{border\}\\)了

显然现在问题被转化成了一道\\(\\operatorname\{FFT\}\\)板子题

代码

#include<bits/stdc++.h>
    #define re register
    #define LL long long
    const int mod=998244353;
    const int maxn=1<<20;
    int n,len,Inv;char S[500005];
    int rev[maxn],a[maxn],b[maxn],c[maxn];
    inline int ksm(int a,int b) {
        int S=1;
        for(;b;b>>=1,a=1ll*a*a%mod) if(b&1) S=1ll*S*a%mod;
        return S;
    }
    inline void NTT(int *f,int *g) {
        for(re int i=0;i<len;i++) 
            if(i<rev[i]) std::swap(g[i],g[rev[i]]),std::swap(f[i],f[rev[i]]);
        for(re int i=2;i<=len;i<<=1) {
            int ln=i>>1,og1=ksm(3,(mod-1)/i);
            for(re int t,og=1,l=0;l<len;l+=i,og=1)
                for(re int x=l;x<l+ln;++x,og=1ll*og*og1%mod) 
                    t=1ll*f[x+ln]*og%mod,f[x+ln]=(f[x]-t+mod)%mod,f[x]=(f[x]+t)%mod,
                    t=1ll*g[x+ln]*og%mod,g[x+ln]=(g[x]-t+mod)%mod,g[x]=(g[x]+t)%mod;
        }
        for(re int i=0;i<len;i++) f[i]=1ll*f[i]*g[i]%mod;
        for(re int i=0;i<len;i++) if(i<rev[i]) std::swap(f[i],f[rev[i]]);
        for(re int i=2;i<=len;i<<=1) {
            int ln=i>>1,og1=ksm((mod+1)/3,(mod-1)/i);
            for(re int t,og=1,l=0;l<len;l+=i,og=1)
                for(re int x=l;x<l+ln;++x,og=1ll*og*og1%mod) 
                    t=1ll*f[x+ln]*og%mod,f[x+ln]=(f[x]-t+mod)%mod,f[x]=(f[x]+t)%mod;
        }
        for(re int i=0;i<len;i++) f[i]=1ll*f[i]*Inv%mod;
    }
    inline int abs(int x) {return x>=0?x:-x;}
    int main() {
        scanf("%s",S);n=strlen(S);
        for(re int i=0;i<n;i++) {
            if(S[i]=='0') a[n-i]++;
            if(S[i]=='1') b[i]++;
        }
        len=1;while(len<n+n+1) len<<=1;Inv=ksm(len,mod-2);
        for(re int i=0;i<len;i++) rev[i]=rev[i>>1]>>1|((i&1)?len>>1:0);
        NTT(a,b);
        for(re int i=1;i<n+n;i++) c[abs(i-n)]+=a[i];
        LL ans=0;
        for(re int i=1;i<n;i++) {
            int flag=0;
            for(re int j=i;j<=n;j+=i) flag|=(c[j]>0);
            if(!flag)  ans^=1ll*(n-i)*(n-i);
        }
        ans^=1ll*n*n;std::cout<<ans;
        return 0;
    }

转载于:https://www.cnblogs.com/asuldb/p/11360232.html

[Link 1]: https://www.luogu.org/problem/P5466