题解 P1962 【斐波那契数列】

· · 题解

本人提供一种0ms的数学方法（pascal），时间复杂度为 lg(n)。不是通项公式，先看代码：

···pascal

var n,x,y,t:qword;
g:real;
procedure p(a:qword);  
begin
  if a=2 then
    begin
      x:=1; y:=1;
    end else
  if a mod 2=0 then
    begin
      p(a div 2);
      t:=x*x+2*x*y;
      y:=x*x+y*y;
      x:=t;
    end else
    begin
      p(a-1);
      t:=x+y;
      y:=x;
      x:=t;
    end;
  x:=x mod 1000000007;
  y:=y mod 1000000007;
  //writeln(a,',',x,' ',a-1,',',y); readln;
end;
begin
  readln(n);
  if n=1 then
    begin
      writeln(1);
      halt;
    end;
  p(n);
  writeln(x);
  // g:=sqrt(5);
  //writeln(1/g*(c((1+g)/2,n)-c((1-g)/2,n)));
end.

··· 看看我的公式吧：

f(x)=f(x/2)^2 +2*f(x/2)*f(x/2-1) [x偶数]

f(x)=f(x/2+0.5)^2+f(x/2-0.5)^2 [x奇数]

怎么推的呢？

先看一个表吧

55 34 21 13 8 5 3 2 1 1 数列倒过来

10 9 8 7 6 5 4 3 2 1 编号

  1                                           1个f(10)
  0    1   1                                 f(9)+f(8) =f(10)
  0    0   2  1                            （把f (9)=f(8)+f(7) 代入上式） 2f(8)+f(7)  =f(10
  0    0   0  3    2                      （把f (8)=f(7)+f(6) 代入上式） 3f(7)+2f(6)   =f(10)
  0    0   0  0    5  3                    5f(6)+3f(5)   =f(10)

正好，表中又藏了一个斐波那契，不难推出： f(10)=f(5)*f(6)+f(4)*f(5)

消元：

f(5)*f(6)+f(4)*f(5)=f(5)*( f(5)+f(4) )+f(4)*f(5)

化简、推广得：

f(x)=f(x/2)^2 +2*f(x/2)*f(x/2-1) [x偶数]

奇数再列表找规律，就可又获得一个公式：

f(x)=f(x/2+0.5)^2+f(x/2-0.5)^2 [x奇数]

把数列中相邻两个数看作“一对”，上面两个公式都是：

已知一对数，能求一个数，

比如 已知f(5)=5,f(4)=3，就能用公式1求出f(10), 用公式2求出f(9)

这样，已知一对数，就能求出另一对数；已知 f(x),f(x-1) ，就能求 f(2x),f(2x-1)

最后处理一下奇偶性问题，处理一下边界f(1)=1，即可

我的程序是用递归实现，p过程的意图是：

给出一个a，把f(a)的值赋给x，把f(a-1)的值赋给y 即

已知a，就能求出 f(a),f(a-1) 这一对数

t没有太多卵用，只作为临时变量