[ABC305G] Banned Substrings
考虑到字母只有 a,b，且限制串的长度不超过 \(6\)，可以想到以当前处理到的位数、结尾的字符情况为状态动态规划。可以指记录 \(5\) 位。
处理每次添加最后一个字符，然后直接判断以新字符结尾的后缀是否出现了限制串，接着去除最高位。复杂度 \(O(n2^5)\)。
发现 \(n\) 很大，且从 \(6\) 开始，每个状态能转移到的状态就是确定的。
可以构造矩阵，使得可以转移的为 \(1\)，不能的为 \(0\)，然后单次矩阵乘法就可以往后递推一次所有 \(32\) 种状态。
使用矩阵快速幂优化即可，复杂度 \(O((2^5)^3\log n)\)。