F



i



v



e



-



gr



ea



t
friend-斐波那契

friend-斐波那契

6264. friend-斐波那契


Description

求f12+f22+f32+....+fn2, 其中 fi 代表斐波那契数列的第 i 项。 (f0=0,f1=1)当然结果会很大,请将它对 109+7取模。

输入格式

一行一个数 n.

输出格式

一行一个数,代表答案。

样例

样例输入

6

样例输出

104

数据范围与提示

对于30%的数据:n≤105。

对于另外20%的数据: 1000000∣n (即n是1000000的倍数),且n≤5∗109。

对于100%的数据:n≤1018。


解体思路:首先需要搞清楚斐波那契数列求和蕴含的规律,先找到它的递归形式:

img

则其各项相加的平方和为:

img

以几何的手段证明:12+12+22+32+52+82=8×13

img

设斐波那契数列的各项为正方形边长,则所求平方和就是算正方形的面积,但是求幂运算需要循环逐个累乘,其复杂度为O(n),这在很多时候是不够的,所以我们需要用快速幂——反复平方法来加速幂运算的过程,要想办法减少步骤,把其中的某一部分合成一步来进行。

比如,如果n能被2整除,那我们可以先计算一半,得到a^(n/2)的值,再把这个值平方得出结果。这样做虽然有优化,但优化的程度很小,仍是线性的复杂度。

再比如,如果我们能找到2k = n,那我们就能把原来的运算优化成((((a2) 2) 2)...),只需要k次运算就可以完成,效率大大提升。可惜的是,这种条件显然太苛刻了,适用范围很小。不过这给了我们一种思路,虽然我们很难找到2k == n,但我们能够找到2k1 + 2k2 + 2k3 +......+ 2km =n。这样,我们可以通过层层递推,在很短的时间内求出各个项的值。可是又有新的问题出现了,我们并不清楚k1、k2...km具体的值是多少,对于不同的n,有不同分法,有没有一种规则能把这些分法统一起来。

我们都学习过进制与进制的转换,知道一个b进制数的值可以表示为各个数位的值与权值之积的总和。比如,2进制数1001,它的值可以表示为10进制的123 + 022 + 021 + 120,即9。这完美地符合了上面的要求。可以通过2进制来把n转化成2^km的序列之和,而2进制中第i位(从右边开始计数,值为1或是0)则标记了对应的2(i - 1)是否存在于序列之中。譬如,13为二进制的1101,他可以表示为23 + 22 + 20,其中由于第二位为0,21项被舍去。

如此一来,我们只需要计算a、a2、a4、a8......的值(这个序列中的项不一定都存在)并把它们乘起来即可完成整个幂运算。借助位运算的操作,可以很方便地实现这一算法,其复杂度为O(logn)。

套用以下模板:

本题需要取模,直接在每一步运算中对a和re取模即可。

AC代码:

 

#include<string.h>
#include<stdio.h>
#define ll long long
#define MOD 1000000007
struct nobe{ ll a[2][2];};
ll n;
ll sum;
nobe mut(nobe x,nobe y){
nobe res;
memset(res.a,0,sizeof(res.a));
for(ll i=0;i<2;i++)
    for( int j=0;j<2;j++)
    for( int k=0;k<2;k++)
      res.a[i][j]=(res.a[i][j]+x.a[i][k]*y.a[k][j])%MOD;
return res;}
void quick(ll n){
      nobe c,res;
        c.a[0][0]=1;
        c.a[0][1]=1;
        c.a[1][0]=1;
        c.a[1][1]=0;
          memset(res.a,0,sizeof(res.a));
            for(int i=0;i<2;i++)
                res.a[i][i]=1;
            while(n)
          {  cont++;
            if(n&1)res=mut(res,c);
                      c=mut(c,c);
            n=n>>1;    }
printf("%ld\n",((res.a[0][1]%MOD)*(res.a[0][1]%MOD+res.a[1][1]%MOD))%MOD);
}
int main(){
    while(scanf("%ld",&n)!=EOF)
    {     quick(n);
    }

return 0;}

  转载请注明: 网站学习 friend-斐波那契