专栏文章

斐波那契数列

EErusel
算法·理论参与者 40已保存评论 45

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
45 条
当前快照
1 份
快照标识符
@mhz5tr0l
此快照首次捕获于
2025/11/15 01:56
4 个月前
此快照最后确认于
2025/11/29 05:25
3 个月前
查看原文
斐波那契数列是一个很神奇的东西，今天我们就来谈一谈它。
前言：本篇博客中会有大量的公式，每一个公式都会给出严谨的证明（证明方法都是最严谨的数学归纳法）

1.从特征方程说起

前言：事实上，特征方程所求得的通项公式在实际应用中几乎不用。但是至少要了解，并会由递推式计算通项式。
特征方程：特征方程可以理解为求通项公式的一个工具。
对于一阶递推式，形如：f[i]=p∗f[i−1]+xf[i]=p*f[i-1]+x
设qq，满足f[i]+q=p(f[i−1]+q)f[i]+q=p(f[i-1]+q)
展开得到f[i]=p∗f[i−1]+q∗(p−1)f[i]=p*f[i-1]+q*(p-1)
∴\therefore x=q∗(p−1)x=q*(p-1)
q=xp−1q=\frac{x}{p-1}
令g[i]=f[i]+qg[i]=f[i]+q
易知{g[i]g[i]}为等比数列，公比为pp
所以g[i]=(f[1]+q)∗pi−1g[i]=(f[1]+q)*p^{i-1}
f[i]=(f[1]+xp−1)∗pi−1−xp−1f[i]=(f[1]+\frac{x}{p-1})*p^{i-1}-\frac{x}{p-1}
对于二阶递推式，形如：f[i]=p∗f[i−1]+q∗f[i−2]f[i]=p*f[i-1]+q*f[i-2]
设u,vu,v，满足f[i]−u∗f[i−1]=v∗(f[i−1]−u∗f[i−2])f[i]-u*f[i-1]=v*(f[i-1]-u*f[i-2])
f[i]=(u+v)∗f[i−1]+u∗v∗f[i−2]f[i]=(u+v)*f[i-1]+u*v*f[i-2]
展开得到q=−u∗vq=-u*v
u2=p∗u+qu^{2}=p*u+q
这就是特征方程。
可以看到{f[i]−u∗f[i−1]f[i]-u*f[i-1]}是一个公比为v的等比数列
f[i]−u∗f[i−1]f[i−1]−u∗f[i−2]=v\frac{f[i]-u*f[i-1]}{f[i-1]-u*f[i-2]}=v
设f[1]−u∗f[0]=af[1]-u*f[0]=a
f[2]−u∗f[1]=a∗vf[2]-u*f[1]=a*v
……
f[n]−u∗f[n−1]=a∗vn−1f[n]-u*f[n-1]=a*v^{n-1}
通过计算得到
f[n]−un∗f[0]=a∗∑i=1n(un−1∗(vu)i−1)f[n]-u^{n}*f[0]=a*\sum^{n}_{i=1}(u^{n-1}*(\frac{v}{u})^{i-1})
对于u,vu,v的大小关系分两类讨论，就可以得到：
当两根不相同时，f[n]f[n]可以表示成A∗un+B∗vnA*u^{n}+B*v^{n}的形式
我们对于斐波那契数列递推式进行一遍上述操作
注意：这里是广义的斐波那契数列
即：a[1]=m,a[2]=k,a[n]=p∗a[n−1]+q∗a[n−2]a[1]=m,a[2]=k,a[n]=p*a[n-1]+q*a[n-2]
注：p2+4∗q>0,p,q≠0,n>2p^2+4*q>0,p,q\neq0,n>2
令a[n]=A∗αn+B∗βna[n]=A*\alpha^{n}+B*\beta^{n}
其中有α,β\alpha,\beta为方程x2=p∗x+qx^{2}=p*x+q（特征方程）的两根
前文保证（p2+4∗q>0p^{2}+4*q>0，即Δ>0\Delta>0）
不妨设α=p−p2+4∗q2\alpha=\frac{p-\sqrt{p^{2}+4*q}}{2}
β=p+p2+4∗q2\beta=\frac{p+\sqrt{p^{2}+4*q}}{2}
所以a[n]=A∗αn+B∗βn=A∗(p−p2+4∗q2)n+B∗(p+p2+4∗q2)na[n]=A*\alpha^{n}+B*\beta^{n}=A*(\frac{p-\sqrt{p^{2}+4*q}}{2})^{n}+B*(\frac{p+\sqrt{p^{2}+4*q}}{2})^{n}
上式对a[1],a[2]a[1],a[2]同样成立
将a[1],a[2]a[1],a[2]代入得
m=p−p2+4∗q2∗A+p+p2+4∗q2∗Bm=\frac{p-\sqrt{p^{2}+4*q}}{2}*A+\frac{p+\sqrt{p^{2}+4*q}}{2}*B
k=(p−p2+4∗q2)2∗A+(p+p2+4∗q2)2∗Bk=(\frac{p-\sqrt{p^{2}+4*q}}{2})^{2}*A+(\frac{p+\sqrt{p^{2}+4*q}}{2})^{2}*B
令p2+4∗q=y\sqrt{p^{2}+4*q}=y，则原方程为
m=p−y2∗A+p+y2∗Bm=\frac{p-y}{2}*A+\frac{p+y}{2}*B
k=(p−y2)2∗A+(p+y2)2∗Bk=(\frac{p-y}{2})^{2}*A+(\frac{p+y}{2})^{2}*B
令p−y2=s,p+y2=t,s+t=p,t−s=y\frac{p-y}{2}=s,\frac{p+y}{2}=t,s+t=p,t-s=y
m=s∗A+t∗Bm=s*A+t*B
k=s2∗A+t2∗Bk=s^{2}*A+t^{2}*B
A=(p+y)∗m−2∗k(p−y)∗yA=\frac{(p+y)*m-2*k}{(p-y)*y}
B=2∗k−(p−y)∗m(p+y)∗yB=\frac{2*k-(p-y)*m}{(p+y)*y}
所以a[n]=(p+y)∗m−2∗k(p−y)∗y∗(p−y2)n+2∗k−(p−y)∗m(p+y)∗y∗(p+y2)na[n]=\frac{(p+y)*m-2*k}{(p-y)*y}*(\frac{p-y}{2})^{n}+\frac{2*k-(p-y)*m}{(p+y)*y}*(\frac{p+y}{2})^{n}
读者可以把m=k=p=q=1m=k=p=q=1代入上式，就可以得到斐波那契的通项公式
f[n]=15∗[(1+52)n−(1−52)n]f[n]=\frac{1}{\sqrt{5}}*[(\frac{1+\sqrt{5}}{2})^{n}-(\frac{1-\sqrt{5}}{2})^{n}]
当p2−4∗q<=0p^{2}-4*q<=0时，读者可以自行思考一下，通项公式又会变成什么样

