812
HDU 3936 斐波那契性質矩陣連乘
題意：p[i]=fib[4*i-1] 給出L,R，求出中間的p[i]的和。
利用性質：p[1]+p[2]+...+p[n]=f[1]^2+f[2]^2+...+f[2*n-1]^2+f[2*n]^2=f[2*n]*f[2*n+1]
fibonacci數列的性質：
1.gcd(fib(n),fib(m))=fib(gcd(n,m))
證明：可以通過反證法先證fibonacci數列的任意相鄰兩項一定互素，然後可證n>m時gcd(fib(n),fib(m))=gcd(fib(n-m),fib(m))，遞歸可
求gcd(fib(n),fib(m))=gcd(fib(k),fib(l))，最後k=l，不然繼續遞歸。K是通過展轉相減法求出，易證k=gcd(n,m)，所以gcd(fib(n),fib(m))
=fib(gcd(n,m))。
2.如果fib(k)能被x整除，則fib(k*i)都可以被x整除。
3.f(0)+f(1)+f(2)+…+f(n)=f(n+2)-1
4.f(1)+f(3)+f(5)+…+f(2n-1)=f(2n)
5.f(2)+f(4)+f(6)+…+f(2n) =f(2n+1)-1
6.[f(0)]^2+[f(1)]^2+…+[f(n)]^2=f(n)·f(n+1)
7.f(0)-f(1)+f(2)-…+(-1)^n·f(n)=(-1)^n·[f(n+1)-f(n)]+1
8.f(m+n)=f(m-1)·f(n-1)+f(m)·f(n)
9.[f(n)]^2=(-1)^(n-1)+f(n-1)·f(n+1)
10.f(2n-1)=[f(n)]^2-[f(n-2)]^2
11.3f(n)=f(n+2)+f(n-2)
12.f(2n-2m-2)[f(2n)+f(2n+2)]=f(2m+2)+f(4n-2m) [ n〉m≥-1,且n≥1]
#include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define M 1000000007
const int MAX=2;
typedef long long int64;
typedef struct
{
long long m[MAX][MAX];
} Matrix;
Matrix P=
{
0,1,
1,1,
};
Matrix I=
{
1,0,
0,1,
};
Matrix matrixmul(Matrix a,Matrix b) //矩陣乘法
{
int i,j,k;
Matrix c;
for (i = 0 ; i < MAX; i++)
for (j = 0; j < MAX; j++)
{
c.m[i][j] = 0;
for (k=0; k<MAX; k++)
c.m[i][j]+=(a.m[i][k]*b.m[k][j])%M;
c.m[i][j]%=M;
}
return c;
}
Matrix quickpow(long long n)
{
Matrix m = P, b = I;
while (n >= 1)
{
if (n & 1)
b = matrixmul(b,m);
n = n >> 1;
m = matrixmul(m,m);
}
return b;
}
int main()
{
int t;
long long l,r;
scanf("%d",&t);
while(t--)
{
scanf("%I64d%I64d",&l,&r);
long long x,y;
Matrix a=quickpow(2*l-3),b=quickpow(2*l-2);
x=((a.m[0][0]+a.m[0][1])%M)*((b.m[0][0]+b.m[0][1])%M)%M;
if(l==1)
x=0;
a=quickpow(2*r-1),b=quickpow(2*r);
y=((a.m[0][0]+a.m[0][1])%M)*((b.m[0][0]+b.m[0][1])%M)%M;
long long ans=((y-x)%M+M)%M;
printf("%I64d\n",ans);
}
return 0;
}
最後更新：2017-04-03 16:48:36