다 교 10 회 HDU 3936 FIB Query (fibonacci 수열 의 성질 및 Ologn 매트릭스 가속 곱 하기 알고리즘)

Fibonacci 수열 통항 공식 ∴ F (n) = (1 / √ 5) * {[(1 + √ 5) / 2] ^ (n + 1) - [(1 - √ 5) / 2] ^ (n + 1)}
성질:
  1.f(0)+f(1)+f(2)+…+f(n)=f(n+2)-1。 

  2.f(1)+f(3)+f(5)+…+f(2n-1)=f(2n)。 

  3.f(2)+f(4)+f(6)+…+f(2n) =f(2n+1)-1。 

  4.[f(0)]^2+[f(1)]^2+…+[f(n)]^2=f(n)·f(n+1)。 

  5.f(0)-f(1)+f(2)-…+(-1)^n·f(n)=(-1)^n·[f(n+1)-f(n)]+1。 

  6.f(m+n-1)=f(m-1)·f(n-1)+f(m)·f(n)。 

             ,              O(log n)   。 

  7.[f(n)]^2=(-1)^(n-1)+f(n-1)·f(n+1)。 

  8.f(2n-1)=[f(n)]^2-[f(n-2)]^2。 

  9.3f(n)=f(n+2)+f(n-2)。 

  10.f(2n-2m-2)[f(2n)+f(2n+2)]=f(2m+2)+f(4n-2m) [ n〉m≥-1, n≥1] 

    11.f(2n+1)=[f(n)]^2+[f(n+1)]^2.

   3 2 ,    4 3 ,    5 5 ,    6 8 ,    7 13 ,    8 21 ,    9 34 ,   .......    5、7、11、13、17、23 :5,13,89,233,1597,28657( 19 )

: 60

  11235,83145,94370,77415,61785.38190,
  99875,27965,16730,33695,49325,72910…


4 6

  sum[i]=sigma(p[j]) 1<=j<=i .

p[i]=f[2*i-1]^2+f[2*i]^2.

4 sum[i]=f[2*i]*f[2*i+1].

sum[r]-sum[l-1] 。

f[2^n].

HDU  78ms 11 10 62   

#include 
#include 

typedef long long ll;
const ll mod=1000000007;
ll mtrx[60][2][2];

void debug (ll a[][2])
{
    printf("%lld  %lld
%lld %lld
",a[0][0],a[0][1],a[1][0],a[1][1]); } void pre_pro() { memset (mtrx , 0 , sizeof(mtrx)); mtrx[0][0][0]=1;mtrx[0][0][1]=1; mtrx[0][1][0]=1;mtrx[0][1][1]=0; for (int t=0 ; t<60 ; ++t) for (int i=0 ; i<2 ; ++i) for (int j=0 ; j<2 ; ++j) { for (int k=0 ; k<2 ; ++k) mtrx[t+1][i][j]+=mtrx[t][i][k]*mtrx[t][k][j]; mtrx[t+1][i][j]%=mod; } } ll fib (ll a) { a--; ll mat[2][2]={1,0,0,1}; ll tmp[2][2]; for (int p=0 ; a ; a>>=1 , ++p) { if(!(a&1))continue; tmp[0][0]=mat[0][0];tmp[0][1]=mat[0][1]; tmp[1][0]=mat[1][0];tmp[1][1]=mat[1][1]; memset (mat, 0 , sizeof(mat)); for (int i=0 ; i<2 ; ++i) for (int j=0 ; j<2 ; ++j) { for (int k=0 ; k<2 ; ++k) mat[i][j]+=mtrx[p][i][k]*tmp[k][j]; mat[i][j]%=mod; } } //debug (mat); return mat[0][0]; } ll sum(ll a) { if(a==0)return 0; else return fib(2*a)*fib(2*a+1)%mod; } int main () { pre_pro(); int cas; //freopen ("in.in","r",stdin); //freopen ("out.txt","w",stdout); //for (int i=0 ; i<20 ; ++i) debug(mtrx[i]); scanf("%d",&cas); while (cas--) { ll l,r; scanf("%I64d%I64d",&l,&r); printf("%d
",(sum(r)-sum(l-1)+mod)%mod); } return 0; }


 

 

좋은 웹페이지 즐겨찾기