2.矩阵乘法

在具体实现中，如果题目要求数据范围过大，特征方程所求的通项公式不容易实现，暴力递推会TLE。
因此，我们采用矩阵乘法。
由于f[i]=f[i−1]+f[i−2]f[i]=f[i-1]+f[i-2]是一个很简单的递推式，它的矩阵也很简单
[1110]\begin{bmatrix}1&1\\1&0\end{bmatrix}
关于矩阵乘法的其他内容本文不再阐述，推荐洛谷日报：从零开始的矩阵乘法
时间复杂度：O(log(n))O(log(n))
模板题：P1962 斐波那契数列
这是一道关于斐波那契数列的模板题
观察数据范围得到，朴素的O(n)算法显然会TLE。显然用矩阵乘法。
同理，P1349也是同样的方法，但是递推矩阵不一样
[p1q0]\begin{bmatrix}p&1\\q&0\end{bmatrix}
这里贴一下P1962的代码
CPP
#include<bits/stdc++.h>

#define LL long long

using namespace std;

LL n;
const LL mod=1000000007;

struct matrix{
    LL a[5][5];
}ans;//矩阵 

void print(matrix a)
{
    for(int i=1;i<=2;i++)
    {
        for(int j=1;j<=2;j++)
            printf("%lld ",a.a[i][j]);
        printf("\n");
    }
}//打印矩阵 

