题解 CF827E 【Rusty String】

· · 题解

【题解】Rusty String [CF827E]

\mathcal{My}\ \mathcal{Blog}

传送门：\text{Rusty String} \text{[CF827E]}

【题目描述】

多组数据，每组数据给出一个由 V,K,? 三种字符组成的字符串，其中 ? 可以替换为 V,K 中的任意一个，求替换后的字符串可以存在的循环周期有哪些。

【分析】

乍一看像是带通配符的字符串匹配（不会的强烈建议去康康这个），由于字符集不大，按照套路就应该枚举两个字符 a \ne b\in\{V,K\}，然后设 f(i)=[A[i]=a], g(i)=[A[i]=b]

则有： PA(k)=\sum_{i=1}^{n}f(i)g(i+k)，翻转 f 得到：PA(k)=\sum_{i=1}^{n}f(n-i+1)g(i+k) =\sum_{i+j=n+k+1}f(i)g(j)

很明显是个 \text{FFT} 的板子，把式子卷起来就可以了。

按照以往的“经验”，或者说惯性思维，多半会这样做（比如说我），但写出来却发现酱紫连第一个样例都过不了。

那么问题出在哪儿了呢？

注意：当 PA(k) \ne 0 时说明在某个地方出现了 'V' 与 'K' 相对应的情况，以 k 作为周期肯定不合法，但 PA(k) = 0 并不能说明 k 一定是合法周期，因为这道题中的特殊符号不是通配符，而是未知字符，通配符可以任意匹配，但未知字符只能匹配一种。

比如样例 1，用上面的错误算法多输出了一个 2，在这种情况下 S_3('?') 分别与 S_1('V'),S_5('K') 进行了匹配，因此以 2 作为周期是不合法的。

考虑改进算法：

之前的做法错在算出来的式子只进行了一周目的匹配判断，那么我们只要将二周目、三周目……全部都判断一下就好了呀，正巧序列 PA 完美的包含了所有长度的循环情况，所以直接暴力枚举周期的倍数即可（复杂度为 O(\frac{n}{1}+\frac{n}{2}+\frac{n}{3} \cdots \frac{n}{n})=O(n\ln n)）。

总时间复杂度为：O(n\log n) 。

你说啥？卡常？玄学优化减少调用次数？不存在的，我写了这么久的 \text{NTT}，还从未被卡过（小骄傲）。

\text{emm...}

等等，还没完，仔细看题啊：“保证输入字符串总长不超过500000 。” 注意是输入总长，所以不要偷懒用 \text{memset}！

【Code】

#include<algorithm>
#include<cstring>
#include<cstdio>
#define LL long long
#define Re register int
using namespace std;
const int N=1048576+3,P=998244353,G=3;
int n,T,ans,invG,f[N],g[N],tr[N],PA[N],can[N];char A[N];
inline void in(Re &x){
    int f=0;x=0;char c=getchar();
    while(c<'0'||c>'9')f|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=f?-x:x;
}
inline int mi(Re x,Re k){
    Re s=1;
    while(k){
        if(k&1)s=(LL)s*x%P;
        x=(LL)x*x%P,k>>=1;
    }
    return s;
}
inline int inv(Re x){return mi(x,P-2);}
inline void NTT(Re *f,Re n,Re op){
    for(Re i=0;i<n;++i)if(i<tr[i])swap(f[i],f[tr[i]]);
    for(Re p=2;p<=n;p<<=1){
        Re len=p>>1,w1=mi(op?invG:G,(P-1)/p);
        for(Re st=0;st<n;st+=p)
            for(Re j=st,base=1;j<=st+len-1;++j){
                Re tmp=(LL)base*f[j+len]%P;
                f[j+len]=(f[j]-tmp+P)%P,(f[j]+=tmp)%=P;
                base=(LL)base*w1%P;
            }
    }
}
inline void sakura(Re *f,Re n,Re *g,Re m){//卷卷卷
    Re n_=n;
    for(m+=n,n=1;n<=m;n<<=1);Re invn=inv(n);
    for(Re i=n_+1;i<=n;++i)f[i]=g[i]=0;//注意初始化
    for(Re i=1;i<n;++i)tr[i]=(tr[i>>1]>>1)|((i&1)?n>>1:0);
    NTT(f,n,0),NTT(g,n,0);
    for(Re i=0;i<n;++i)f[i]=(LL)f[i]*g[i]%P;
    NTT(f,n,1);
    for(Re i=0;i<=m;++i)f[i]=(LL)f[i]*invn%P;
}
int main(){
//    freopen("123.txt","r",stdin);
    in(T),invG=inv(G);
    while(T--){
        in(n),scanf("%s",A+1),ans=0;
        for(Re i=1;i<=n;++i)PA[i]=0;//注意初始化
        for(Re i=1;i<=n;++i)f[n-i+1]=(A[i]=='K'),g[i]=(A[i]=='V');
        sakura(f,n,g,n);
        for(Re i=1;i<n;++i)PA[i]+=f[i+n+1];//PA[n]可以不用管，因为一定合法
        for(Re i=1;i<=n;++i)f[n-i+1]=(A[i]=='V'),g[i]=(A[i]=='K');
        sakura(f,n,g,n);
        for(Re i=1;i<n;++i)PA[i]+=f[i+n+1];
        for(Re i=1;i<=n;++i){
            can[i]=1;
            for(Re j=i;j<=n&&can[i];j+=i)can[i]&=(!PA[j]);//枚举倍数依次判断
            ans+=can[i];
        }
        printf("%d\n",ans);
        for(Re i=1;i<=n;++i)if(can[i])printf("%d ",i);puts("");
    }
}

最后还是忍不住吐槽一下，这题不至于黑吧，顶多紫。