被第二题搞得坐牢2个半小时，在最后10分钟才确定推出的求和公式没问题，是除法取模不规范导致求解有偏差，只能说菜是原罪。这里贴一下赛后修改的代码，希望能对列位有些帮助，欢迎巨佬指导。
思路：
- 分奇偶讨论固定长度下伪回文串的数量，定义长度为\(n\)的伪回文串的数量为\(a_{n}\)：
（1）\(n\)为偶数时，\(a_{n} = 26^{\frac{n}{2}}\times\frac{n}{2}\times25\)；
（2）\(n\)为奇数时，\(a_{n} = 26\times26^{\frac{n-1}{2}}\times\frac{n-1}{2}\times25\)。
- 对长度不超过\(n\)的伪回文串的数量求和，得\(S_{m}\)（为方便计算，这里我们定义\(m = \lfloor \frac{n}{2} \rfloor\)，并优先考虑\(n\)为奇数的情况）：
\[S_{m}=\sum_{k=1}^{m}{26^{k}\times k \times25 + 26\times26^{k}\times k \times25}
=\sum_{k=1}^{m}{27\times26^{k}\times k \times25}
\]
- 采用错位相减，化简\(S_{m}\)：
\[S_{m} = 27 \times 26^{m+1}\times\left(m-1\right) + \frac{27 \times \left[ 26^{m}\times(25^{2}-1)+26\right]}{25}
\]
- 如果\(n\)为偶数，则在\(S_{m}\)的基础上减去\(26^{m+1}\times k \times 25\)即可。
其他技巧：这题由于\(n\)的数量级很大，需要采用快速幂算法求解\(26^{m}\)；同时，\(S_m\)中存在除法，要计算分母关于模的逆元，使用分子与分母逆元相乘再取模，代替除法。
代码：
import sys
from functools import cache
def exgcd(a, b):
if b == 0:return a, 1, 0
d, x2, y2 = exgcd(b, a % b)
x1 = y2
y1 = (x2 - (a // b) * y2)
return d, x1, y1
def solve(n):
mod = 10**9 + 7
m = n // 2
add = lambda x, y: (x + y) % mod
pro = lambda x, y: (x * y) % mod
@cache
def fast(m):
nonlocal mod
if m == 0:return 1
elif m == 1:return 26
elif m % 2 == 0:return pro(fast(m // 2), fast(m // 2)) % mod
elif m % 2 == 1:return pro(fast(m // 2), fast(m // 2 + 1)) % mod
base1 = fast(m+1)
base2 = fast(m)
_, rev, _ = exgcd(25, mod)
Sm = add(pro(27, pro(base1, m-1)), pro(pro(27, add(pro(base2, 25**2-1), 26)), rev))
if n % 2 == 0:
result = add(Sm, -pro(pro(25, pro(26, m)), base2))
else:
result = Sm
return result
for line in sys.stdin:
n = int(line.split()[0])
ans = solve(n)
print(ans)