matrix init()
{
    matrix ret;
    ret.a[1][1]=1,ret.a[1][2]=1;
    ret.a[2][1]=1,ret.a[2][2]=0;
    return ret;
}//递推矩阵 

matrix mul(matrix a,matrix b)
{
    matrix ret;
    for(int i=1;i<=2;i++)
    {
        for(int j=1;j<=2;j++)
        {
            ret.a[i][j]=0;
            for(int k=1;k<=2;k++)
                ret.a[i][j]+=(a.a[i][k]*b.a[k][j])%mod,ret.a[i][j]%=mod;
        }
    }
    //print(ret);
    return ret;
}//矩阵相乘 

matrix fast_power(matrix a,LL x)
{
    matrix ret;
    for(int i=1;i<=2;i++)
    {
        for(int j=1;j<=2;j++)
        {
            if(i==j)ret.a[i][j]=1;
            else ret.a[i][j]=0;
        }
    }//初始矩阵 
    while(x)
    {
        if(x&1)ret=mul(ret,a);
        a=mul(a,a);
        x>>=1;
    }
    return ret;
}//矩阵快速幂 

int main()
{
    scanf("%lld",&n);
    ans=fast_power(init(),n-1);
    printf("%lld\n",ans.a[1][1]);

    
    return 0;
}

3.斐波那契数列的一个性质

