太神了，感觉比任何一道我做过的 *3000 都难啊！
首先考虑一个很蠢的 dp，大概设 \(f_{k,i,j}\) 表示从前往后定了字符串的前 \(k\) 位，同时也定了后 \(k\) 位，在原串上从前往后匹配到 \(i\)，从后往前匹配到 \(j\) 的方案数，直接硬上矩乘是 \(O(|s|^6\log n)\) 的。/fad
肯定要找一点性质优化，一个观察是有用的步数只有 \(O(|s|)\) 步，其它都在走自环，不过不太能用。另一个性质就是只有两种本质不同的转移：\(s_i=s_j\) 和 \(s_i\not=s_j\)。
然后就不会了，就去瞄了眼题解，发现是把这个 dp 看成一个自动机转移，很厉害啊！先鸣谢xht然后抠张图：
其中红点代表 \(s_i\not=s_j\)，绿点代表 \(s_i=s_j\)。
有了这个自动机我们能干什么呢？大概看一看就可以发现，每条路径对答案的贡献只和绿点的个数以及红点的个数有关，而红点的个数与两倍绿点的个数之和只能是 \(|s|\) 或者 \(|s|+1\)，也就是说我们只有 \(O(|s|)\) 种本质不同的路径。因此我们可以先跑一个 \(O(|s|^3)\) 的 dp 把每种路径的条数算出来，然后如果我们对每种路径矩乘可以做到 \(O(|s|^4\log n)\)。
但是这还不够，还不够怎么办？并行！我们尝试用一次矩乘并行这 \(O(|s|)\) 种不同的路径。我们规定绿点先转移，红点后转移，那么设 \(f_i\) 表示绿点走了 \(i\) 个，设 \(g_i\) 表示红点还剩 \(i\) 个，则 \(f,g\) 之间可以通过预处理的路径条数转移，直接矩乘就行，可以做到 \(O(|s|^3\log n)\)。
实际上仍然使用自动机会更好理解，先鸣谢 xht，再抠张图：
上面是没有压缩过的，对 \(O(|s|)\) 条链分开跑的，下面是压缩以后的自动机。
你写完高高兴兴一测样例二发现挂掉了，原因是奇数长度中间那个位置会同时跳两个，这是不行的，减去就行。
这个自动机挺特殊的应该可以去矩乘，大概可以做到 \(O(|s|^3)\) 但是纯口胡没写过。
标签：矩乘,Gift,绿点,路径,CF506E,Kitayuta,自动机,dp,log From： https://www.cnblogs.com/275307894a/p/17415330.html