比较有趣的字符串题目。利用 Border 性质，或者用生成函数解决。
暴力解法
利用 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)$，会出现两种情况：
- $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 的数量是 $\mathcal O(|S|)$ 的，所有最终总的时间复杂度为 $\mathcal O(n|S|)$。
Brute 50pts
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
| #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)$，常数较小。
Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
| #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。考虑在不包含名字的字符串后，添加一个字符，那么接下来要么出现名字，要么还是不出现名字，得到关系：
继续考虑第二类转移，我们构造 $H(x)$ 表示 Border 长度集合构成的数列对应的 OGF。此时考虑在不包含名字的字符串后，直接添加一个名字，那么合法的字符串可以在所有 Border 所有位置结束，得到关系：
通过上面两个式子我们最终可以得到：
一次多项式求逆即可，时间复杂度为 $\mathcal O(n\log n)$。代码略。