今天好像又摆了一天?
上午还就是做 jimmy 的题，顺带做了一道之前讲课讲的题，这题是真他妈牛逼啊我草???
中午很快就睡了，睡眠质量很好，睡前还窜了。
下午做 csp 和 noi online 的题，被暴打了。但是感觉星战那题确实不错，笑梗不笑题，星战真好题。
晚上有意思的来了。
先是 pjw 发了个帖子求助模拟赛的情况，本来大家在下面讨论的好好的都结帖了?然后某人直接来了一句：
真属实绷不住了啊别人结帖了问题都解决了你来这说一嘴是个什么意思啊。谁问你了啊???自以为是的小丑???，也真就跟没事找事的傻逼一样?
后面就是看他跑到洛谷群开始阴阳怪气了?，属于是洛谷上对不起来线跑别的地方开始叫了是吧?
后面被 Tibrella 骂破防了捏，这就是你谷网红的心理承受能力吗???，别顶个金钩就自以为是了?，OI 实力再强也掩盖不了你道德败坏的事实捏???
妈的，越写越气，洛谷什么时候出一个屏蔽某人发言的功能啊。
在这里放一句从 lelekue 那赫过来的话：对于事多的人，我只希望你赶紧死。
推歌：Abstruse Dilemma -Ashrount vs. 打打だいず(DD-Dice)
我草 Arcaea 公募曲包冠军！
听感很爽，谱面配置也写的感觉非常顺手。我宣布 616 全员除 Guy 都复活！
个人感觉和光追不相上下，都很神！
CF506E
我草真的神题，为什么才 3000 啊
首先为了防止记重复，我们填入字符肯定是从两边忘中间填。因此我们设 \(f[i][l][r]\) 为只考虑最终回文串的前 \(i\) 个字符和后 \(i\) 个字符，且给定字符串还有 \(s[l\sim r]\) 没有匹配时的方案数，注意，我们状态这里定义的是尽可能与 \(s\) 进行匹配。
这样做的原因是因为，假如我们在考虑 sx...ys 这个字符串时，我们首先会在 sx...ys 外面加入 s 来成为回文串，而当我们进到里面时，我们又会在 x...y 这里重新加入一次 s，这样就会让 ssx...yss 算重。因此我们要让它尽可能与 \(s\) 进行匹配。
这时我们填入的字母就有 \(k=\frac{n+|s|}{2}\)（我们先只考虑偶回文串）。
状态设出来我们就可以转移了。
- 当 \(s_l = s_r\) 时，我们的转移为：
- 当 \(s_l\not=s_r\) 时，我们的转移为：
- 而当 \(l>r\) 时，我们可以把它设为终点 \(g_i\)，而对于 \(g_i\) 来说，两边放什么字母都无所谓了。因此转移为：
我们当然可以暴力矩阵快速幂加速，复杂度为 \(O(|s|^6\log n)\)。
我们知道，dp 可以转化为在自动机上转移的过程，因此我们把自动机建出来，见下图：
图中绿色的点为 \(s_l=s_r\) 的情况，因此走自环的方案数有 \(25\) 中，红色点同理。
而我们要求的答案就是从起点出发，走到终点且路径长度为 \(k\) 的方案数。
我们发现最终走向 \(g_i\) 的点一定都是绿点（因为最终两边一定相等），那么我们就可以考虑把这个自动机优化一下状态。
我们发现绝大多数时候都是在走自环，我们就考虑自环如何插入到路径中。我们可以发现一条路径上有 \(a\) 个红点和 \(b\) 个绿点的路径和另一条有 \(a\) 个红点和 \(b\) 个绿点的路径是等价的，只需要让自环一一对应即可（这里能对应上是因为最终走到终点的一定是绿点）。因此我们总的方案数为 \(\sum F(a, b)G(a, b)\)，其中 \(F(a, b)\) 为 \(a\) 个红点和 \(b\) 个绿点的路径走 \(k\) 条边到终点的方案数，\(G(a, b)\) 为走 \(a\) 个红点和 \(b\) 个绿点的路径数。
我们首先考虑求出 \(G(a, b)\)。这个其实可以直接在自动机上跑拓扑序 dp，我们设 \(f_{l, r, a, b}\) 为在自动机上 \(\{l, r\}\) 这个节点，经过了 \(a\) 个红点和 \(b\) 个绿点时的方案数。但是复杂度为 \(O(|s|^4)\)。但是我们可以发现有了红点的数量后绿点的数量也可以直接求出来。由于每个红点会使得字符串长度减一，绿点减二，因此绿点的数量为 \(\left \lceil\frac{|s|-a}{2} \right \rceil\)。复杂度可以降到 \(O(|s|^3)\)。
我们再考虑求出 \(F(a, b)\)。一个朴素的想法就是每次求 \(F(a, b)\) 的时候就搞出来一条有 \(a\) 个红点，\(b\) 个绿点的链（我们前面已经说了是路径等价的），然后跑矩阵快速幂即可。就像下图：
但是我们发现这样要构建出来 \(O(|s|^2)\) 条链，复杂度即为 \(O(|s|^5\log n)\)。不能接受。
但是我们考虑利用矩阵快速幂能求出图中任意两点走 \(k\) 条路的方案数，我们可以把上面的图再次压缩一下：
这样构建出来图，每次只需要选取合适的起点和终点就可以获得和上面那张图一样的链和效果。
这样复杂度为 \(O(|s|^3\log n)\)。
而对于奇回文串的情况，我们发现最终 \(f_{i, l, l +1}\) 的情况不能转移到 \(g_i\)。因此我们考虑把这些方案减去即可。我们按照上面的思路，依旧是 DAG 上 dp 和矩阵快速幂即可。
