给出M个单词,问长度为N的包含不少于K个单词的字符串一共有多少个。到目前为止做的自动机的题目好像都是差不多样子。。都是包含不包含单词之类的。。
这题用d[i][j][k]表示第i步走到字符j包含了单词集合k,因为一共只有10个单词,可以用二进制压缩状态表示这个集合。注意在建立trie图时要合并节点和它的fail节点的状态,一开始没想到这个WA了一次。状态转移方程为
不加优化的代码交上去时间接近TLE。。。于是改成了滚动数组,并用for循环清0,还是要跑360ms左右。这相对于1s的时限还是很慢的。。。于是点了下Statistic,发现大家都是跑了好几百ms。。。。
#include#include #define MAXN 105#define ALP 26#define MOD 20090717int n,m,k;char s[11];int next[MAXN][ALP],fail[MAXN],flag[MAXN],pos;int newnode(){ for(int i=0;i =MOD)x%=MOD; } } } } //统计第n步走过>=k个单词的状态的总数 int ans=0; for(int s=0;s =MOD)ans%=MOD; } } return ans;}int main(){ //freopen("test.in","r",stdin); while(scanf("%d%d%d",&n,&m,&k),n||m||k){ pos=0;newnode(); for(int i=1;i<=m;i++){ scanf("%s",s); insert(s,i); } makenext(); int ans=dp(); printf("%d\n",ans); } return 0;}