题解：P1393 Mivik 的标题

· · 题解

严肃竞选本题最魔怔做法，看完这篇题解还有手感你是这个👍

*注：代码中的状态定义可能和文字中的不同，比如 f 数组的两维相反，起始状态也有差别（代码中先做了补集转化）。

题意简述

给定一个字符串 S，求有多少个长为 n、字符集为 1\sim m 的字符串 T，满足 S 是 T 的子串。

答案乘以 m^{-n}，再对 998244353 取膜。

解题思路

Subtask 2

看到至少包含一个首先想到可以先钦定再反演，于是定义 f_{i,j} 表示钦定长度为 i 的 T 中出现了 j 次 S 且 S 是 T 的后缀，其余任意的方案。转移的话考虑枚举新的 S 接上去，由于当前的 T 末尾是一段 S，枚举 border 即可，令

B=\{nxt_n,nxt_{nxt_n},\cdots\}\left(0\notin B\right)

则转移为

f_{i,j}=\sum_{k=0}^{i-|S|} m^kf_{i-|S|-k,j-1}+\sum_{b\in B} f_{i-|S|+b,j-1}

初始状态 f_{i,1}=m^{i-|S|} (i\ge|S|)，然后反演一下就是答案，时间复杂度 \mathcal O(n^3)。

::::info[代码]

#include<bits/stdc++.h>
// #define int long long
using namespace std;
// #define LOCAL
namespace IO{
    char *p1,*p2,*p3,buf[100000],buf2[100000];
    #ifndef LOCAL
        #define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++)
        #define flush() (fwrite(buf2,1,p3-buf2,stdout),p3=buf2)
        #define putchar(ch) (p3==buf2+100000&&flush(),*p3++=(ch))
        struct Manager{
            Manager(){p3=buf2;}
            ~Manager(){flush();}
        }_;
    #endif
    template<typename T>
    inline void read(T &x){
        int f=1,ch=getchar();x=0;
        while(ch!=EOF&&!isdigit(ch)){
            if(ch=='-') f=-f;
            ch=getchar();
        }
        while(isdigit(ch)){
            x=(x<<3)+(x<<1)+ch-'0';
            ch=getchar();
        }
        x*=f;
    }
    inline void read(char &ch){
        ch=getchar();
    }
    inline void read(char* s){
        int ch=getchar();
        while(ch!=EOF&&isspace(ch)) ch=getchar();
        while(ch!=EOF&&!isspace(ch)){
            *s++=(char)ch;
            ch=getchar();
        }
        *s='\0';
    }
    template<typename T>
    inline void write(T x){
        if(x<0) putchar('-'),x=-x;
        if(x>9) write(x/10);
        putchar(x%10+'0');
    }
    inline void write(char ch){
        putchar(ch);
    }
    inline void write(const char* s){
        while(*s) putchar(*s++);
    }
    inline void write(char* s){
        while(*s) putchar(*s++);
    }
    template<typename T>
    inline void writeln(T x){
        write(x),putchar('\n');
    }
    template<typename T,typename... Args>
    inline void read(T &&x,Args&&... args){
        read(x),read(std::forward<Args>(args)...);
    }
    template<typename T,typename... Args>
    inline void write(T x,Args... args){
        write(x),putchar(' '),write(args...);
    }
    template<typename T,typename... Args>
    inline void writeln(T x,Args... args){
        write(x),putchar(' '),writeln(args...);
    }
}using namespace IO;
constexpr int N=5005,Mod=998244353;
int m,c,Ic,n,ans,s[N],nxt[N],pw[N],Ipw[N],g[N],fac[N],Inv[N],Ifac[N],f[N][N];
inline int Pow(int a,int b){
    int res=1;
    while(b){
        if(b&1) res=res*1ll*a%Mod;
        a=a*1ll*a%Mod;
        b>>=1;
    }
    return res;
}
inline int C(int n,int m){
    if(n<0||m<0||n<m) return 0;
    return fac[n]*1ll*Ifac[m]%Mod*Ifac[n-m]%Mod;
}
signed main(){
    // freopen(".in","r",stdin);
    // freopen(".out","w",stdout);
    read(m,c,n);
    Ic=Pow(c,Mod-2);
    for(int i=1;i<=n;i++){
        read(s[i]);
    }
    pw[0]=Ipw[0]=fac[0]=Ifac[0]=Inv[1]=1;
    for(int i=1;i<=m;i++){
        if(i>1) Inv[i]=(Mod-Mod/i)*1ll*Inv[Mod%i]%Mod;
        Ifac[i]=Ifac[i-1]*1ll*Inv[i]%Mod;
        fac[i]=fac[i-1]*1ll*i%Mod;
        Ipw[i]=Ipw[i-1]*1ll*Ic%Mod;
        pw[i]=pw[i-1]*1ll*c%Mod;
    }
    for(int i=2,j=0;i<=n;i++){
        while(j&&s[i]!=s[j+1]) j=nxt[j];
        if(s[i]==s[j+1]) ++j;
        nxt[i]=j;
    }
    f[1][0]=(Mod-1)*1ll*pw[m-n]%Mod;
    for(int i=1;i<m;i++){
        for(int j=0;j<=m;j++){
            (f[i][j]+=(Mod-f[i-1][j])*1ll*Ipw[n]%Mod)%=Mod;
            for(int k=nxt[n];k&&j-n+k>=0;k=nxt[k]){
                (f[i][j]+=(Mod-f[i][j-n+k])%Mod*1ll*Ipw[n-k]%Mod)%=Mod;
            }
        }
    }
    ans=pw[m];
    for(int i=1;i<=m;i++){
        for(int j=0;j<=m-i*n;j++){
            ans=(ans+f[i][j]*1ll*C(m-j+i*(1-n),i)%Mod)%Mod;
        }
    }
    write((1+Mod-ans*1ll*Ipw[m]%Mod)%Mod);
}

