没见过的套路，还是很神的。模数写成 \(10^4+5\) 调了 1h /fn。
首先记 \(m=|S|+n\)。
计数考虑 dp。插入字符使其成为回文串 dp 显然是困困难难的。
考虑从最终插入字符后的结果入手，则对于回文串 \(T\) 能通过 \(S\) 插入字符得到当且仅当 \(|T|=|S|+n\) 且 \(S\) 为 \(T\) 的子序列。
因为 \(T\) 是回文串，所以若是类似状态 \(f_{i,j}\) 表示前 \(i\) 个字符最多匹配到 \(S\) 第 \(j\) 个字符则会有后效性。
于是设计状态 \(f_{i,l,r}\) 表示考虑 \(T\) 的前后 \(i\) 个字符，\(S\) 剩下 \(S:[l,r]\) 未匹配，则转移为：
- \(S_l=S_r\)：
\(f_{i,l,r}\to f_{i+1,l+1,r-1}\)。
\(f_{i,l,r}\to 25\cdot f_{i,l,r}\)。
第一条转移表示 \(T_{i+1}=T_{m-i}=S_l(S_r)\) 则 \(T_{i+1}\)，\(T_{m-i}\) 只有一种选择，且 \(S_l,S_r\) 均会被匹配。
第二条转移表示 \(T_{i+1}=T_{m-i}\ne S_l(S_r)\) 则 \(T_{i+1}\)，\(T_{m-i}\) 有 25 种选择，且 \(S_l,S_r\) 均不会被匹配。
- \(S_l\ne S_r\)：
\(f_{i,l,r}\to f_{i+1,l+1,r}\)。
\(f_{i,l,r}\to f_{i+1,l,r-1}\)。
\(f_{i,l,r}\to 24\cdot f_{i,l,r}\)。
前两条转移式分别表示 \(T_{i+1}=T_{m-i}=S_l\)，\(T_{i+1}=T_{m-i}=S_r\)。
第三条转移表示 \(T_{i+1}=T_{m-i}\ne S_l/S_r\) 则 \(T_{i+1}\)，\(T_{m-i}\) 只有 24 种选择，且匹配情况不变。