我正在解决这个问题：
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
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;
}
您能提出任何改进建议吗？
有时此类问题可以通过数学技巧来解决，
而不是暴力解决方案。
的大值n在我看来，模数表明
存在一个聪明的解决方案。当然，找出解决方案是困难的部分。
（我不确定这是否适合您的情况，我只是向您指出另一种方法）
例如，在计算机编程艺术，第一卷：基本算法 https://rads.stackoverflow.com/amzn/click/com/0201896834
Knuth 使用“生成函数”，这是一种构建封闭形式的巧妙方法
为 Fn 斐波那契数列。
欲了解更多信息，请阅读生成函数 (pdf) http://courses.csail.mit.edu/6.042/fall05/ln11.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 xn in the
power series for x/(1−x−x2)
would be an explicit formula for the
nth Fibonacci number. [...]
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
