NZEC用於python中的fibosum（spoj）

-1

該代碼在我的解釋器上工作得很好，但給NZEC上了spoj。NZEC用於python中的fibosum（spoj）

cases = int(raw_input()) 
for i in xrange(cases): 
    k = 0 
    n,m = map(int, sys.stdin.readline().split()) 
    sq5 = Decimal(sqrt(5)) 
    phi = (1 + sq5)/2       #Refer wikipedia page for calculating fibonacci numbers 
    print (int(Decimal(phi)**(m+2)/sq5 + Decimal(0.5)) - int(Decimal(phi)**(n+1)/sq5 + Decimal(0.5)))%1000000007

我在做什麼錯？

來源

2012-10-08 Shiva Teja

裹行'N，M =地圖（INT，...'裏面你在一個'嘗試循環：N ，m = map（int，... except：break'）這是否工作？ – halex

不會。它仍然給NZEC。 –

您需要用於此問題的斐波那契數字太大，無法以任何合理的方式準確存儲在Decimal中精度（F（10 ** 9）有超過2億位數）！您需要重新考慮您對問題的處理方法。 –

我懷疑你正在得到一個NZEC，因爲輸入中有多餘的空格。但是，處理它們很簡單。立即讀取輸入，然後用空格標記它。

import sys 
tokenizedInput = sys.stdin.read().split() # Delimited by white spaces 
cases = int(tokenizedInput[0]) 
readAt = 1 
for i in xrange(cases): 
    k = 0 
    n,m = map(int, tokenizedInput[readAt:readAt+2]) 
    sq5 = Decimal(sqrt(5)) 
    phi = (1 + sq5)/2       #Refer wikipedia page for calculating fibonacci numbers 
    print (int(Decimal(phi)**(m+2)/sq5 + Decimal(0.5)) - int(Decimal(phi)**(n+1)/sq5 + Decimal(0.5)))%1000000007 
    readAt = readAt + 2 # Increment the position to read at by 2

如果你提交這個，你應該得到一個TLE。正如Mark Dickinson在問題評論中指出的那樣，這是一種效率低下的算法。

來源

2013-01-07 02:12:37 sidi

這可能是由於OverflowError

內置POW（）函數，即**操作，工作沒有得到很好的時候米10^9的值是相當大的預期。

>>> (1.1)**1000000000 

Traceback (most recent call last): 
File "<pyshell#0>", line 1, in <module> 
1.1**(100000000) 
OverflowError: (34, 'Numerical result out of range')

即使math.pow（）將無法正常工作。

>>> import math 
>>> math.pow(1.1,1000000000) 

Traceback (most recent call last): 
File "<pyshell#2>", line 1, in <module> 
math.pow(1.1,1000000000) 
OverflowError: math range error

而是通過O（LN米）使用矩陣方法來代替比奈的斐波納契式的去。正如比奈的公式創建功率天真功能最終可能高達O（M）

來源

2015-05-31 12:25:43 Deepit

NZEC用於python中的fibosum（spoj）

回答

相關問題