华泰证券FINTECH决赛第二题题解

标签：决赛 26 FINTECH 题解 pro fast times return mod

被第二题搞得坐牢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)

标签：决赛,26,FINTECH,题解,pro,fast,times,return,mod
From： https://www.cnblogs.com/zl-record/p/17538288.html