用AC自动机处理所有了解的单词

显然,不能直接算,直接算的话,我们需要大力容斥,复杂度不允许

我们不妨反过来做,我们根据AC自动机处理出所有的不可行解,然后用总数减去即可

计算所有不可行解用dp,\(f[i][j]\)表示处理到字符串第i位,在自动机上第j个节点的不可行方案数,直接暴力转移即可

 


发表评论

电子邮件地址不会被公开。 必填项已用*标注