文件详细信息

下载本文件

本文件的大小为 2674 字节。

#include<cstdio>
void read(int&num){
	int ch=getchar();
	num=0;
	while(ch<48||ch>57)ch=getchar();
	while(ch>=48&&ch<=57)num=(num<<3)+(num<<1)+(ch^48),ch=getchar();
}
void write(int a){
	static int ch[25],cnt;
	if(a==0)putchar('0');
	cnt=0;
	while(a)ch[++cnt]=a%10|48,a/=10;
	while(cnt)putchar(ch[cnt--]);
}
typedef long long ll;
const int maxn=100005;
const ll P=1000000007;
int n,m,a[maxn],opt,ql,qr;
struct Matrix{
	ll a[2][2];
	Matrix(){
		a[0][0]=a[0][1]=a[1][0]=a[1][1]=0;
	}
}I,start,trans,x;
Matrix operator*(const Matrix a,const Matrix b){
	Matrix res;
	for(int i=0;i<2;i++)
		for(int j=0;j<2;j++)
			for(int k=0;k<2;k++)
				res.a[i][k]=(res.a[i][k]+a.a[i][j]*b.a[j][k])%P;
	return res;
}
Matrix qpow(Matrix a,ll x){
	Matrix res=I;
	while(x){
		if(x&1)res=res*a;
		a=a*a;
		x>>=1;
	}
	return res;
}
int Fibonacci(int x){
	if(x==0)return 0;
	if(x==1||x==2)return 1;
	return(start*qpow(trans,x-2)).a[0][0];
}
struct Seg{
	Matrix m,tag;
	bool e;
}T[maxn<<2];
void pushup(Matrix&ans,const Matrix a,const Matrix b){
	for(int i=0;i<2;i++)
		for(int j=0;j<2;j++)
			ans.a[i][j]=(a.a[i][j]+b.a[i][j])%P;
}
void pushdown(int u){
	if(!T[u].e)return;
	T[u<<1].m=T[u<<1].m*T[u].tag;
	if(T[u<<1].e)T[u<<1].tag=T[u<<1].tag*T[u].tag;
	else{
		T[u<<1].e=true;
		T[u<<1].tag=T[u].tag;
	}
	T[u<<1|1].m=T[u<<1|1].m*T[u].tag;
	if(T[u<<1|1].e)T[u<<1|1].tag=T[u<<1|1].tag*T[u].tag;
	else{
		T[u<<1|1].e=true;
		T[u<<1|1].tag=T[u].tag;
	}
	T[u].e=false;
}
void build(const int u,const int l,const int r){
	T[u].e=false;
	if(l==r){
		T[u].m.a[0][0]=Fibonacci(a[l]);
		T[u].m.a[0][1]=Fibonacci(a[l]-1);
		return;
	}
	pushdown(u);
	const int m=(l+r)>>1;
	build(u<<1,l,m);
	build(u<<1|1,m+1,r);
	pushup(T[u].m,T[u<<1].m,T[u<<1|1].m);
}
void modify(const int u,const int l,const int r){
	if(ql<=l&&r<=qr){
		T[u].m=T[u].m*x;
		if(!T[u].e){
			T[u].tag=x;
			T[u].e=true;
		}else T[u].tag=T[u].tag*x;
		return;
	}
	pushdown(u);
	const int m=(l+r)>>1;
	if(ql<=m)modify(u<<1,l,m);
	if(qr>m)modify(u<<1|1,m+1,r);
	pushup(T[u].m,T[u<<1].m,T[u<<1|1].m);
}
Matrix query(const int u,const int l,const int r){
	if(ql<=l&&r<=qr)return T[u].m;
	pushdown(u);
	const int m=(l+r)>>1;
	if(qr<=m)return query(u<<1,l,m);
	if(ql>m)return query(u<<1|1,m+1,r);
	Matrix ans;
	pushup(ans,query(u<<1,l,m),query(u<<1|1,m+1,r));
	return ans;
}
int main(){
	I.a[0][0]=I.a[1][1]=1;
	start.a[0][0]=start.a[0][1]=1;
	trans.a[0][0]=trans.a[0][1]=trans.a[1][0]=1;
	read(n),read(m);
	for(int i=1;i<=n;i++)read(a[i]);
	build(1,1,n);
	for(int i=1,tmp;i<=m;i++){
		read(opt),read(ql),read(qr);
		if(opt==1){
			read(tmp);
			x=qpow(trans,tmp);
			modify(1,1,n);
		}else write(query(1,1,n).a[0][0]),putchar('\n');
	}
	return 0;
}