我试图用Python解决this问题。注意到只有初吻需要交替,任何由于初吻而不是链条一部分的吻都可以很好地拥抱下一个第二个人,这是我想出的密码。这只是一个简单的数学计算,没有循环,没有迭代,什么都没有。但我仍然收到一条超时的信息。有什么方法可以优化它吗?在
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
你用非常大的指数计算能力,如果结果不在过程中减少,这是非常缓慢的。例如,
10**10000000 % 11
的简单计算需要创建一个10000000位数字并取模11。一个更好的方法是modular exponentiation,在每次乘法后减少模11,而整数永远不会变大。在Python提供了内置的模幂运算。使用
pow(a,b,c)
计算(a**b) % c
。在这是假设你的算法是正确的,我没有验证。在
答案是一个非常简单的递归。}我们有两个选择:
F(1) = 2
对于{n = H
,那么亲吻剩下的客人的方法就只是F(n-1)
n = K
,那么亲吻剩余客人的方式是2 ** k
,其中{k = ceil((n - 1) / 2)
把它们放在一起,我们得到
F(n) = F(n - 1) + 2 ** ceil((n - 1) / 2)
我的尝试,包括拿走所有的mod 100000007:
编辑:更新(更快,更不可读!
^{pr2}$F(1e9)
大约需要3分钟):编辑2:经过进一步思考,我意识到上面的事实只是:
但是如果
n
是偶数,最后一个2 ** n/2
只出现一次,所以我们有:跑得快多了!(受限于
pow(x, y, z)
的速度,我认为是O(lg n)
?)在只是因为,这里有一条线:
结果:
相关问题 更多 >
编程相关推荐