Sasha and Array

维护斐波那契数列

乘上一个矩阵可以快速得出斐波那契数列

这个比较简单~

cpp

#include<bits/stdc++.h>
#define close std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;
typedef long long ll;
const ll MAXN =  3e5+7;
const ll mod = 1e9+7;
const ll inf = 0x3f3f3f3f;
const ll M=2;
#define int ll
struct matrix {
	ll x[M+1][M+1];
	matrix() {
		memset(x,0,sizeof(x));
	}
};
matrix multiply(matrix &a,matrix &b) {
	matrix c;
	for(int i=1; i<=M; i++)
		for(int j=1; j<=M; j++)
			for(int k=1; k<=M; k++)
				c.x[i][j]+=a.x[i][k]*b.x[k][j]%mod;
	return c;
}
matrix mpow(matrix a,ll m) { //矩阵a的m次方
	matrix res;
	for(int i=1; i<=M; i++) res.x[i][i]=1; //单位矩阵
	while(m>0) {
		if(m&1) res=multiply(res,a);
		a=multiply(a,a);
		m>>=1;
	}
	return res;
}
void Debug(matrix &a) {
	for(int i=1; i<=M; i++) {
		for(int j=1; j<=M; j++) cout<<a.x[i][j]<<" ";
		cout<<'\n';
	}
}
struct Info {
	matrix sum;
};
Info operator +(const Info &a,const Info &b) {
	Info c;
	c.sum.x[1][1]=(a.sum.x[1][1]+b.sum.x[1][1])%mod;
	c.sum.x[1][2]=(a.sum.x[1][2]+b.sum.x[1][2])%mod;
	c.sum.x[2][1]=(a.sum.x[2][1]+b.sum.x[2][1])%mod;
	c.sum.x[2][2]=(a.sum.x[2][2]+b.sum.x[2][2])%mod;
	return c;
}
matrix A;
int a[MAXN];
struct node {
	int lazy;
	Info val;
} seg[MAXN<<2];
void up(int id) {
	seg[id].val=seg[id<<1].val+seg[id<<1|1].val;
}
void settag(int id,int l,int r,int tag) {
	matrix tmp=mpow(A,tag);
	seg[id].val.sum=multiply(seg[id].val.sum,tmp);
	seg[id].lazy+=tag;
}
void down(int id,int l,int r) {
	if(seg[id].lazy==0) return;
	int mid=l+r>>1;
	settag(id<<1,l,mid,seg[id].lazy);
	settag(id<<1|1,mid+1,r,seg[id].lazy);
	seg[id].lazy=0;
}
void build(int id,int l,int r) {
	if(l==r) {
		seg[id].val.sum.x[1][1]=1;
		seg[id].val.sum.x[2][2]=1;
		matrix tmp=mpow(A,a[l]-1);
		seg[id].val.sum=multiply(seg[id].val.sum,tmp);
		seg[id].lazy=0;
		return;
	}
	int mid = l+r>>1;
	build(id<<1,l,mid);
	build(id<<1|1,mid+1,r);
	up(id);
}
void modify(int id,int l,int r,int ql,int qr,int val) {
	if (ql<=l&&r<=qr) {
		settag(id,l,r,val);
		return;
	}
	down(id,l,r);
	int mid =(l+r) >> 1;
	if (qr<=mid)
		modify(id <<1,l,mid,ql,qr,val);
	else if (ql>mid)
		modify(id<<1|1, mid+1,r,ql,qr,val);
	else {
		modify(id<<1,l,mid,ql,qr,val);
		modify(id<<1|1,mid+1,r,ql,qr,val);
	}
	up(id);
}
Info query(int id,int l ,int r,int ql,int qr) {
	if(ql<=l&&r<=qr) {
		return seg[id].val;
	}
	down(id,l,r);
	int mid=l+r>>1;
	if(qr<=mid) return query(id<<1,l,mid,ql,qr);
	else if(ql>mid) return query(id<<1|1,mid+1,r,ql,qr);
	else return query(id<<1,l,mid,ql,qr)+query(id<<1|1,mid+1,r,ql,qr);
}
void solve() {
	int n,m;
	cin>>n>>m;
	for(int i=1; i<=n; i++) {
		cin>>a[i];
	}
	A.x[1][1]=1;
	A.x[1][2]=1;
	A.x[2][1]=1;
	A.x[2][2]=0;
	build(1,1,n);
	while(m--) {
		int op;
		cin>>op;
		if(op==1) {
			int l,r,x;
			cin>>l>>r>>x;
			modify(1,1,n,l,r,x);
		} else {
			int l,r;
			cin>>l>>r;
			matrix tmp =query(1,1,n,l,r).sum;
			matrix ans;
			ans.x[1][1]=1;
			ans=multiply(ans,tmp);
			cout<<ans.x[1][1]%mod<<'\n';
		}
	}
}
signed main() {
	solve();
}

*这题时间卡的好死 感觉写再丑点就要t了