「PKUSC2018」神仙的游戲

題意：給出一個(gè)01?串，其中?可以代替成為0或1，令 $ F(i) $ 表示是否存在長(zhǎng)度為 $ i $ 的border，求 $ (F(1) \times 1 \times 1) \bigoplus (F(2) \times 2 \times 2) \bigoplus (F(3) \times 3 \times 3) \dots \bigoplus (F(n) \times n \times n) $ 。

做法：
對(duì)于第一個(gè)subtask，枚舉每長(zhǎng)度的border然后暴力匹配是否存在即可。
對(duì)于第二個(gè)subtask，字符串哈希判斷字符串前后綴是否相同即可。
然后考慮對(duì)于一個(gè)長(zhǎng)度為 $ len $ 的border，那么所有距離為 $ n-len $ 的數(shù)字都相同（問號(hào)可以轉(zhuǎn)成0或1）。對(duì)于一個(gè)長(zhǎng)度為 $ len $ 的border不存在，當(dāng)且僅當(dāng)存在距離為 $ n-len $ 的倍數(shù)的數(shù)字不同。
對(duì)于第四個(gè)subtask，枚舉記錄01的距離即可。
對(duì)于第五個(gè)subtask，設(shè)原串為 $ s $ ，考慮快速記錄01距離，當(dāng)存在距離為x的0和1，都有 $ \sum_{j-i=x}{ [ s[j] != s[i] ] } $ ， 若 $ A_{i} = [ s[i] = 1 ] $ , $ B_{i} = [ s[n-i-1] = 1 ] $ ， 則 $ A \times B = \sum_{n+j-i=x}{s[j] != s[i]} $ 。FFT/NTT 即可。

#include<bits/stdc++.h> #define rep(i,a,b) for(int i=(a),i##ed=(b);i<=i##ed;i++) #define per(i,a,b) for(int i=(a),i##ed=(b);i>=i##ed;i--) using namespace std; typedef long long ll; const ll mod=998244353; const int N=500010; int n,lmt,l,r[N*4]; char s[N]; ll a[N*4],b[N*4],ans=0; bool f[N];ll ksm(ll x,ll y) { ll s=1;for(;y;y/=2,x=x*x%mod) if(y%2) s=s*x%mod;return s; } void ntt(ll *A,int opt) {rep(i,0,lmt-1) if(i<r[i]) swap(A[i],A[r[i]]);for(int mid=1;mid<lmt;mid<<=1) {ll Wn=ksm(opt==1? 3:(mod+1)/3,(mod-1)/(mid<<1));for(int R=mid<<1,j=0;j<lmt;j+=R) {ll w=1;for(int k=0;k<mid;k++,w=w*Wn%mod) {ll x=A[j+k],y=w*A[j+mid+k]%mod;A[j+k]=(x+y)%mod,A[j+mid+k]=(x-y+mod)%mod;}}}if(opt==-1) {ll inv=ksm(lmt,mod-2); rep(i,0,lmt-1) A[i]=A[i]*inv%mod;} } int main() {scanf("%s",s+1),n=strlen(s+1);rep(i,1,n) {if(s[i]=='1') a[i-1]=1; else if(s[i]=='0') b[i-1]=1;}reverse(b,b+n); // rep(i,0,n-1) printf("%lld ",a[i]); puts("\n"); // rep(i,0,n-1) printf("%lld ",b[i]); puts("\n");for(lmt=1,l=0;lmt<=n+n;lmt<<=1,++l);rep(i,0,lmt-1) r[i]=(r[i>>1]>>1)|((i&1)<<(l-1));ntt(a,1),ntt(b,1);rep(i,0,lmt-1) a[i]=a[i]*b[i]%mod;ntt(a,-1); // rep(i,0,n+n-2) printf("%lld ",a[i]); puts("\n");rep(i,0,n-1) f[i]=(a[n-i-1]==0)&&(a[n+i-1]==0);per(i,n-1,1) if(f[i]) {for(int j=i+i;j<n;j+=i) if(!f[j]) { f[i]=0;break; }}rep(i,1,n) if(f[n-i]) ans^=(ll)i*i;printf("%lld\n",ans);return 0; }

轉(zhuǎn)載于:https://www.cnblogs.com/daniel14311531/p/10429025.html

總結(jié)

以上是生活随笔為你收集整理的「PKUSC2018」神仙的游戏 - 题解的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。