P1393 Mivik 的标题

· · 题解

比较有趣的字符串题目。利用 Border Theory 性质优化，或者用生成函数解决。

暴力解法

利用 P3193 [HNOI2008] GT考试 类似的方法，设计 f(i,j) 表示考虑前 i 位，当前已匹配 j 位。转移矩阵容易通过 KMP 求出，这样是 \mathcal O(n|S|^2)，加上矩阵快速幂优化可以做到 \mathcal O(|S|^3\log n)。这样显然不够优。

我们直接记录 f(i) 表示 字符串恰好在 [i-|S|+1,i] 出现一次。最终答案为 \sum_{i=|S|}^n f(i)\cdot m^{n-i}。考虑求 f(i)，会出现两种情况：

  2. 加入 S 的一段前缀时出现了 S。那么满足该前缀是 S 的一个 Border，我们利用 KMP，求出所有 Border 然后进行转移即可，不合法的方案为 \sum_j f(i-|S|+j)。但是因为 Border 的数量是 \mathcal O(|S|) 的，所有最终总的时间复杂度为 \mathcal O(n|S|)。
#include<iostream>
#include<cstdio>
using namespace std;
const int N=5e5+10,mod=998244353;
template<class T>
inline void read(T &x)
{
    x=0;bool f=0;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=1;ch=getchar();}
    while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    if(f)x=~x+1;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1)
{
    read(x),read(x1...);
}
int n,m,c;
int s[N];
int ne[N];
int f[N];
inline void adj(int &x){x+=x>>31&mod;}
inline int qpow(int x,int k=mod-2)
{
    int res=1;
    while(k)
    {
        if(k&1)res=1ll*res*x%mod;
        x=1ll*x*x%mod;
        k>>=1;
    }
    return res;
}
int main()
{
    read(m,c,n);
    for(int i=1;i<=n;i++)read(s[i]);
    for(int i=2,j=0;i<=n;i++)
    {
        while(j&&s[i]!=s[j+1])j=ne[j];
        if(s[i]==s[j+1])j++;
        ne[i]=j;
    }
    for(int i=n,res=0,mul=1;i<=m;i++,mul=1ll*mul*c%mod)
    {
        adj(res=1ll*res*c%mod-f[i-n]),adj(f[i]=res+mul-mod);
        for(int j=ne[n];j;j=ne[j])adj(f[i]-=f[i-n+j]);
    }
    int ans=0;
    for(int i=m,mul=1;i>=n;i--,mul=1ll*mul*c%mod)
        adj(ans+=1ll*mul*f[i]%mod-mod);
    printf("%d\n",1ll*ans*qpow(qpow(c,m))%mod);
    return 0;
}

解法一

尝试运用 Border Theory 对暴力进行优化。S 所有的 Border 可以被划分为至多 \mathcal O(\log n) 个等差数列。尝试利用这一点，对于每个等差数列分别考虑，维护每个等差数列的前缀和即可。时间复杂度为 \mathcal O(n\log n)，常数较小。

#include<iostream>
#include<cstdio>
using namespace std;
const int N=2e5+10,K=19,mod=998244353;
template<class T>
inline void read(T &x)
{
    x=0;bool f=0;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=1;ch=getchar();}
    while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    if(f)x=~x+1;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1)
{
    read(x),read(x1...);
}
int n,m,c;
int s[N];
int ne[N];
int tot,l[K],r[K],d[K];
int f[N],g[N][K];
inline void adj(int &x){x+=x>>31&mod;}
inline int qpow(int x,int k=mod-2)
{
    int res=1;
    while(k)
    {
        if(k&1)res=1ll*res*x%mod;
        x=1ll*x*x%mod;
        k>>=1;
    }
    return res;
}
int main()
{
    read(m,c,n);
    for(int i=1;i<=n;i++)read(s[i]);
    for(int i=2,j=0;i<=n;i++)
    {
        while(j&&s[i]!=s[j+1])j=ne[j];
        if(s[i]==s[j+1])j++;
        ne[i]=j;
    }
    for(int i=ne[n];i;i=ne[i])
    {
        d[++tot]=i-ne[i],r[tot]=n-i;
        while(ne[i]&&i-ne[i]==d[tot])i=ne[i];
        l[tot]=n-i;
    }
    for(int i=n,res=0,mul=1;i<=m;i++,mul=1ll*mul*c%mod)
    {
        adj(res=1ll*res*c%mod-f[i-n]),adj(f[i]=res+mul-mod);
        for(int j=1;j<=tot;j++)
        {
            if(i>=l[j]+d[j])adj(f[i]+=g[i-l[j]-d[j]][j]-mod);
            adj(f[i]-=g[i-r[j]][j]);
        }
        for(int j=1;j<=tot;j++)adj(g[i][j]=g[i-d[j]][j]+f[i]-mod);
    }
    int ans=0;
    for(int i=m,mul=1;i>=n;i--,mul=1ll*mul*c%mod)
        adj(ans+=1ll*mul*f[i]%mod-mod);
    printf("%d\n",1ll*ans*qpow(qpow(c,m))%mod);
    return 0;
}

解法二

考虑第二类转移，非常的像分治 FFT，我们似乎可以直接这样求解，但是这样并不优美。所以还是利用生成函数把基本关系列出来。设 g(i) 表示长度为 i 的不包含名字的字符串方案数，F(x) 为 f(i) 的 OGF，G(x) 为 g(i) 的 OGF。考虑在不包含名字的字符串后，添加一个字符，那么接下来要么出现名字，要么还是不出现名字，得到关系：

G(x)\cdot mx+1=F(x)+G(x)\pmod {x^n}

继续考虑第二类转移，我们构造 H(x) 表示 Border 长度集合构成的数列对应的 OGF。此时考虑在不包含名字的字符串后，直接添加一个名字，那么合法的字符串可以在所有 Border 所有位置结束，得到关系：

G(x)\cdot x^{|S|}=F(x)H(x)\pmod{x^n}

通过上面两个式子我们最终可以得到：

F(x)=\frac{x^{|S|}}{x^{|S|}+(1-mx)\cdot H(x)}

一次多项式求逆即可，时间复杂度为 \mathcal O(n\log n)。代码略。