Description
有一个长为(n)的数列(a_{1},a_{2}...a_{n}),你需要对这个数列维护如下两种操作:
- (1space l space rspace x) 表示将数列中的(a_{l},a_{l+1}...a_{r-1},a_{r})加上(x)
- (2space lspace r) 表示要你求出(sum_{i=l}^{r}fib(a_{i}))对(10^9+7)取模后的结果
fib(x)fib(x)表示的是斐波那契的第(x)项,(fib(1)=1,fib(2)=1,fib(i)=fib(i-1)+fib(i-2)(i>2))
线段树维护矩阵。
emmm,吓人。
看着题解码
有些懵逼这种矩乘写法。
为啥最普通的矩阵乘法不行？？？
调了半天发现快速幂里面的(for)后面加了个分号？？
区间修改操作即为原矩阵乘上转移矩阵的(x)次方。
话说和我推的式子貌似又不是很一样？？？QwQ？
代码
#include<iostream>
#include<cstdio>
#include<algorithm>
#define int long long
#define R register
using namespace std;
const int mod=1e9+7;
const int gz=100001;
inline void in(R int &x)
{
int f=1;x=0;char s=getchar();
while(!isdigit(s)){if(s=='-')f=-1;s=getchar();}
while(isdigit(s)){x=x*10+s-'0';s=getchar();}
x*=f;
}
int n,m,val[gz];
struct Matrix
{
int m[4][4];
inline void clear()
{
for(R int i=0;i<4;i++)
for(R int j=0;j<4;j++)
m[i][j]=0;
}
inline void pre()
{
for(R int i=0;i<4;i++)m[i][i]=1;
}
inline bool emp()
{
return (m[1][1]==1 and m[1][2]==0 and m[2][1]==0 and m[2][2]==1);
}
Matrix operator *(const Matrix &a)const
{
Matrix tmp;tmp.clear();
for(R int i=1;i<=2;i++)
for(R int k=1;k<=2;k++)
for(R int j=1;j<=2;j++)
tmp.m[i][j]=(tmp.m[i][j]+m[i][k]*a.m[k][j])%mod;
return tmp;
}
friend Matrix operator +(Matrix a,Matrix b)
{
Matrix tmp;tmp.clear();
for(R int i=1;i<=2;i++)
for(R int j=1;j<=2;j++)
tmp.m[i][j]=(a.m[i][j]+b.m[i][j])%mod;
return tmp;
}
};
Matrix fir,fb;
Matrix tr[gz<<2],tg[gz<<2];
#define ls o<<1
#define rs o<<1|1
inline void up(R int o)
{
tr[o]=tr[ls]+tr[rs];
}
inline Matrix ksm(R Matrix a,R int y)
{
Matrix res;res.clear();res.pre();
for(;y;y>>=1,a=a*a)
if(y&1)res=res*a;
return res;
}
void build(R int o,R int l,R int r)
{
tr[o].clear();tg[o].clear();tg[o].pre();
if(l==r)
{
tr[o]=fir*ksm(fb,val[l]-1);
return ;
}
R int mid=(l+r)>>1;
build(ls,l,mid);
build(rs,mid+1,r);
up(o);
}
inline void down(R int o)
{
if(tg[o].emp())return;
tr[ls]=tr[ls]*tg[o];
tr[rs]=tr[rs]*tg[o];
tg[ls]=tg[ls]*tg[o];
tg[rs]=tg[rs]*tg[o];
tg[o].clear();
tg[o].pre();
}
void change(R int o,R int l,R int r,R int x,R int y,R Matrix k)
{
if(x<=l and y>=r)
{
tr[o]=tr[o]*k;
tg[o]=tg[o]*k;
return;
}
down(o);
R int mid=(l+r)>>1;
if(x<=mid) change(ls,l,mid,x,y,k);
if(y>mid)change(rs,mid+1,r,x,y,k);
up(o);
}
inline Matrix query(R int o,R int l,R int r ,R int x,R int y)
{
if(x<=l and y>=r)return tr[o];
down(o);
Matrix res;res.clear();
R int mid=(l+r)>>1;
if(x<=mid) res=res+query(ls,l,mid,x,y);
if(y>mid) res=res+query(rs,mid+1,r,x,y);
return res;
}
signed main()
{
fb.clear(),fir.clear();
fir.m[1][1]=fir.m[1][2]=1;fir.m[2][1]=fir.m[2][2]=0;
fb.m[1][1]=fb.m[1][2]=fb.m[2][1]=1;fb.m[2][2]=0;//转移矩阵
in(n),in(m);
for(R int i=1;i<=n;i++)in(val[i]);
build(1,1,n);
for(R int opt,l,r,x;m;m--)
{
in(opt);
switch(opt)
{
case 1:in(l),in(r),in(x);change(1,1,n,l,r,ksm(fb,x));break;
case 2:in(l),in(r),printf("%lld
",query(1,1,n,l,r).m[1][2]%mod);break;
}
}
}