【题解】Rusty String [CF827E]

传送门：( ext{Rusty String}) ( ext{[CF827E]})

【题目描述】

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

【分析】

乍一看像是带通配符的字符串匹配（不会的强烈建议去康康这个），由于字符集不大，按照套路就应该枚举两个字符 (a e bin{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))

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

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

那么问题出在哪儿了呢？

注意：当 (PA(k) e 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(nlogn))）。

总时间复杂度为：(O(nlogn)) 。

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

( ext{emm...})

等等，还没完，仔细看题啊：“保证输入字符串总长不超过 (5∗10^5) 。” 注意是输入总长，所以不要偷懒用 ( ext{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
",ans);
        for(Re i=1;i<=n;++i)if(can[i])printf("%d ",i);puts("");
    }
}