c++ - 我可以做些什么来改进我的斐波那契数生成器？

Question

我正在解决这个问题:

G(n) is defined as

G(n) = G(n-1) + f(4n-1) , for n > 0

and G(0) = 0

f(i) is ith Fibonacci number. Given n you need to evaluate G(n)

modulo 1000000007.

Input

First line contains number of test cases t (t<40000). Each of the next t

lines contain an integer n ( 0 <= n < 2^51).

Output

For each test case print G(n) modulo 1000000007.

Example

Input:
2
2
4



Output:


15
714

这是我写的代码:

typedef long long type;
#define check 1000000007
type x;
type y;

type f(type n)
{
    return(ceil((pow(1.618,n) - pow(-0.618,n))/((sqrt(5)*1.0))));
}
type val(type n)
{
    if(n==0)
    return 0;
    else 
    return (val(n-1)+f(4*n-1));
}
int main()
{
    cin>>x;
    while(x--)
    {
       cin>>y;
       cout<<val(y)%check<<endl;
       }
    //getch();
    return 0;
}

你能提出任何改进建议吗？

Answer 1

有时这些问题可以用数学技巧来解决，
而不是蛮力解决方案。

在我看来，n 和模的较大值表明
存在一个聪明的解决方案。当然，找出解决方案是困难的部分。

(我不确定这是否适合您的情况，我只是为您提供另一种方法)

例如，在 Art of Computer Programming, Volume 1: Fundamental Algorithms
Knuth 使用“生成函数”，一种构造封闭形式的巧妙方法
为 Fn 斐波那契数。

有关更多信息，请阅读 Generating Functions (pdf)

Why should one care about the generating function for a sequence? There are several answers, but here is one: if we can find a generating function for a sequence, then we can often find a closed form for the nth coefficient— which can be pretty useful! For example, a closed form for the coefficient of xⁿ in the power series for x/(1−x−x²) would be an explicit formula for the nth Fibonacci number. [...]