同时，我们可以采用另外一种做法：
f[2∗n]=f[n+1]2−f[n−1]2=(2∗f[n−1]+f[n])∗f[n]f[2*n]=f[n+1]^{2}-f[n-1]^{2}=(2*f[n-1]+f[n])*f[n]
f[2∗n+1]=f[n+1]2+f[n]2f[2*n+1]=f[n+1]^{2}+f[n]^{2}
在这里，我们证明一下这两个定理。
证明1：
直接采用通项公式(通项公式还是有用的)
设s=1+52,t=1−52s=\frac{1+\sqrt{5}}{2},t=\frac{1-\sqrt{5}}{2}
引理：
sn−tn=(1+5)n−(1−5)n2ns^{n}-t^{n}=\frac{(1+\sqrt{5})^{n}-(1-\sqrt{5})^{n}}{2^{n}}
把(1+5)n(1+\sqrt{5})^{n}和(1−5)n(1-\sqrt{5})^{n}进行多项式展开
……
这样的证明过于繁琐，读者可以亲自尝试一下。
证明2：
采用数学归纳法
设11至2∗n2*n都满足上述公式 （两个公式同时满足）
f[2∗n+1]=f[2∗n]+f[2∗n−1]=f[n+1]2−f[n−1]2+f[n]2+f[n−1]2=f[n+1]2+f[n]2f[2*n+1]=f[2*n]+f[2*n-1]=f[n+1]^{2}-f[n-1]^{2}+f[n]^{2}+f[n-1]^{2}=f[n+1]^{2}+f[n]^{2}
f[2∗n+2]=f[2∗n+1]+f[2∗n]f[2*n+2]=f[2*n+1]+f[2*n]
=f[n+1]2+f[n]2+f[n+1]2−f[n−1]2=f[n+1]^{2}+f[n]^{2}+f[n+1]^{2}-f[n-1]^{2}
=f[n+1]2+f[n+1]2+f[n]2−f[n−1]2=f[n+1]^{2}+f[n+1]^{2}+f[n]^{2}-f[n-1]^{2}
=f[n+1]2+f[n+1]2−2∗f[n+1]∗f[n]+f[n]2−f[n−1]2+2∗f[n+1]∗f[n]=f[n+1]^{2}+f[n+1]^{2}-2*f[n+1]*f[n]+f[n]^{2}-f[n-1]^{2}+2*f[n+1]*f[n]
=f[n+1]2+f[n−1]2−f[n−1]2+2∗f[n+1]∗f[n]=f[n+1]^{2}+f[n-1]^{2}-f[n-1]^{2}+2*f[n+1]*f[n]
=f[n+1]2+2∗f[n+1]∗f[n]=f[n+1]^{2}+2*f[n+1]*f[n]
=f[n+1]∗(2∗f[n]+f[n+1])=f[n+1]*(2*f[n]+f[n+1])
=f[n+2]2−f[n]2=f[n+2]^{2}-f[n]^{2}
所以原命题成立
证明3：
f[2∗n]=f[n+1]2−f[n−1]2f[2*n]=f[n+1]^{2}-f[n-1]^{2}
f[2∗n+1]=f[n+1]2+f[n]2f[2*n+1]=f[n+1]^{2}+f[n]^{2}
只需证明：
f[n+m]=f[m−1]∗f[n]+f[m]∗f[n+1]f[n+m]=f[m-1]*f[n]+f[m]*f[n+1]
若上式成立
f[2∗n]=f[n+n]f[2*n]=f[n+n]
=f[n−1]∗f[n]+f[n]∗f[n+1]=f[n-1]*f[n]+f[n]*f[n+1]
=f[n]∗(f[n+1]+f[n−1])=f[n]*(f[n+1]+f[n-1])
=f[n+1]2−f[n−1]2=f[n+1]^{2}-f[n-1]^{2}
f[2∗n+1]=f[n+(n+1)]f[2*n+1]=f[n+(n+1)]
=f[n−1]∗f[n+1]+f[n]∗f[n+2]=f[n-1]*f[n+1]+f[n]*f[n+2]
=f[n+1]2−f[n]∗f[n+1]+f[n]2+f[n]∗f[n+1]=f[n+1]^{2}-f[n]*f[n+1]+f[n]^2+f[n]*f[n+1]
=f[n+1]2+f[n]2=f[n+1]^{2}+f[n]^{2}
那怎么证明上面这个式子呢？
还是可以通过数学归纳法（只是这里提供了一个新的思路，后期也要用到这个定理）
设11至x−1x-1都两两满足f[n+m]=f[m−1]∗f[n]+f[m]∗f[n+1]f[n+m]=f[m-1]*f[n]+f[m]*f[n+1]
下证
f[1+x]=f[x−1]∗f[1]+f[x]∗f[2]f[1+x]=f[x-1]*f[1]+f[x]*f[2]
f[2+x]=f[x−1]∗f[2]+f[x]∗f[3]f[2+x]=f[x-1]*f[2]+f[x]*f[3]
…………
f[x−1+x]=f[x−1]∗f[x−1]+f[x]∗f[x]f[x-1+x]=f[x-1]*f[x-1]+f[x]*f[x]
对于任意的f[p+x]f[p+x]
都有f[p+x]=f[(p−1)+x]+f[(p−2)+x]f[p+x]=f[(p-1)+x]+f[(p-2)+x]
=f[p+(x−1)]+f[(p−1)+(x−1)]=f[p+(x-1)]+f[(p-1)+(x-1)]
=f[x−2]∗f[p]+f[x−1]∗f[p+1]+f[x−2]∗f[p−1]+f[x−1]∗f[p]=f[x-2]*f[p]+f[x-1]*f[p+1]+f[x-2]*f[p-1]+f[x-1]*f[p]
=f[x−2]∗f[p+1]+f[x−1]∗f[p+2]=f[x-2]*f[p+1]+f[x-1]*f[p+2]
=f[x]∗f[p+1]−f[x−1]∗f[p+1]+f[x−1]∗f[p]+f[x−1]∗f[p+1]=f[x]*f[p+1]-f[x-1]*f[p+1]+f[x-1]*f[p]+f[x-1]*f[p+1]
=f[x]∗f[p+1]+f[x−1]∗f[p]=f[x]*f[p+1]+f[x-1]*f[p]
所以原命题成立
利用减半递推+记忆化，便可以AC
代码：
CPP
#pragma GCC diagnostic error "-std=c++14"
#pragma GCC target("avx")
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")//强行优化

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

ll n;
const ll mod=1e9+7;

map<ll,ll>f;

