2

我正在解决这个问题：

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)

模 1000000007。

Input

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

行包含一个整数 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;
}

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

4

4 回答 4

1

G(n) = G(n-1) + f(4n-1) = G(n-2) + f(4n-1) + f(4n-5) 等等。

所以

G(n) = f(4n-1) + f(4n-5) + f(4n-9) ... f(3)

f(n) = f(n-1) + f(n-2) = 2f(n-2) + f(n-3) = 3f(n-3) + 2f(n-4) = 5f(n -4) + 3f(n-5) f(n-5) = 3f(n-8) + 2f(n-9) 因此 f(n) = 5f(n-4) + 9f(n-8) + 6f(n-9) = 5f(n-4) + 9f(n-8) + 18f(n-12) + 12f(n-13)

= 5f(n-4) + 9f(n-8) + 18f(n-12) + 36f(n-16) + 24f(n-17)

无论如何，很明显系数每次都会翻倍。当然，从上面我们可以根据 f(n-8) 等定义 f(n-4)。不确定这会导致什么。

这里有一个系列， f(3)=2 和 f(2) = 1 所以最后你将添加常数。

实际上，尽管出于您的目的，您可以一次计算 f(n) 而不必在此时存储超过 2 个，并且您知道上面 G 的公式，当您通过计算 f(n) 时，您可以更新当 n 在每个点与 3 mod 4 相等时，G 适当地对斐波那契数求和。

您将找不到空间来保存具有如此庞大数字（2 的 51 次方）的表，甚至无法保存到磁盘，尽管它确实是您需要存储在表中的总和 (f(3), f(3 )+f(7)、f(3)+f(7)+f(11) 等）如果你要保存任何东西。

于 2011-02-02T14:56:39.083 回答
1

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

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

（我不确定这是否适合您的情况，我只是为您指出另一种方法）

例如，在《计算机编程艺术》第 1 卷：基本算法中， Knuth 使用了“生成函数”，这是一种 为 Fn 斐波那契数
构造封闭形式的巧妙方法。

有关更多信息，请阅读生成函数 (pdf)

为什么要关心序列的生成函数？有几个答案，但这里有一个：如果我们可以找到序列的生成函数，那么我们通常可以找到第 n 个系数的封闭形式——这非常有用！例如，x/(1−x−x 2 )的幂级数中 x n的系数的封闭形式将是第 n 个斐波那契数的显式公式。[...]

于 2011-02-02T14:23:38.850 回答
0

那么 f() 是斐波那契函数吗？我建议您使用常规递归算法。但是您可以通过添加缓存来显着提高性能，因为对于较小的 i 值的 f(i) 调用将非常频繁地重复。

您可以通过使用静态本地整数数组来做到这一点。如果元素为 0，则为未命中，因此您计算该值并将其存储在数组中。

这样您就可以避免使用浮点运算，并且不会填满堆栈。

于 2011-02-02T13:19:44.227 回答
0

我认为获得价值的更好方法G(n)是像这样计算它：

type val(type n, std::vector<type> &fib)
{
  type ret = 0, s = min(type(fib.size()), n);
  for(type i=0; i < s; ++i)
      ret += fib[i];

  if(n > fib.size()){    
    fib.reserve(n);
    int tmp;
    for(type i = fib.size(); i < n; ++i){
      tmp = f(4*i+3);
      fib.push_back(tmp);
      ret += tmp;
    }

  }
  return ret;
}

（对于整个代码检查http://www.ideone.com/jorMy）

尽可能避免递归，这样就不会每次都计算斐波那契函数。

编辑：我花了很多时间来发现（我的数学有点生疏），但你也可以这样写 val ：

numtype val(numtype n) {
  return ceil(2.218*pow(6.8541,n-1) - 0.018*pow(0.145898,n-1) - 0.2);
}

（http://www.ideone.com/H1SYz上的代码）

这是您的总和的封闭形式。如果您想自己找到它（毕竟这是家庭作业），请按照 Nick D 的回答。

于 2011-02-02T13:47:54.917 回答