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。
解体思路：首先需要搞清楚斐波那契数列求和蕴含的规律，先找到它的递归形式：
则其各项相加的平方和为：
以几何的手段证明：12 12 22 32 52 82=8×13
设斐波那契数列的各项为正方形边长，则所求平方和就是算正方形的面积，但是求幂运算需要循环逐个累乘，其复杂度为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)。
套用以下模板：
代码语言：javascript复制typedef long long ll;
ll quick_pow(ll a, ll n)//a^n
{
ll re = 1;
while(n != 0)
{
if(n & 1)//判断n的最后一位是1还是0
re *= a;
a = (a * a);//将a平方，即把a^(2^i)变为a^(2^(i 1))
n >>= 1;//n右移一位，舍去n的最后一位
}
return re;
}本题需要取模，直接在每一步运算中对a和re取模即可。
AC代码：
代码语言：javascript复制#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("%ldn",((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;}
