这里有更好的算法吗？

Question

我试图在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.更好的方法是模幂运算,你在每次乘法后减少模11并且整数永远不会变大.

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

这是假设您的算法是正确的,我没有验证.