ll solve(ll x)
{
	if(x==0)return 0;
	if(x==1)return 1;
	if(x==2)return 1;//边界条件
	ll y=(x>>1),f1=f[y-1]?f[y-1]:solve(y-1),f2=f[y]?f[y]:solve(y),f3=f[y+1]?f[y+1]:solve(y+1);//处理f[y-1],f[y],f[y+1]
	if(x&1)return (f[x]=(f3*f3+f2*f2+mod)%mod);//如果为奇数
	else return (f[x]=(f3*f3-f1*f1+mod)%mod);//如果为偶数
   //套用公式+记忆化，把答案丢进map里
}

inline ll read()
{
    ll x=0,f=1;char ch=getchar();
    while(ch>'9'||ch<'0') { if(ch=='-') f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') { x=x*10+ch-'0';ch=getchar();}
    return x*f;
}

int main()
{
	scanf("%lld",&n);
	printf("%lld\n",(solve(n)+mod)%mod);//疯狂取模
	
	return 0;
}
时间复杂度：递归O(log(n))O(log(n)),mapO(log(n))O(log(n))总时间复杂度为O(log2(n))O(log^{2}(n))
这里提到了这两个公式，顺便再拓展一个：
f[3∗n]=f[n+1]3+f[n]3−f[n−1]3f[3*n]=f[n+1]^{3}+f[n]^{3}-f[n-1]^{3}
有兴趣的读者可以亲自证明一下。
当然啦，它对应的也有两个公式。
上述的数学归纳法的证明必须有几个公式互相依靠。

4.另外一个性质

我们先来看一道题目
P1306 斐波那契公约数
题目描述：
对于FibonacciFibonacci数列：1,1,2,3,5,8,13......大家应该很熟悉吧~~~
但是现在有一个很“简单”问题：第nn项和第mm项的最大公约数是多少？(n⩽1e9n\leqslant1e9)
本题要求gcd(f[n],f[m])gcd(f[n],f[m])
我们可以用矩阵乘法把f[n],f[m]f[n],f[m]都算出来
题目要求对1e8取模，所以做gcd的时候就会遇到问题。
斐波那契数列中还有一个性质：
gcd(f[n],f[m])=f[gcd(n,m)]gcd(f[n],f[m])=f[gcd(n,m)]
证明：
若证gcd(f[n],f[m])=f[gcd(n,m)]gcd(f[n],f[m])=f[gcd(n,m)]
即证gcd(f[n+m],f[n])=gcd(f[m],f[n])gcd(f[n+m],f[n])=gcd(f[m],f[n])
gcd(f[n+m],f[n])gcd(f[n+m],f[n])
=gcd(f[n+1]f[m]+f[n]f[m−1],f[n])=gcd(f[n+1]f[m]+f[n]f[m-1],f[n])
=gcd(f[n+1]f[m],f[n])=gcd(f[n+1]f[m],f[n])
=gcd(f[n+1],f[n])∗gcd(f[m],f[n])=gcd(f[n+1],f[n])*gcd(f[m],f[n])
=gcd(f[m],f[n])=gcd(f[m],f[n])
得证
有了这个性质之后
题目<==><==>求f[gcd(n,m)]mod1e8f[gcd(n,m)] mod 1e8
矩阵乘法即可

5.又一个性质

先看一道题P3986
题目描述：
定义一个数列：
f(0)=a,f(1)=b,f(n)=f(n−1)+f(n−2)f(0) = a, f(1) = b, f(n) = f(n - 1) + f(n - 2)
其中a,ba, b均为正整数，n≥2n≥2。
问有多少种 (a,b)(a, b)，使得kk出现在这个数列里，且不是前两项。
由于答案可能很大，你只需要输出答案模109+710^{9}+7的结果即可。
数据范围：
1≤k≤1091≤k≤10^{9}
简单分析得：
设g[0]=1,g[1]=1,g[n]=g[n−1]+g[n−2](n≥2)g[0]=1,g[1]=1,g[n]=g[n-1]+g[n-2](n≥2)(就是斐波那契数列)
显然有f[n]=g[n−1]∗a+g[n−2]∗b(n≥2)f[n]=g[n-1]*a+g[n-2]*b(n≥2)
问f[n]=kf[n]=k的情况数
由于1≤k≤1091≤k≤10^{9}，所以nn的取值范围也很小，只要暴力枚举g[n−1],g[n−2]g[n-1],g[n-2]，然后对于每一种情况用exgcdexgcd解一个不定方程即可
这里介绍另一种方法
先介绍一个性质
f[i]f[i−1]−f[i+1]f[i−2]=(−1)if[i]f[i-1]-f[i+1]f[i-2]=(-1)^{i} (f[0]=0,f[−1]=1)(f[0]=0,f[-1]=1)
还是用数学归纳法
另g[i]=f[i]f[i−1]−f[i+1]f[i−2]g[i]=f[i]f[i-1]-f[i+1]f[i-2]
当i=0i=0时，原式显然成立
g[i]=(f[i−1]+f[i−2])f[i−1]−(f[i]+f[i−1])f[i−2]g[i]=(f[i-1]+f[i-2])f[i-1]-(f[i]+f[i-1])f[i-2] =f[i−1]2−f[i]f[i−2]=f[i-1]^{2}-f[i]f[i-2]
设i=ki=k时，原命题成立
g[k]=f[k−1]2−f[k]f[k−2]g[k]=f[k-1]^{2}-f[k]f[k-2]
g[k+1]=f[k]2−f[k+1]f[k−1]g[k+1]=f[k]^{2}-f[k+1]f[k-1]
g[k]+g[k+1]=0g[k]+g[k+1]=0
∵g[k]=−1k\because g[k]=-1^{k}
∴g[k+1]=−1k+1\therefore g[k+1]=-1^{k+1}
两式相加得0
所以原命题成立
根据上式
方程g[n−1]∗a+g[n−2]∗b=kg[n-1]*a+g[n-2]*b=k就有通解x=k∗−1n−2f[n−3]x=k*-1^{n-2}f[n-3]
求得一个解之后，其余的就好求了

6.线段树

众所周知，线段树可以处理很多关于区间的问题
（如果对线段树没有了解的，推荐洛谷日报浅谈线段树或者我的博客线段树1，线段树2，线段树3）
数列操作
这是关于数列操作的一个表格。
注意到13操作：区间加斐波那契数列
这就是我们接下来要研究的
例题：
CF446C
题意翻译:
题面大意：给出一个数列，每次可以选取一个区间，按顺序加上第ii个FibonacciNumbersFibonacci Numbers(斐波那契数)进行更新，也可以查询某一个区间的总和。
这题虽然是黑题，其实并不难
我们只要思考几件事：
1.线段树的标记下传（pushdownpushdown）能不能在O(1)O(1)内完成
2.线段树更新sumsum能不能在O(1)O(1)内完成
对于1，前文提到f[n]=g[n−1]∗a+g[n−2]∗bf[n]=g[n-1]*a+g[n-2]*b
对于2，这里再提一个性质：
令s[i]=∑i=1nf[i]s[i]=\sum_{i=1}^{n}f[i]
s[i]=f[n+2]−f[2]s[i]=f[n+2]-f[2]
这个定理的证明
还是用数学归纳法。。。
显然当i=1i=1时，原命题成立
设i=ki=k时，原命题成立。
s[k+1]=s[k]+f[k+1]=f[k+2]−f[2]+f[k+1]=f[k+3]−f[2]s[k+1]=s[k]+f[k+1]=f[k+2]-f[2]+f[k+1]=f[k+3]-f[2]
∴\therefore 原命题成立
便能实现再O(1)O(1)内完成更新sumsum了
代码：
CPP
#include<bits/stdc++.h>

#define rd(x) x=read()
#define N 300005
#define ls rt<<1
#define rs rt<<1|1

using namespace std;

typedef long long ll;

ll n,m;
struct T{
	ll f1,f2,v;
}t[N*20];
ll a[N],f[N],sum[N];
const ll mod=1e9+9;

inline ll read()
{
    ll f=1,x=0;char s=getchar();
    while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();}
    while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();}
    return x*f;
}

