python - 这里可能有更好的算法吗？

Question

我正在尝试解决 this Python 中的问题。请注意，只有初吻需要交替，任何由于初吻而不属于链的一部分的吻都可以很好地拥抱第二个下一个人，这是我想出的代码。这只是一个简单的数学计算，没有循环，没有迭代，什么都没有。但我仍然收到超时消息。有什么办法可以优化吗？

import psyco
psyco.full()
testcase = int(raw_input())
for i in xrange(0,testcase):
    n = int(raw_input())
    if n%2:
        m = n/2;
        ans = 2 + 4*(2**m-1);
        ans = ans%1000000007;
        print ans
    else:
        m = n/2 - 1
        ans = 2 + 2**(n/2) + 4*(2**m-1);
        ans = ans%1000000007
        print ans

Answer 1

您正在计算具有非常大指数的能力，如果结果不在过程中减少，这将非常慢。例如，10**10000000 % 11 的简单计算需要创建一个 10000000 位数字并取模 11。更好的方法是 modular exponentiation在每次乘法后减少模 11，整数永远不会变大。

Python 提供内置的模幂运算。使用 pow(a,b,c) 计算 (a**b) % c。

这是假设你的算法是正确的，我没有验证。