1

我正在尝试用 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
4

2 回答 2

11

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

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

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

于 2012-09-02T09:43:35.147 回答
3

答案是一个非常简单的递归。F(1) = 2因为F(n)我们有两个选择：

  • n = H，那么亲吻剩下的客人的方式数简直就是F(n-1)
  • n = K，那么亲吻剩余客人的方式数就是公主不被强迫亲吻的剩余客人的数量2 ** k。k由于她必须亲吻剩下的每一位客人，k = ceil((n - 1) / 2)

把它们放在一起，我们得到F(n) = F(n - 1) + 2 ** ceil((n - 1) / 2)

我的尝试，包括采取一切 mod 1000000007：

from math import ceil

def F(n):
    m = 1000000007
    a = 2
    for i in range(2, n+1):
        a = (a + pow(2, int(ceil((i - 1.0) / 2)), m)) % m
    return a

编辑：更新（更快，更不可读！F(1e9)大约需要 3 分钟）：

def F(n):
    m = 1000000007
    a = 2
    z = 1

    for i in xrange(2, n, 2):
        z = (z * 2) % m
        a = (a + z + z) % m

    if (n & 1 == 0):
        z = (z * 2) % m
        a = (a + z) % m

    return a

编辑2：经过进一步思考，我意识到上面实际上只是：

F(n) = (1 + 1) + (2 + 2) + (4 + 4) + ... + (2 ** n/2 + 2 ** n/2)
     = 2 * (1 + 2 + 4 + ... + 2 ** n/2)
     = 2 * (2 ** (n/2 + 1) - 1)
     = 2 ** (n/2 + 2) - 2

但是如果n是偶数，最后一个2 ** n/2只出现一次，所以我们有：

def F(n):
    m = 1000000007
    z = pow(2, n/2, m)

    if (n % 2 == 0):
        return (z * 3 - 2) % m
    else:
        return (z * 4 - 2) % m

哪个运行得更快！（受速度限制pow(x, y, z)，我认为是O(lg n)？）

仅仅因为，这里是单线：

def F(n):
    return (pow(2, n/2, 1000000007) * (3 + n % 2) - 2) % 1000000007

结果：

1   => 2
2   => 4
3   => 6
4   => 10
5   => 14
6   => 22
7   => 30
8   => 46
9   => 62
10  => 94
1e6 => 902893650
1e7 => 502879941
1e8 => 251151906
1e9 => 375000001
于 2012-09-02T10:38:13.717 回答