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

被第二题搞得坐牢2个半小时，在最后10分钟才确定推出的求和公式没问题，是除法取模不规范导致求解有偏差，只能说菜是原罪。这里贴一下赛后修改的代码，希望能对列位有些帮助，欢迎巨佬指导。

思路： https://www.cnblogs.com/zl-record/p/17538288.html

代码：

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)