祎隋

PKUSC2018神仙的游戏
链接题解:前置芝士:kmp的next算循环节:当满足i%(i-next[i])==0,则循环节长度为i-next[...
扫描右侧二维码阅读全文
04
2019/04

PKUSC2018神仙的游戏

链接

题解:
前置芝士:

kmp的next算循环节:

当满足i%(i-next[i])==0,则循环节长度为i-next[i]

p为s的循环节,|S|-p为一个border

常规套路凑一下卷积搞一下就行了

code:

#include<bits/stdc++.h>
#define maxn 500005
using namespace std;
typedef long long ll;
const ll mod=998244353;
int n;
char s[maxn];
ll x1[maxn*3],x2[maxn*3],x3[maxn*3];
ll qkpow(ll t,ll pos){
    ll ans=1,base=t;
    while(pos){
        if(pos&1) ans=ans*base%mod;
        base=base*base%mod;
        pos>>=1;
    }
    return ans;
}
void change(ll y[],int len){
    for(int i=1,j=len/2;i<len-1;i++){
        if(i<j) swap(y[i],y[j]);
        int k=len>>1;
        while(j>=k){
            j-=k;
            k>>=1;
        }
        if(j<k) j+=k;
    }
}
void ntt(ll y[],int len,int on){
    change(y,len);
    for(int h=2;h<=len;h<<=1){
        ll base=qkpow(3,(mod-1)/h);
        if(on==-1) base=qkpow(base,mod-2);
        for(int j=0;j<len;j+=h){
            ll w=1;
            for(int k=j;k<j+h/2;k++){
                ll t1=y[k];
                ll t2=w*y[k+h/2]%mod;
                y[k]=(t1+t2)%mod;
                y[k+h/2]=(t1-t2+mod)%mod;
                w=w*base%mod;
            }
        }
    }
    ll inv=qkpow(len,mod-2);
    if(on==-1){
        for(int i=0;i<len;i++) y[i]=y[i]*inv%mod;
    }
}
int vis[maxn<<1];
void init(){
    scanf("%s",s);
    n=strlen(s);
    int len=1;
    for(len=1;len<(n<<1);len<<=1);
    for(int i=0;i<n;i++) x1[i]=(s[i]=='0');
    for(int i=0;i<n;i++) x2[i]=(s[n-i-1]=='1');
    ntt(x1,len,1);
    ntt(x2,len,1);
    for(int i=0;i<len;i++) x1[i]=x1[i]*x2[i]%mod;
    ntt(x1,len,-1);
    ll ans;
    for(int i=n;i<2*n-1;i++)if(x1[i])vis[i-n+1]=1;
    for(int i=0;i<n;i++)if(x1[i])vis[n-i-1]=1;
    for(int i=1;i<n;i++)for(int j=i;j<=n;j+=i)vis[i]|=vis[j];
    ans=(ll)n*n;
    for(int i=1;i<n;i++)if(!vis[i])ans^=(ll)(n-i)*(n-i);
    printf("%lld\n",ans);
}
int main(){
    init();
     
    return 0;
}
Last modification:April 5th, 2019 at 08:13 am

Leave a Comment