CF506E
首先 \(nl^2\) 的 dp。
我们可以记录状态 \(\mathrm{dp[k][l][r]}\),表示当前加入了 \(k\) 个数，前缀匹配到 \(l\),后缀匹配到了 \(r\)。
update at 10-27
很抱歉我真的不知道这个从头到尾的想法是如何得到的。
我只能得到一个丑陋无比的DP，复杂看不出逻辑的自动机，以及无穷无尽的口胡。
大体思路是这样的，我们建出来dp的转移自动机。、
我们直接暴力做会带 \(n\) 的，但是这并不是很值得，因为我们实际上有很多无用的匹配。
我们更换视角，考虑在 自动机上转移，然后求从 \(1\) 到 \(t\) 走 \(n\) 步的方案数。
有效果的匹配只有 \(n\) 种，这体现在自动机的转移边上。
剩下的就是走的自环，发现自环的贡献依然会有两种，24&25。
再次发现实际上 我们一条刨除自环的路径，所产生的权值只和24,25权点个数有关。
所以答案写成 \[ \sum_{a,b}\#(a,b)F(a,b) \]
\(\#(a,b)\) 表示到结束状态的路径上有 \(a\) 个 \(24\),\(b\) 个 \(25\) 的路径条数。
\(F(a,b)=(\frac{1}{1-24x})^a(\frac{1}{1-25x})^b\frac{1}{1-26x}\) 是一个线性递推的形式。
我TMD，想了几天才发现自己的dp和题解不能说一模一样，只能说毫不相干。
题解的贪心是从两侧分别贪心匹配，直到 第一次 \(l>r\) 这种 立即 停止。这样的确是双射不会算重。
这样的DP可能更有性质，我的就很烂，很烂。
这下，如果不同 \((a,b)\) 对为 \(x\) 组的话，我可以 \(O(xn\log)\) 级别算出 \(F(a,b)\) 以及 \(O(xn^2)\) 算出 \(\#(a,b)\)。
当然根据题解写的 dp 的性质，这样的 \((a,b)\) 只有 \(O(N)\) 对。
那复杂度瓶颈在 \(\#(a,b)\) 的 \(n^3\) 上。
不想写了，想直接跳过了，反正我会将这道题放进queue，真实的神仙题。