2014年蓝桥杯本科C/C++组预赛第9题是很好的一道关于斐波那契(Fibonacci)数列的题目。本文将从这一题目出发,探讨一些与斐波那契数列相关的性质。

题目

题目链接:斐波那契 http://lx.lanqiao.org/problem.page?gpid=T121

题目内容:

问题描述

斐波那契数列大家都非常熟悉。它的定义是:

f(x)={1x=1,2f(x1)+f(x2)x>2

对于给定的整数 nm,我们希望求出:f(1)+f(2)++f(n) 的值。但这个值可能非常大,所以我们把它对 f(m) 取模。

公式如下:

(i=1nf(i)) mod f(m)

但这个数字依然很大,所以需要再对 p 取模。

  • 输入格式 输入为一行用空格分开的整数 n m p (0<n,m,p<1018)
  • 输出格式 输出为1个整数,表示答案
  • 样例输入 2 3 5
  • 样例输出 0
  • 样例输入 15 11 29
  • 样例输出 25

Fibonacci数列

通过递推式和特征方程,不难得到Fibonacci数列的通项公式为:

f(n)=15((1+(5)2)n(1+(5)2)n)

根据Fibonacci数列的递推关系,可以使用矩阵乘法的方法来在O(log n)的时间复杂度内求得Fibonacci数列的第 n 项的值。具体算法:

A=[1110],f(n)=An1[0][0]

Fibonacci数列有很多很有用的性质,首先根据Fibonacci数列的递推关系,有:

f(n+1)=f(n)+f(n1)

那么,由此得到:

f(n)=f(n+1)f(n1)

从这个等式可以推出:

i=1nf(i)=f(1)+f(2)+f(3)++f(n)=f(1)+f(3)f(1)+f(4)f(2)++f(n+1)f(n1)=f(n)+f(n+1)f(2)=f(n+2)1

这个性质非常重要,通过这个性质,可以将Fibonacci数列前 N 项的求和转化为求解某一项的值。

与上式同理,不难得到:

i=1nf(2i1)=f(1)+f(3)+f(5)++f(2n1)=f(2n)1i=1nf(2i)=f(2)+f(4)+f(5)++f(2n)=f(2n+1)1

此外,Fibonacci数列还有以下这些有用的性质:

i=1nf(i)2=f(n)f(n+1) i=1nf(i)(1)i=(1)n(f(n+1)f(n))+1

常用的还有下列结论:

f(n+m)=f(n+1)f(m)+f(n)f(m1)f(2n+1)=f(n+1)2+f(n)2f(2n)=2f(n)f(n+1)f(n)2f(n)2=(1)n+1+f(n1)f(n+1)

由上式稍作变换,便有 f(m1)2 mod f(m)=(1)m

这两个公式都可以通过数学归纳法证明。

题目分析

通过上面的Fibonacci数列前N项求和公式,可以将原来的问题简化成 f(n)%f(m)%p 的情形。

f(n) mod f(m)=f(nm+m) mod f(m)=(f(nm+1)f(m)+f(nm)f(m1)) mod f(m)=f(n)f(m1) mod f(m)==f(m1)nmf(n mod m) mod f(m)

因此,当 m 的值比较小时,完全可以通过预处理一定范围内的Fibonacci数列,便可以求解出问题的答案。

那么对于本题呢?题目中 n,m 的值都达到了 1018,可见,无法通过上面的方面求解。

上文中,我们已经将问题规约为求解 (f(n+2)1) mod f(m) mod p ,因此,下面将针对这一简化后的问题讨论其解法。 因为这一问题与 f(n+2) mod f(m) mod p 等价(仅仅需要将结果减 1 加上 p 然后对 p 取模),为方便起见, 后文主要讨论 f(n+2) mod f(m) mod p

如果 n+2==m,那么显然只需要求解出第 m 项的结果即可(因为涉及到 1+pf(m) 取模)。最终答案应该为

f(m) mod p1+p) mod p

结合前面提到了快速幂模的方法,这个问题是容易的。我们还有以下结论(推导过程参见文末参考 2):

  1. k 为奇数时,f(m1)×f(k) mod f(m)=f(mk)
  2. k 为偶数时,f(m1)×f(k) mod f(m)=f(m)f(mk)
  • 如果 m 为偶数,那么如果 nmn2m 都是偶数,那么结果应该是: f(n) mod f(m)=f(n mod m)

  • 如果 m 为奇数,那么:

    • 如果 nmn2m 都是偶数,那么结果应该是: f(n) mod f(m)=f(n mod m)
    • 如果 nm 是偶数,n2m 是奇数,那么结果应该是: f(n) mod f(m)=f(m)f(n mod m)
    • 如果 nm 是奇数,n2m 是偶数,那么结果应该是:
      • 如果 n mod m 是奇数,结果为 f(n) mod f(m)=f(mn mod m)
      • 如果 n mod m 是偶数,结果为 f(n) mod f(m)=f(m)f(mf(n mod m))
    • 如果 nmn2m 都是奇数,那么结果应该是:
      • 如果 n mod m 是奇数,结果为 f(n) mod f(m)=f(m)f(mf(n mod m))
      • 如果 n mod m 是偶数,结果为 f(n) mod f(m)=f(mn mod m)
  • 如果 m 是偶数,那么:

    • 如果 nm 是奇数,那么结果应该是:
      • 如果 n mod m 是奇数,结果为 f(n) mod f(m)=f(mn mod m)
      • 如果 n mod m 是偶数,结果为 f(n) mod f(m)=f(m)f(mf(n mod m))
    • 如果 nm 是偶数,那么结果应该是: f(n) mod f(m)=f(n mod m)

至此,本题基本解决完毕。

其他的细节

这道题的数据量非常大,因此在其他的一些地方也应该充分注意,才有可能通过全部测试点。

  1. 使用矩阵快速幂模来求解某一项的值。
  2. 64位整数的二进制分解乘法(long long乘以long long会导致溢出)。
long long multiply(long long a, long long b) {
    long long ans = 0;
    a %= MOD;
    while(b) {
        if(b & 1) {
            ans = (ans + a) % MOD;
            b--;
        }
        b >>= 1;
        a = (a + a) % MOD; // a *= 2
    }
    return ans;
}

题目Accept代码:PREV_29.cpp

Fibonacci另一种快速算法

http://www.zhihu.com/question/29215494看到了另一种基于分治的Fibonacci数列第n项的方法:

double Fibonacci(int n){
    double x = 1.0, y = 1.0, a = 0, b = 1.0,t;
    while (n>0)
    {
        if (n & 1){
            t = a*x + b*y;
            a = x*(b - a) + a*y;
            b = t;
        }
        t = 2 * x*y - x*x;
        y = x*x + y*y;
        x = t;
        n >>= 1;
    }
    return a;
}

关于该算法的解释如下图所示:

参考

  1. Fibonacci数列的幂和
  2. 从蓝桥杯来谈Fibonacci数列