4861: [Beijing2017]魔法咒语

首先有不能含某个子串,那么容易发现使用ac自动机解决

对于前60%数据:

令f[i,j]表示构造到了第i个位置,目前位于ac自动机的第j个节点上。

有f[i+len[v]][to] += f[i][j]

那么很容易解决掉了这部分数据。

对于后40%数据:

因为考虑到len小于等于2,那么就是个类似fib的递归式。不过f是个矩阵。

实际上发现把矩阵直接写进去 是等价的,那么一个矩阵快速幂就可以了...

c++ 代码如下:

 

3 + 3 =