::::

Subtask 3

考虑套路地将反演的系数、其余随意排列的贡献融合到转移中，此时不再需要统计 S 的次数，将第二维 j 改为形成的极长 S 连续段的个数（要求重叠），第一维 i 改为连续段总长度减去 |S|j，此时转移为

f_{i,j}=-\frac{1}{m^{|S|}}f_{i,j-1}-\sum_{b\in B}\frac{1}{m^{|S|-b}}f_{i-|S|+b,j}

初始状态为 f_{0,1}=m^{n-|S|}，答案为

ans=\sum_{i,j}\binom{n-i+(1-|S|)j}{j}f_{i,j}

此时时间复杂度还是 \mathcal O(n^3)，似乎想要优化就只能从枚举 border 的转移开始，发现每次转移都是固定的，是否可以用生成函数之类的东西来刻画转移呢？

显然是可以的，定义

F(x,y)=\sum_{i,j}f_{i,j}x^iy^j

则有

F=-\frac{1}{m^{|S|}}yF-\sum_{b\in B}\frac{1}{m^{|S|-b}}x^{|S|-b}F+m^{n-|S|}y

令

A(x)=1+\sum_{b\in B}\frac{1}{m^{|S|-b}}x^{|S|-b}

可以解得

F=\frac{m^{n-|S|}y}{A(x)+\frac{1}{m^{|S|}}y}

答案呢？注意到 f 前面的系数

\binom{n-i+(1-|S|)j}{j}=[z^{n-i-|S|j}]\frac{1}{(1-z)^{j+1}}=[z^n]\frac{z^{i+|S|j}}{(1-z)^{j+1}}

带回求 ans 的式子可得

\begin{aligned} ans&=\sum_{i,j}\binom{n-i+(1-|S|)j}{j}f_{i,j}\\ &=[z^n]\sum_{i,j}f_{i,j}\frac{z^{i+|S|j}}{(1-z)^{j+1}}\\ &=[z^n]\sum_{i,j}\frac{1}{1-z}f_{i,j}\left(\frac{z^{|S|}}{1-z}\right)^jz^{i}\\ &=[z^n]\frac{1}{1-z}F\left(z,\frac{z^{|S|}}{1-z}\right) \end{aligned}

展开一下 F 的部分

\begin{aligned} F\left(z,\frac{z^{|S|}}{1-z}\right)&=\frac{m^{n-|S|}\frac{z^{|S|}}{1-z}}{A(z)+\frac{1}{m^{|S|}}\frac{z^{|S|}}{1-z}}\\ &=\frac{m^{n-|S|}z^{|S|}}{(1-z)A(z)+\frac{1}{m^{|S|}}z^{|S|}} \end{aligned}

令 D(z)=(1-z)A(z)+\frac{1}{m^{|S|}}z^{|S|}，再带回 ans 中，则

ans=m^{n-|S|}[z^{n-|S|}]\frac{1}{(1-z)D(z)}

然后显然 \frac{1}{1-z}=\sum_{i=0}^\infty x^i，因此

ans=m^{n-|S|}\sum_{i=0}^{n-|S|}[z^i]\frac{1}{D(z)}

然后 D(z) 显然是好求的，这时候多项式大佬就会直接掏出多项式求逆的板子秒了这道题，但是我不会，怎么办呢？此时你看了看小标题，发现这里是 Subtask3，支持 \mathcal O(n^2)，于是考虑递推。

