python - 加权格子路径

Question

对于此链接上的算法(https://projecteuler.net/problem=638)我编写了以下代码，但因为它处理的是大整数并且需要很长时间我正在寻找使其高效的方法，任何人都可以阅读我的代码并给出一些建议，

def WeightedLatticePaths(k):
sigma = []
for m in range(1,k+1):
    X = pow(10,m)+m
    n = 2*X
    x=0
    y=0

    paths =[]
    for i in range(pow(2,n)):
        if ('{0:0%db}'%n).format(i).count('1')==X:
            paths.append(('{0:0%db}'%n).format(i))

    c = []
    for i in range(len(paths)):
        a = []
        route = paths[i]
        for item in route:
            if item=='0':
                y+=1
            if item=='1':
                x+=1
                a.append(y)
        p = sum(a)
        c.append(pow(m,p))

    C = sum(c)
    sigma.append(C)
return sum(sigma)%(1000000007)

Answer 1

尝试查看 modular exponentiation .它会更有效率，但我不确定它是否足够高效。顺便说一下，Python pow您正在使用的内置函数可以采用第三个参数 - 模数。将其用于模幂运算。

在解决结果被调制的问题时，经验法则是在计算过程中尽可能使用模数。因此，您可以确保您使用的数字不会大于您的模数。