PKUSC2018 神仙的游戏

题目:

  小 和小 是两位神仙。他们经常在一起玩神仙才会玩的一些游戏,比如 “口算一个 4 位数是不是完全平方数” 。

  今天他们发现了一种新的游戏:首先称 长度为 的前缀成为 border 当且仅当 。给出一个由 01? 组成的字符串 , 将 中的问号用变成 01 替换,对每个 口算是否存在替换问号的方案使得 长度为 的前缀成为 border,把这个结果记做 如果 长度为 的前缀能够成为 border,否则

  由于小 和小 是神仙,所以他们计算的 的长度很长,因此把计算的结果一一比对会花费很长的时间。为了方便比对,他们规定了一个校验值: 来校验他们的答案是否相同。xor 表示按位异或。但是不巧,在某一次游戏中,他们口算出的校验值并不一样,他们希望你帮助他们来计算一个正确的校验值。当然,他们不强迫你口算,可以编程解决。

思路:

  如果长度为 的前缀成为 border,那么对于 ,都满足 。那么把所有的 根据 分组,只有每一组中不同时存在 时才合法。
  那么对于每一对 ,所有的 都会被这一对 破坏。这样就可以 枚举 ,再 处理每个前缀是否合法。那考虑优化 的枚举,如果设多项式 ,那么这两个多项式相乘得到的就是 。这样就能用NTT优化到 了。

代码:

#include <bits/stdc++.h>
#define _(...) (void)(__VA_ARGS__)
#define mset(a,b) memset(a,b,sizeof a)
#define rep(i,a,b) for(int i(a),i##_END_(b);i<=i##_END_;i++)
#define drep(i,a,b) for(int i(a),i##_END_(b);i>=i##_END_;i--)
template<class T> inline bool tomax(T &a,T b){return a<b?a=b,1:0;}
template<class T> inline bool tomin(T &a,T b){return b<a?a=b,1:0;}
typedef long long ll;
const int N=5e5+5,MOD=998244353;

namespace NTT{
    int qkpow(int x,int k){
        int ans=1;
        for(;k;k>>=1,x=(ll)x*x%MOD)
            if(k&1)ans=(ll)x*ans%MOD;
        return ans;
    }
    int inv(int x){
        return qkpow(x,MOD-2);
    }
    const int M=1<<20|5;
    int rev[M];
    void DFT(int a[],int n,bool inv_f){
        rep(i,0,n-1)
            if(i<rev[i])
                std::swap(a[i],a[rev[i]]);
        for(int l=2,m=1;l<=n;l<<=1,m<<=1){
            int base=qkpow(3,(MOD-1)/l);
            if(inv_f)base=inv(base);
            for(int *p=a;p!=a+n;p+=l){
                int w=1;
                rep(i,0,m-1){
                    int t=(ll)w*p[i+m]%MOD;
                    p[i+m]=(p[i]-t+MOD)%MOD;
                    p[i]=(p[i]+t)%MOD;
                    w=(ll)w*base%MOD;
                }
            }
        }
    }
    int a[M],b[M];
    int log2(int x){
        int r=0;
        while((1<<r)<x)r++;
        return r;
    }
    void calc(int _a[],int _b[],int res[],int n,int m){
        int lim=log2(n+m),r=1<<lim;
        rep(i,0,r-1)a[i]=b[i]=0;
        rep(i,0,n-1)a[i]=_a[i];
        rep(i,0,m-1)b[i]=_b[i];
        rep(i,0,r-1)rev[i]=(rev[i>>1]>>1)|((i&1)<<(lim-1));
        DFT(a,r,false);DFT(b,r,false);
        rep(i,0,r-1)a[i]=(ll)a[i]*b[i]%MOD;
        DFT(a,r,true);
        int ir=inv(r);
        rep(i,0,n+m-2)
            res[i]=(ll)a[i]*ir%MOD;
    }
}

char s[N];
bool mark[N];
int a[N],b[N],res[N*2];
int main(){
    scanf("%s",s+1);
    int n=strlen(s+1);
    rep(i,1,n){
        if(s[i]=='0')a[i]=1;
        if(s[i]=='1')b[n-i]=1;
    }
    NTT::calc(a,b,res,n+1,n+1);
    // rep(i,0,n)printf("a:%d\n",a[i]);
    // rep(i,0,n)printf("b:%d\n",b[i]);
    // rep(i,0,n+n)printf("res:%d\n",res[i]);
    rep(i,1,n)mark[i]=res[i+n]|res[n-i];
    rep(i,1,n)
        for(int j=i;j<=n;j+=i)
            mark[i]|=mark[j];
    ll ans=(ll)n*n;
    rep(i,1,n)
        if(!mark[i])
            ans^=(ll)(n-i)*(n-i);
    printf("%lld\n",ans);
    return 0;
}