[HDU2855]Fibonacci Check-up

题目：Fibonacci Check-up

链接：http://acm.hdu.edu.cn/showproblem.php?pid=2855

分析：

1）二项式展开：$(x+1)^n = \sum^n_{k=0}{C^k_n * x^k}$

2）Fibonacci数列可以写为：$ \left[ \begin{array}{cc} 0 & 1 \\ 1 & 1 \end{array} \right]^n$的左下角项。

3）构造矩阵$ T = Fib+E = \left[ \begin{array}{cc} 0 & 1 \\ 1 & 1 \end{array} \right] + \left[ \begin{array}{cc} 1 & 0 \\ 0 & 1 \end{array} \right] = \left[ \begin{array}{cc} 1 & 1 \\ 1 & 2 \end{array} \right]$。

#include <iostream>

#include <cstring>

#include <cstdio>

using namespace std;

typedef long long LL;

int MOD;

struct Matrix{

    LL a[][];

    void init(int f){

        memset(a,,sizeof a);

        if(f==-)return;

        for(int i=;i<;++i)a[i][i]=;

    }

};

Matrix operator*(Matrix& A,Matrix& B){

    Matrix C;C.init(-);

    for(int i=;i<;++i)

    for(int j=;j<;++j)

        for(int k=;k<;++k){

            C.a[i][j]+=A.a[i][k]*B.a[k][j];

            C.a[i][j]%=MOD;

        }

    return C;

}

Matrix operator^(Matrix A,int n){

    Matrix Rt;Rt.init();

    for(;n;n>>=){

        if(n&)Rt=Rt*A;

        A=A*A;

    }

    return Rt;

}

int main(){

    int n,Case;scanf("%d",&Case);

    Matrix A,T;

    T.a[][]=;T.a[][]=;

    T.a[][]=;T.a[][]=;

    for(;Case--;){

        scanf("%d%d",&n,&MOD);

        A=T^n;

        LL ans=A.a[][];

        printf("%lld\n",ans%MOD);

    }

    return ;

}

4)$\sum^n_{k=0}{C^k_n * f(k)} = f(2*n) $

5)证明：$ \sum^n_{k=0}{C^k_n * f(k)} $

= $ \sum^n_{k=0}{ C^k_n * { [ { ( \frac{1+\sqrt{5}}{2} )}^k - { ( \frac{1-\sqrt{5}}{2} )}^k }] } $

= $ \sum^n_{k=0}{ C^k_n * {( \frac{1+\sqrt{5}}{2} )}^k } - \sum^n_{k=0}{ C^k_n * { ( \frac{1-\sqrt{5}}{2} )}^k } $

= $ { ( \frac{1+\sqrt{5}}{2} + 1 ) }^k $ - $ { ( \frac{1-\sqrt{5}}{2} + 1 ) }^k $

= $ { ( \frac{3+\sqrt{5}}{2} ) }^k $ - $ { ( \frac{3-\sqrt{5}}{2} ) }^k $

= $ { ( \frac{6+2*\sqrt{5}}{4} ) }^k $ - $ { ( \frac{6-2*\sqrt{5}}{4} ) }^k $

= $ { ( \frac{1+\sqrt{5}}{2} ) }^{2k} $ - $ { ( \frac{1-\sqrt{5}}{2} ) }^{2k} $

= $ f(2*k) $

#include <iostream>

#include <cstring>

#include <cstdio>

using namespace std;

typedef long long LL;

int MOD;

struct Matrix{

    LL a[][];

    void init(int f){

        memset(a,,sizeof a);

        if(f==-)return;

        for(int i=;i<;++i)a[i][i]=;

    }

};

Matrix operator*(Matrix& A,Matrix& B){

    Matrix C;C.init(-);

    for(int i=;i<;++i)

    for(int j=;j<;++j)

        for(int k=;k<;++k){

            C.a[i][j]+=A.a[i][k]*B.a[k][j];

            C.a[i][j]%=MOD;

        }

    return C;

}

Matrix operator^(Matrix A,int n){

    Matrix Rt;Rt.init();

    for(;n;n>>=){

        if(n&)Rt=Rt*A;

        A=A*A;

    }

    return Rt;

}

int main(){

    int n,Case;scanf("%d",&Case);

    Matrix A,T;

    T.a[][]=;T.a[][]=;

    T.a[][]=;T.a[][]=;

    for(;Case--;){

        scanf("%d%d",&n,&MOD);

        A=T^(n+n);

        LL ans=A.a[][];

        printf("%lld\n",ans%MOD);

    }

    return ;

}

巴特西

[HDU2855]Fibonacci Check-up

最新文章

热门文章