斐波那契数列

简单的说就是f[n]=f[n-1]+f[n-2],f[1]=1,f[2]=1的一个数列。

1.根据递推式可以简单得出一个递归求法。

typedef long long ll;

ll f(ll x){
    if(x==1||x==2)return 1;
    else return f(x-1)+f(x-2);
}

int main(){
    ll n;
    scanf("%lld",&n);
    printf("%lld\n",f(n));
}

2.显然得出这样得一个递归式子出现了大量得重复计算，可以记忆化优化

typedef long long ll;
const int maxn=50;
ll f[maxn];

int main(){
    ll n;
    f[1]=f[2]=1;
    scanf("%lld",&n);
    for(int i=3;i<=n;i++){
        f[i]=f[i-1]+f[i-2];
    }
    printf("%lld\n",f[n]);
}

3.如果可以构造如图所示的矩阵，那么连续给矩阵乘以n个这样的矩阵就可以得到f。

 又因为矩阵满足结合律，所以可以用快速幂的方式，除去矩阵乘法的时间复杂度，O（logn）就可以得到斐波那契数列的第n项。

对于常系数线性齐次递推得到如下结论：

const int N=10,M=10;
long long a[10];
long long f[10];

struct matrix{
    int n,m;
    long long a[N][M];
    matrix(){//    初始化2*2的单位矩阵
        n=m=2;
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                a[i][j]=0;
            }
        }
        for(int i=0;i<n;i++){
            a[i][i]=1;
        }
    }
    void clear(){
        //memset(a,0,sizeof(a));
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                a[i][j]=0;
            }
        }
    }
    matrix operator+(const matrix &b)const{
        matrix tmp;
        tmp.clear();
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                tmp.a[i][j]=a[i][j]+b.a[i][j];
            }
        }
        return tmp;
    }
    matrix operator*(const matrix &b)const{
        matrix tmp;
        tmp.clear();
        for(int i=0;i<n;i++){
            for(int j=0;j<b.m;j++){
                for(int k=0;k<m;k++){
                    tmp.a[i][j]=((a[i][k]*b.a[k][j])+tmp.a[i][j]);
                }
            }
        }
        return tmp;
    }
};

matrix pow2(matrix A,int n){
    matrix B;
    while(n>0){
        if(n&1)B=B*A;
        A=A*A;
        n/=2;
    }
    return B;
}

long long solve(long long a[],long long f[],int n,int m){
    matrix A,B;
    A.clear();
    B.clear();
    A.n=B.n=n;
    A.m=n;
    B.m=1;
    for(int i=0;i<n-1;i++){
        A.a[i+1][i]=1;
    }
    for(int i=0;i<n;i++){
        B.a[i][0]=f[n-i-1];
        A.a[0][i]=a[n-i-1];
    }
    A=pow2(A,m);
    B=A*B;
    return B.a[n-1][0];
}

int main(){//求斐波那契数列第m项
    a[0]=1,a[1]=1;      //系数
    f[0]=0,f[1]=1;      //前n项
    int m;
    scanf("%d",&m);
    printf("%lld\n",solve(a,f,2,m));
    return 0;
}

4.模素数下求类斐波那契数得第n项（2019南昌网络赛 H. The Nth Item）

题意：Q个询问，每次求F(N)，但是N要用上一次询问的结果得到，结果mod998244353。

由待定系数法构造等比数列，求得F(n)=1/sqrt(17)*[((3+sqrt(17))/2)^n-((3-sqrt(17))/2)^n]。发现式子中有根号，要做得就是找到一个可以代替根号17得数，也就是17的二次剩余。

例如本题（2019南昌网络赛 H. The Nth Item）。假设二次剩余为x，那么公式里的全部sqrt(17)都可以换为x。F(n)=1/x*[((3+x)/2)^n-((3-x)/2)^n]。

对于一个数x，求(x^n)%p,显然可以用欧拉定理降幂为x^(n%phi(p)+phi(p)),本题p=998244353，那么指数n最大便为：1996488703。我们可以分块预处理,设N=sqrt(1996488703),把X[0]=x^0,X[1]=x^1,...,X[n]=x^N预处理出来，再把pre[0]=x^(0*N),pre[1]=x^(1*N),...,pre[N]=x^(N*N))。

求出来，这样对于一个询问n=a*N+b，我们其实就是求 (x^(a*N))*(x^b),即pre[a]*X[b]=pre[n/N]*X[n%N]。