void init()
{
	f[1]=1,f[2]=1;
	for(ll i=3;i<=n+1;i++)f[i]=(f[i-2]+f[i-1])%mod;
}//预处理斐波那契

void pushup(ll rt,ll pos)
{
	t[rt].f1%=mod,t[rt].f2%=mod;
	t[rt].v=t[ls].v+t[rs].v+(t[rt].f1*f[pos]+t[rt].f2*f[pos+1]-t[rt].f2),t[rt].v%=mod;
}//更新rt

void pushdown(ll rt,ll l,ll r)
{
	if(t[rt].f1==0&&t[rt].f2==0)return ;
	ll mid=(l+r)>>1;
	t[ls].f1+=t[rt].f1,t[rs].f1+=t[rt].f1*f[mid-l]+t[rt].f2*f[mid-l+1];
	t[ls].f2+=t[rt].f2,t[rs].f2+=t[rt].f1*f[mid-l+1]+t[rt].f2*f[mid-l+2];
	t[rt].f1=t[rt].f2=0;
	pushup(ls,mid-l+1),pushup(rs,r-mid); 
} //标记下传

void update(ll rt,ll l,ll r,ll L,ll R)
{
	if(L<=l&&r<=R)//边界条件
	{
		t[rt].f1+=f[l-L+1];
		t[rt].f2+=f[l-L+2];
		t[rt].f1%=mod,t[rt].f2%=mod;
		pushup(rt,r-l+1);
		return ;
	}
	pushdown(rt,l,r);
	ll mid=(l+r)>>1;
	if(L<=mid)update(ls,l,mid,L,R);
	if(mid<R)update(rs,mid+1,r,L,R);
	pushup(rt,r-l+1);
}//区间加斐波那契数列

