-2

该代码在我的解释器上运行良好，但在 spoj 上提供了 NZEC。

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

我究竟做错了什么？

4

3 回答 3

0

我怀疑你得到的是 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-07T02:12:37.333 回答
0

这可能是由于溢出错误

当 10^9 中的 m 值很大时，内置的pow()函数，即 ** 运算符，效果不如预期。

>>> (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 m)。由于在Binet 公式中为幂创建朴素函数可能最终会达到O(m)

于 2015-05-31T12:25:43.450 回答
0

也检查我的代码：#include using namespace std;

#define mod 1000000007

long long result[2][2]={{1,1},{1,0}};
long long transformation[2][2]={{1,1},{1,0}};    
void matrixMul(long long a[2][2],long long b[2][2])
{
 int i,j,k;
 long long re[2][2] ={0};
 for(i=0;i<2;i++) {
    for(j=0;j<2;j++) {
        for(k=0;k<2;k++) {
            re[i][j] = (re[i][j] + (a[i][k]*b[k][j])%mod ) % mod;
        }
    }
 }
 for(i=0;i<2;i++)
 {
    for(j=0;j<2;j++)
        result[i][j]=re[i][j];
 }
}

void initialize() {
result[0][0]=result[0][1]=result[1][0]=1;
result[1][1]=0;
}
void power(int n)
{
if(n==1)
return ;
power(n/2);
matrixMul(result,result);
if(n&1)
{
    matrixMul(result,transformation);
}
}

int main()
{   
int t;
cin>>t;
while(t--){
initialize();
long long n,m;
cin>>n>>m;
long long x,y;
if(n == 0 || n == 1) {
        x=n;
}
else {
    power(n);
    x=result[0][0]-1;
}
initialize();
if(m == 0 || m == 1) {
        x=m;
}
else {
    power(m+1);
    y=result[0][0]-1;
}
if(x>y){
    x=x-y;
}
else
    x=y-x;

cout<<((x+mod)%mod)<<endl;
}
return 0;
}
于 2019-02-04T06:19:56.393 回答