首页 > 文本生成器加强版
开通博客写题解
头像 孔维飒
发表于 2022-06-21 22:20:26
文本生成器加强版 （吐槽） 感觉没有什么加强。 这个题单纯的增加m大小，而在AC自动机中的节点个数还依旧是大约6000个，所以依旧不能使用矩阵快速幂进行优化，就正常的计算即可。 同样是通过暴力枚举，进行dp出来不存在这写字符串的数的个数，然后使用总数减去。 注意AC自动机建完之后，用fail拓扑序来 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 Henry_WYH
发表于 2022-04-07 14:15:52
本题是JSOI2007文本生成器的加强版，在于文章的长度扩大了一百倍，因此我们需要对我们一开始的DP进行优化。 观察一下原题的DP，写成这样： 状态定义：f[i][p]表示生成到第i位字符，位于字典的AC自动机的p位置，且不含有任意字典串作为子串的方案数 f[0][0]=1; for(int 展开全文
去ta的博客 赞 (0) 回复(0) 收起
查看本题
查看本题讨论

等你来战

查看全部
牛客竞赛，专业的竞技算法训练平台

扫描二维码，进入QQ群

扫码关注“比赛自动姬”