P1393 Mivik 的标题

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

暴力解法

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

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

$S$ 已经在 $[1, i - | S |]$ 中出现过。那么不合法的方案为 $\sum_{j = 0}^{i - | S |} f (j) \cdot m^{i - | S | - j}$ ，前缀和即可。
加入 $S$ 的一段前缀时出现了 $S$ 。那么满足该前缀是 $S$ 的一个 Border，我们利用 KMP，求出所有 Border 然后进行转移即可，不合法的方案为 $\sum_{j} f (i - | S | + j)$ 。但是因为 Border 的数量是 $O (| S |)$ 的，所有最终总的时间复杂度为 $O (n | S |)$ 。

Brute 50pts

#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 可以被划分为至多 $O (\log n)$ 个等差数列。尝试利用这一点，对于每个等差数列分别考虑，维护每个等差数列的前缀和即可。时间复杂度为 $O (n \log n)$ ，常数较小。

Code

#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 m x + 1 = F (x) + G (x) (\mod x^{n})

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

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

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

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

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