それはここにある私のコードは、常にそれがHackerrank.Theリンクでの問題ですタイムアウト

Question

を取得する理由を作るフィボナッチsequence.Can'tの用語を取得するように求められます再帰的シーケンスF（n + 2）= F（n + 1）+ F（n）のF（1）をそれぞれA、Bに割り当て、N番目の項目を尋ね、モジュロ+ 7）。私は解決する古典的な方法は、迅速な行列の乗法を使用している知っている。そして私はPython3でそれを書く。私のIDEのテストは問題ありません。しかし、なぜ私のコードは常にタイムアウトを取得するのか分からない。 ：

def mul22(a, b): 
    r = [[0, 0], [0, 0]] 
    r[0][0] = (a[0][0] * b[0][0] + a[0][1] * b[1][0]) % 1000000007 
    r[0][1] = (a[0][0] * b[0][1] + a[0][1] * b[1][1]) % 1000000007 
    r[1][0] = (a[1][0] * b[0][0] + a[1][1] * b[1][0]) % 1000000007 
    r[1][1] = (a[1][0] * b[0][1] + a[1][1] * b[1][1]) % 1000000007 
    return r 

def MatrixPow(A, n): 
    if n == 1: 
     return A 
    if n % 2 == 1: 
     return mul22(mul22(MatrixPow(A, n // 2),MatrixPow(A, n // 2)), A) 
    return mul22(MatrixPow(A, n // 2), MatrixPow(A, n // 2)) 

for i in range(int(input())): 
    A,B,N= map(int,input().split()) 
    if N == 1: 
     print(B % 1000000007) 
    else: 
     print(mul22(MatrixPow([[1, 1],[1, 0]], N - 1),[[B,1],[A,1]])[0][0] % 1000000007) 

最初は問題だと思います10 ** 9 + 7はすべての再帰的プロセスを非常に遅くします。しかし、私はIDEで何度もテストして、すべてが大丈夫です.TLEはありません。欠けているものはありますか？

Answer 1

MatrixPow関数の記述方法は、実際にはO(log(n))で実行されていません。実行時間はO(N)です。

この電源機能を考えてみましょう：

def power_n(a,b): 
    print 1 
    if b==0: 
     return 1 
    if b%2==1: 
     return (((power_n(a,b/2)*power_n(a,b/2))%MOD)*a)%MOD 
    return (power_n(a,b/2)*power_n(a,b/2))%MOD 

と、この：

def power_log(a,b): 
    print 2 
    if b==0: 
     return 1 
    k = power_log(a,b/2) 
    if b%2==1: 
     return (((k*k)%MOD)*a)%MOD 
    return (k*k)%MOD 

第一および第二の違いは、我々は後者の場合には一度だけ全体の再帰ツリーを通過しているということである（1回と私たちはそれを保存します）、最初のケースでは何度も繰り返し計算します。

PS（n個のログを記録）、彼らは同じように見えるけれども

、第一1は、従来のループに似ており、第二の機能は、実際にOで実行される電源機能である一方、（n）はOで実行されます： nは、bを意味します。電源

EDIT：

分析： （私は両方の機能にprint文を追加し、それを実行した、ここでの結果は）

power_n(6,20) 
    1 
    1 
    1 
    1 
    1 
    1 
    1 
    1 
    1 
    1 
    1 
    1 
    1 
    1 
    1 
    1 
    1 
    1 
    1 
    1 
    1 
    1 
    1 
    1 
    1 
    1 
    1 
    1 
    1 
    1 
    1 
    1 
    1 
    1 
    1 
    1 
    1 
    1 
    1 
    1 
    1 
    1 
    1 
    1 
    1 
    1 
    1 
    1 
    1 
    1 
    1 
    1 
    1 
    1 
    1 
    1 
    1 
    1 
    1 
    1 
    1 
    1 
    1 
    Out[22]: 414469870 

power_log(6,20) 
    2 
    2 
    2 
    2 
    2 
    2 
    Out[25]: 414469870 

回数の違いを参照してください。関数が呼び出されます。