1

この問題を Python で解決しようとしています。最初のキスだけが交代を必要とすることに注意してください.最初のキスのためにチェーンの一部ではないキスは、2番目の次の人に抱擁を与えることができます.これは私が思いついたコードです. これは単純な数学的計算であり、ループも反復も何もありません。しかし、それでもタイムアウトのメッセージが表示されます。それを最適化する手段はありますか？

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

これに対する答えは、非常に単純な再帰です。2 つの選択肢があります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は 1 回しか発生しないため、次のようになります。

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 に答える