#文本生成器加强版#

本题是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;
            }
        }
    }

最后用总数减去不成立的数量即可。