ll query(ll rt,ll l,ll r,ll L,ll R)
{
	if(L<=l&&r<=R)return t[rt].v;
	pushdown(rt,l,r);
	ll res=0;
	ll mid=(l+r)>>1;
	if(L<=mid)res+=query(ls,l,mid,L,R);
	if(mid<R)res+=query(rs,mid+1,r,L,R);
	return res%mod;
}//查询和

int main()
{
	rd(n),rd(m);
	init();
	for(ll i=1;i<=n;i++)rd(a[i]),sum[i]=sum[i-1]+a[i];//预处理前缀和
	while(m--)
	{
		ll opt,l,r;
		rd(opt),rd(l),rd(r);
		if(opt==1)update(1,1,n,l,r);
		else printf("%lld\n",(query(1,1,n,l,r)+sum[r]-sum[l-1]+mod)%mod);
	}
	
		
    return 0;
}

7.∑i=1nf[i]∗i\sum_{i=1}^{n}f[i]*i

∑i=1nf[i]∗i=n∗f[n+2]−f[n+3]+2\sum_{i=1}^{n}f[i]*i=n*f[n+2]-f[n+3]+2
命运驱使着我用数学归纳法。。。
当n=1n=1时，原命题显然成立
设n=kn=k时，原命题成立
令s[i]=∑i=1nf[i]∗is[i]=\sum_{i=1}^{n}f[i]*i
s[k+1]=s[k]+f[k+1]∗(k+1)s[k+1]=s[k]+f[k+1]*(k+1)
=k∗f[k+2]−f[k+3]+2+f[k+1]∗(k+1)=k*f[k+2]-f[k+3]+2+f[k+1]*(k+1)
=k∗f[k+3]−f[k+3]+2+f[k+1]=k*f[k+3]-f[k+3]+2+f[k+1]
=k∗f[k+3]−f[k+2]+2=k*f[k+3]-f[k+2]+2
所以原命题成立
然后用矩阵乘法计算即可。

参考文献

衷心的感谢以上的文献

推荐文献

完结撒花！

后记：

在翻阅洛谷日报的时候，我发现很多的算法都已经介绍了，
唯独没有神奇的斐波那契数列，于是心血来潮，写下了这篇文章。

评论

共 45 条评论，欢迎与作者交流。

正在加载评论...