|
斐波那契数列是一个很神奇的东西，今天我们就来谈一谈它。 前言：本篇博客中会有大量的公式，每一个公式都会给出严谨的证明（证明方法都是最严谨的数学归纳法） 1.从特征方程说起前言：事实上，特征方程所求得的通项公式在实际应用中几乎不用。但是至少要了解，并会由递推式计算通项式。 特征方程：特征方程可以理解为求通项公式的一个工具。 
2.矩阵乘法
这里贴一下P1962的代码 #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.斐波那契数列的一个性质
证明2： 采用数学归纳法 设1至2*n都满足上述公式 （两个公式同时满足） 
所以原命题成立
证明3： 
那怎么证明上面这个式子呢？ 还是可以通过数学归纳法（只是这里提供了一个新的思路，后期也要用到这个定理） 
所以原命题成立 利用减半递推+记忆化，便可以AC 代码： #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;
}
4.另外一个性质我们先来看一道题目 P1306 斐波那契公约数 题目描述：
5.又一个性质
6.线段树众所周知，线段树可以处理很多关于区间的问题 （如果对线段树没有了解的，推荐洛谷日报浅谈线段树或者我的博客线段树1，线段树2，线段树3）
这是关于数列操作的一个表格。 注意到13操作：区间加斐波那契数列 这就是我们接下来要研究的 例题： CF446C 题意翻译:
代码： #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;
}
参考文献衷心的感谢以上的文献
|