令

\frac{1}{D(z)}=\sum_{i=0}^\infty d_iz^i

对比 D(z)\cdot \frac{1}{D(z)}=1 的左右系数，得到

[z^i]D(z)\cdot \frac{1}{D(z)}=[i=0]

定义 B'=\{|S|-b\mid b\in B\}，并将 D(z) 展开

\begin{aligned} [i=0]&=[z^i]D(z)\cdot \frac{1}{D(z)}\\ &=[z^i]\left((1-z)A(z)+\frac{1}{m^{|S|}}z^{|S|}\right)\left(\sum_{i=0}^\infty d_iz^i\right)\\ &=[z^i]\left((1-z)\left(1+\sum_{b\in B'}\frac{1}{m^{b}}z^{b}\right)+\frac{1}{m^{|S|}}z^{|S|}\right)\left(\sum_{i=0}^\infty d_iz^i\right)\\ &=[z^i]\left(1-z+\sum_{b\in B'}\frac{1}{m^{b}}(z^{b}-z^{b+1})+\frac{1}{m^{|S|}}z^{|S|}\right)\left(\sum_{i=0}^\infty d_iz^i\right)\\ &=d_i-d_{i-1}+\sum_{b\in B'}\frac{1}{m^{b}}(d_{i-b}-d_{i-b-1})+\frac{1}{m^{|S|}}d_{i-|S|}\\ \end{aligned}

然后移个项

d_i=[i=0]+d_{i-1}-\sum_{b\in B'}\frac{1}{m^{b}}(d_{i-b}-d_{i-b-1})-\frac{1}{m^{|S|}}d_{i-|S|}

从 d_0=1 开始递推，d 的负数下标视作 0 即可，复杂度 \mathcal O(n^2)。

::::info[代码]

#include<bits/stdc++.h>
// #define int long long
using namespace std;
// #define LOCAL
namespace IO{
    char *p1,*p2,*p3,buf[100000],buf2[100000];
    #ifndef LOCAL
        #define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++)
        #define flush() (fwrite(buf2,1,p3-buf2,stdout),p3=buf2)
        #define putchar(ch) (p3==buf2+100000&&flush(),*p3++=(ch))
        struct Manager{
            Manager(){p3=buf2;}
            ~Manager(){flush();}
        }_;
    #endif
    template<typename T>
    inline void read(T &x){
        int f=1,ch=getchar();x=0;
        while(ch!=EOF&&!isdigit(ch)){
            if(ch=='-') f=-f;
            ch=getchar();
        }
        while(isdigit(ch)){
            x=(x<<3)+(x<<1)+ch-'0';
            ch=getchar();
        }
        x*=f;
    }
    inline void read(char &ch){
        ch=getchar();
    }
    inline void read(char* s){
        int ch=getchar();
        while(ch!=EOF&&isspace(ch)) ch=getchar();
        while(ch!=EOF&&!isspace(ch)){
            *s++=(char)ch;
            ch=getchar();
        }
        *s='\0';
    }
    template<typename T>
    inline void write(T x){
        if(x<0) putchar('-'),x=-x;
        if(x>9) write(x/10);
        putchar(x%10+'0');
    }
    inline void write(char ch){
        putchar(ch);
    }
    inline void write(const char* s){
        while(*s) putchar(*s++);
    }
    inline void write(char* s){
        while(*s) putchar(*s++);
    }
    template<typename T>
    inline void writeln(T x){
        write(x),putchar('\n');
    }
    template<typename T,typename... Args>
    inline void read(T &&x,Args&&... args){
        read(x),read(std::forward<Args>(args)...);
    }
    template<typename T,typename... Args>
    inline void write(T x,Args... args){
        write(x),putchar(' '),write(args...);
    }
    template<typename T,typename... Args>
    inline void writeln(T x,Args... args){
        write(x),putchar(' '),writeln(args...);
    }
}using namespace IO;
constexpr int N=10005,Mod=998244353;
int m,c,Ic,n,ans,s[N],d[N],nxt[N],pw[N],Ipw[N],g[N],fac[N],Inv[N],Ifac[N];
inline int Pow(int a,int b){
    int res=1;
    while(b){
        if(b&1) res=res*1ll*a%Mod;
        a=a*1ll*a%Mod;
        b>>=1;
    }
    return res;
}
inline int C(int n,int m){
    if(n<0||m<0||n<m) return 0;
    return fac[n]*1ll*Ifac[m]%Mod*Ifac[n-m]%Mod;
}
signed main(){
    // freopen(".in","r",stdin);
    // freopen(".out","w",stdout);
    read(m,c,n);
    Ic=Pow(c,Mod-2);
    for(int i=1;i<=n;i++){
        read(s[i]);
    }
    pw[0]=Ipw[0]=fac[0]=Ifac[0]=Inv[1]=1;
    for(int i=1;i<=m;i++){
        if(i>1) Inv[i]=(Mod-Mod/i)*1ll*Inv[Mod%i]%Mod;
        Ifac[i]=Ifac[i-1]*1ll*Inv[i]%Mod;
        fac[i]=fac[i-1]*1ll*i%Mod;
        Ipw[i]=Ipw[i-1]*1ll*Ic%Mod;
        pw[i]=pw[i-1]*1ll*c%Mod;
    }
    for(int i=2,j=0;i<=n;i++){
        while(j&&s[i]!=s[j+1]) j=nxt[j];
        if(s[i]==s[j+1]) ++j;
        nxt[i]=j;
    }
    ans=d[0]=1;
    for(int i=1;i<=m-n;i++){
        d[i]=d[i-1];
        for(int j=nxt[n];j;j=nxt[j]){
            int k=n-j;
            d[i]=(d[i]+Mod-((i-k>=0?d[i-k]:0)+Mod-(i-k-1>=0?d[i-k-1]:0))%Mod*1ll*Ipw[k]%Mod)%Mod;
        }
        if(i>=n){
            d[i]=(d[i]+Mod-Ipw[n]*1ll*d[i-n]%Mod)%Mod;
        }
        ans=(ans+d[i])%Mod;
    }
    write(ans%Mod*1ll*Ipw[n]%Mod);
}

::::

Subtask 4（满分）

还有第三关？？？

常规的优化似乎已经到了尽头，我们需要发掘一些新性质，通过翻阅题解可得，B 可以被划分为 \log|S| 个等差数列，这似乎是一个很强的性质，考虑优化刚刚的递推。

递推的瓶颈在于枚举 b，将这一部分单独拿出来，令

K_i=\sum_{b\in B'}\frac{1}{m^{b}}(d_{i-b}-d_{i-b-1})

设 B' 被划分为 s 个等差数列，第 i 个的小值为 min_i，公差为 step_i，长度为 len_i，pos_{i,j}=min_i+j\cdot step_i，则

K_p=\sum_{i=1}^s\sum_{j=0}^{len_i-1}\frac{1}{m^{pos_{i,j}}}(d_{p-pos_{i,j}}-d_{p-1-pos_{i,j}})

将第二个求和表述成关于 p 的 s 个函数，令

G_i(p)=\sum_{j=0}^{len_i-1}\frac{1}{m^{pos_{i,j}}}d_{p-pos_{i,j}}

则 K_p=\sum_{i=1}^s(G_i(p)-G_i(p-1))，考虑递推地求 G_i

\begin{aligned} G_i(p)&=\sum_{j=0}^{len_i-1}\frac{1}{m^{pos_{i,j}}}d_{p-pos_{i,j}}\\ &=\frac{d_{p-min_i}}{m^{min_i}}+\sum_{j=1}^{len_i-1}\frac{1}{m^{pos_{i,j}}}d_{p-pos_{i,j}}\\ &=\frac{d_{p-min_i}}{m^{min_i}}+\sum_{j=0}^{len_i-2}\frac{1}{m^{pos_{i,j}+step_i}}d_{p-pos_{i,j}-step_i}\\ &=\frac{d_{p-min_i}}{m^{min_i}}+\frac{1}{m^{step_i}}\sum_{j=0}^{len_i-2}\frac{1}{m^{pos_{i,j}}}d_{p-pos_{i,j}-step_i}\\ &=\frac{d_{p-min_i}}{m^{min_i}}+\frac{1}{m^{step_i}}G_i(p-step_i)-\frac{1}{m^{pos_i,len_i}}d_{p-pos_{i,len_i}}\\ \end{aligned}

于是这道题就做完了，复杂度 \mathcal O(n\log|S|)。

::::info[代码]

#include<bits/stdc++.h>
// #define int long long
using namespace std;
// #define LOCAL
namespace IO{
    char *p1,*p2,*p3,buf[100000],buf2[100000];
    #ifndef LOCAL
        #define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++)
        #define flush() (fwrite(buf2,1,p3-buf2,stdout),p3=buf2)
        #define putchar(ch) (p3==buf2+100000&&flush(),*p3++=(ch))
        struct Manager{
            Manager(){p3=buf2;}
            ~Manager(){flush();}
        }_;
    #endif
    template<typename T>
    inline void read(T &x){
        int f=1,ch=getchar();x=0;
        while(ch!=EOF&&!isdigit(ch)){
            if(ch=='-') f=-f;
            ch=getchar();
        }
        while(isdigit(ch)){
            x=(x<<3)+(x<<1)+ch-'0';
            ch=getchar();
        }
        x*=f;
    }
    inline void read(char &ch){
        ch=getchar();
    }
    inline void read(char* s){
        int ch=getchar();
        while(ch!=EOF&&isspace(ch)) ch=getchar();
        while(ch!=EOF&&!isspace(ch)){
            *s++=(char)ch;
            ch=getchar();
        }
        *s='\0';
    }
    template<typename T>
    inline void write(T x){
        if(x<0) putchar('-'),x=-x;
        if(x>9) write(x/10);
        putchar(x%10+'0');
    }
    inline void write(char ch){
        putchar(ch);
    }
    inline void write(const char* s){
        while(*s) putchar(*s++);
    }
    inline void write(char* s){
        while(*s) putchar(*s++);
    }
    template<typename T>
    inline void writeln(T x){
        write(x),putchar('\n');
    }
    template<typename T,typename... Args>
    inline void read(T &&x,Args&&... args){
        read(x),read(std::forward<Args>(args)...);
    }
    template<typename T,typename... Args>
    inline void write(T x,Args... args){
        write(x),putchar(' '),write(args...);
    }
    template<typename T,typename... Args>
    inline void writeln(T x,Args... args){
        write(x),putchar(' '),writeln(args...);
    }
}using namespace IO;
constexpr int N=200005,lN=30,Mod=998244353;
int m,c,Ic,n,ans,s[N],d[N],nxt[N],pw[N],Ipw[N],g[N],fac[N],Inv[N],Ifac[N];
int tot,bgn[lN],stp[lN],len[lN],S[lN][N];
inline int Pow(int a,int b){
    int res=1;
    while(b){
        if(b&1) res=res*1ll*a%Mod;
        a=a*1ll*a%Mod;
        b>>=1;
    }
    return res;
}
inline int C(int n,int m){
    if(n<0||m<0||n<m) return 0;
    return fac[n]*1ll*Ifac[m]%Mod*Ifac[n-m]%Mod;
}
signed main(){
    // freopen(".in","r",stdin);
    // freopen(".out","w",stdout);
    read(m,c,n);
    Ic=Pow(c,Mod-2);
    for(int i=1;i<=n;i++){
        read(s[i]);
    }
    pw[0]=Ipw[0]=fac[0]=Ifac[0]=Inv[1]=1;
    for(int i=1;i<=m;i++){
        if(i>1) Inv[i]=(Mod-Mod/i)*1ll*Inv[Mod%i]%Mod;
        Ifac[i]=Ifac[i-1]*1ll*Inv[i]%Mod;
        fac[i]=fac[i-1]*1ll*i%Mod;
        Ipw[i]=Ipw[i-1]*1ll*Ic%Mod;
        pw[i]=pw[i-1]*1ll*c%Mod;
    }
    for(int i=2,j=0;i<=n;i++){
        while(j&&s[i]!=s[j+1]) j=nxt[j];
        if(s[i]==s[j+1]) ++j;
        nxt[i]=j;
    }
    for(int i=nxt[n];i;i=nxt[i]){
        stp[++tot]=i-nxt[i],bgn[tot]=n-i,len[tot]=1;
        while(nxt[i]&&i-nxt[i]==stp[tot]){
            ++len[tot];
            i=nxt[i];
        }
    }
    ans=d[0]=1;
    for(int i=1;i<=m-n;i++){
        d[i]=d[i-1];
        for(int j=1;j<=tot;j++){
            if(i>=bgn[j]){
                S[j][i]=d[i-bgn[j]]*1ll*Ipw[bgn[j]]%Mod;
                if(i>=stp[j]){
                    S[j][i]=(S[j][i]+S[j][i-stp[j]]*1ll*Ipw[stp[j]]%Mod)%Mod;
                }
                if(i>=bgn[j]+len[j]*stp[j]){
                    S[j][i]=(S[j][i]+Mod-d[i-bgn[j]-len[j]*stp[j]]*1ll*Ipw[bgn[j]+len[j]*stp[j]]%Mod)%Mod;
                }
            }
            d[i]=(d[i]+Mod-(S[j][i]+Mod-S[j][i-1])%Mod)%Mod;
        }
        if(i>=n){
            d[i]=(d[i]+Mod-Ipw[n]*1ll*d[i-n]%Mod)%Mod;
        }
        ans=(ans+d[i])%Mod;
    }
    write(ans%Mod*1ll*Ipw[n]%Mod);
}

::::