using namespace std;
const int N = 5e4;
const ll mod = 998244353;
const ll inv17 = 438914993;//sqrt(17)的二次剩余
const ll x1 = 736044383;//(3+sqrt(17))/2
const ll x2 = 262199973;//(3-sqrt(17))/2
ll X1[N+10],X2[N+10],pre1[N+10],pre2[N+10];
ll ans,n,q,nn,res;
ll mo(ll x){ return x>=mod?x%mod:x; }
void Init(){
    pre1[0]=pre2[0]=X1[0]=X2[0]=1;
    for(int i=1;i<=N;i++)
        X1[i]=mo(X1[i-1]*x1),X2[i]=mo(X2[i-1]*x2);
    for(int i=1;i<=N;i++)
        pre1[i]=mo(pre1[i-1]*X1[N]),pre2[i]=mo(pre2[i-1]*X2[N]);
}
int main(){
    Init();
    scanf("%lld%lld",&q,&n);
    res=ans=0;
    while(q--){
        n^=(res*res);
        nn=n%(mod-1)+mod-1;
        res=mo(pre1[nn/N]*X1[nn%N])-mo(pre2[nn/N]*X2[nn%N]);
        res=mo(res+mod);
        res=mo(res*inv17);
        ans^=res;

    }
    printf("%lld\n",ans);
    return 0;
}

5.斐波那契数列又称为黄金分割数列

当n趋向于无穷大时，前一项与后一项的比值越来越逼近黄金分割0.618（或者说后一项与前一项的比值小数部分越来越逼近0.618）。

1÷1=1，1÷2=0.5，2÷3=0.666...，3÷5=0.6，5÷8=0.625…………，55÷89=0.617977……………144÷233=0.618025…46368÷75025=0.6180339886…...

证明：

f+f=f

两边除以f得：f/f+1=f/f

设f无穷大为x，n为无穷大，得：x+1=1/x

解得：x=（√5-1）/2

 

6.斐波那契数与杨辉三角

将杨辉三角左对齐，成如图所示排列，将同一斜行的数加起来，即得一数列1、1、2、3、5、8、……

公式表示如下：

f⑴=C(0,0)=1。

f⑵=C(1,0)=1。

f⑶=C(2,0)+C(1,1)=1+1=2。

f⑷=C(3,0)+C(2,1)=1+2=3。

f⑸=C(4,0)+C(3,1)+C(2,2)=1+3+1=5。

f⑹=C(5,0)+C(4,1)+C(3,2)=1+4+3=8。

f⑺=C(6,0)+C(5,1)+C(4,2)+C(3,3)=1+5+6+1=13。

……

f(n)=C(n-1,0)+C(n-2,1)+…+C(n-1-m,m) (m<=n-1-m)

 

7.其他公式

与集合子集:斐波那契数列的第n+2项同时也代表了集合{1,2,...,n}中所有不包含相邻正整数的子集个数。

 

奇数项求和：

偶数项求和:  

前n项求和：f-1

平方求和:     （值得一提的是这个公式也说明了用斐波那契数的前n项为边长的n个正方形可以构造出一个矩形）

隔项关系:

f(2n-2m-2)[f(2n)+f(2n+2)]=f(2m+2)+f(4n-2m) [ n〉m≥-1，且n≥1]

 

两倍项关系:f(2n)/f(n)=f(n-1)+f(n+1)

其他公式:

当且仅当，n%4==0时，f[n]%3==0等等。。。。。。

8.尾数循环

 

斐波那契数列的个位数：一个60步的循环

11235,83145,94370,77415,61785,38190,

99875,27965,16730,33695,49325,72910…

进一步，斐波那契数列的最后两位数是一个300步的循环，最后三位数是一个1500步的循环，最后四位数是一个15000步的循环，最后五位数是一个150000步的循环。

 

9.广义斐波那契数列

斐波那契—卢卡斯数列

卢卡斯数列1、3、4、7、11、18…，也具有斐波那契数列同样的性质。（我们可称之为斐波那契—卢卡斯递推：从第三项开始，每一项都等于前两项之和f(n) = f(n-1)+ f(n-2)。

卢卡斯数列的通项公式为 f(n)=[(1+√5)/2]^n+[(1-√5)/2]^n

这两个数列还有一种特殊的联系（如下表所示），F(n)*L(n)=F(2n)，及L(n)=F(n-1)+F(n+1)

 

斐波那契数列还让我们联想到佩尔数列：1，2，5，12，29，…，也有|2*2-1*5|=|5*5-2*12|=…=1。

佩尔数列Pn的递推规则：P1=1，P2=2，Pn=P(n-2)+2P(n-1).

---

据此类推到所有根据前两项导出第三项的通用规则：f(n) = f(n-1) * p + f(n-2) * q，称为广义斐波那契数列。

 

当p=1，q=1时，我们得到斐波那契—卢卡斯数列。

当p=1，q=2时，我们得到佩尔—勾股弦数（跟边长为整数的直角三角形有关的数列集合）。

当p=2，q=-1时，我们得到等差数列。其中f1=1，f2=2时，我们得到自然数列1，2，3，4…。自然数列的特征就是每个数的平方与前后两数之积的差为1（等差数列的这种差值称为自然特征）。

具有类似黄金特征、勾股特征、自然特征的广义——斐波那契数列p=±1。

当f1=1，f2=2，p=2，q=0 时，我们得到等比数列1，2，4，8，16……