本题是JSOI2007文本生成器的加强版,在于文章的长度扩大了一百倍,因此我们需要对我们一开始的DP进行优化。
观察一下原题的DP,写成这样:
状态定义:f[i][p]
表示生成到第i位字符,位于字典的AC自动机的p位置,且不含有任意字典串作为子串的方案数
f[0][0]=1;
for(int i=0;i<m;++i){
for(int p=0;p<=AC.idx;++p){
for(int ch=0;ch<26;++ch){
int tmp=AC.tr[p][ch];
bool ok=true;
for(;tmp;tmp=AC.fail[tmp]) if(AC.cnt[tmp]) ok=false;
if(AC.cnt[AC.tr[0][ch]]) ok=false;
if(ok)
f[i+1][AC.tr[p][ch]]=(f[i+1][AC.tr[p][ch]]+f[i][p])%mod;
}
}
}
由于状态数和转移是必须要枚举的,因此我们考虑对检验p位置后一位是否可以添加ch字符进行优化。这一步可以通过预处理得到,而预处理省下的时间复杂度刚好为1e2的级别。
预处理:
for(int p=0;p<=AC.idx;++p){
for(int ch=0;ch<26;++ch){
int tmp=AC.tr[p][ch];
ok[p][ch]=true;
for(;tmp;tmp=AC.fail[tmp]) if(AC.cnt[tmp]) ok[p][ch]=false;
if(AC.cnt[AC.tr[0][ch]]) ok[p][ch]=false;
}
}
但是还有一个问题就是构造串增大一百倍,这个空间貌似有一点点吃紧。本着能省一点是一点的原则,用一个滚动数组保险一点:
f[0][0]=1;
for(int i=0;i<m;++i){
for(int p=0;p<=AC.idx;++p) f[(i+1)&1][p]=0;
for(int p=0;p<=AC.idx;++p){
for(int ch=0;ch<26;++ch){
if(ok[p][ch])
f[(i+1)&1][AC.tr[p][ch]]=(f[(i+1)&1][AC.tr[p][ch]]+f[i&1][p])%mod;
}
}
}
最后用总数减去不成立的数量即可。