HRY and fibonacci

C++14(g++5.4) 解法, 执行用时: 870ms, 内存消耗: 17628K, 提交时间: 2019-05-01 15:41:16

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod=1e8+7;
const int maxn=1e5+10;
struct matrix{
	int mat[2][2];
	matrix(){memset(mat,0,sizeof(mat));}
	matrix operator*(const struct matrix& rhs)const{
		matrix tmp;
		for(int i=0;i<2;i++)for(int j=0;j<2;j++)for(int k=0;k<2;k++)
			(tmp.mat[i][j]+=(1ll*mat[i][k]*rhs.mat[k][j])%mod)%=mod;
		return tmp;
	}
	matrix operator+(const struct matrix& rhs)const{
		matrix tmp;
		for(int i=0;i<2;i++)for(int j=0;j<2;j++)tmp.mat[i][j]=(mat[i][j]+rhs.mat[i][j])%mod;
		return tmp;
	}
	bool operator==(const struct matrix& rhs)const{
		for(int i=0;i<2;i++)for(int j=0;j<2;j++)if(mat[i][j]!=rhs.mat[i][j])return 0;
		return 1;
	}
};
matrix A,U,tmp;
matrix powm(matrix B,int b){
	matrix tmp=U;
	while(b){
		if(b&1)tmp=tmp*B;
		B=B*B;b>>=1;
	}
	return tmp;
}
matrix sum1[maxn<<2],add1[maxn<<2];
ll sum2[maxn<<2],add2[maxn<<2]; 
void pushup1(int rt){sum1[rt]=sum1[rt<<1]+sum1[rt<<1|1];}
void pushup2(int rt){sum2[rt]=(sum2[rt<<1]+sum2[rt<<1|1])%mod;}
void pushdown1(int rt){
	if(add1[rt]==U)return;
	sum1[rt<<1]=sum1[rt<<1]*add1[rt];sum1[rt<<1|1]=sum1[rt<<1|1]*add1[rt];
	add1[rt<<1]=add1[rt<<1]*add1[rt];add1[rt<<1|1]=add1[rt<<1|1]*add1[rt];
	add1[rt]=U;
}
void pushdown2(int rt,int l,int r){
	if(add2[rt]==0)return;
	int mid=(l+r)>>1;
	(sum2[rt<<1]+=add2[rt]*(mid-l+1)%mod)%=mod;(sum2[rt<<1|1]+=add2[rt]*(r-mid)%mod)%=mod;
	(add2[rt<<1]+=add2[rt])%=mod;(add2[rt<<1|1]+=add2[rt])%=mod;
	add2[rt]=0;
}
int x;
void build(int rt,int l,int r){
	add1[rt]=U,add2[rt]=0;
	if(l==r){
		scanf("%d",&x);
		sum1[rt]=powm(A,x+2);sum2[rt]=x+3;
		return ;
	}
	int mid=(l+r)>>1;
	build(rt<<1,l,mid);build(rt<<1|1,mid+1,r);
	pushup1(rt);pushup2(rt);
}
void update(int L,int R,ll x,int rt,int l,int r){
	if(L<=l&&r<=R){
		sum1[rt]=sum1[rt]*tmp;add1[rt]=add1[rt]*tmp;
		(sum2[rt]+=x*(r-l+1)%mod)%=mod;(add2[rt]+=x)%=mod;
		return ;
	}
	pushdown1(rt);pushdown2(rt,l,r);
	int mid=(l+r)>>1;
	if(L<=mid)update(L,R,x,rt<<1,l,mid);
	if(R>mid)update(L,R,x,rt<<1|1,mid+1,r);
	pushup1(rt);pushup2(rt); 
}
matrix query1(int L,int R,int rt,int l,int r){
	if(L<=l&&r<=R)return sum1[rt];
	pushdown1(rt);
	int mid=(l+r)>>1;
	matrix res;
	if(L<=mid)res=res+query1(L,R,rt<<1,l,mid);
	if(R>mid)res=res+query1(L,R,rt<<1|1,mid+1,r);
	return res;
}
ll query2(int L,int R,int rt,int l,int r){
	if(L<=l&&r<=R)return sum2[rt];
	pushdown2(rt,l,r);
	int mid=(l+r)>>1;
	ll res=0;
	if(L<=mid)(res+=query2(L,R,rt<<1,l,mid))%=mod;
	if(R>mid)(res+=query2(L,R,rt<<1|1,mid+1,r))%=mod;
	return res;
}
int main(){
	A.mat[0][0]=A.mat[0][1]=A.mat[1][0]=1;A.mat[1][1]=0;
	U.mat[0][0]=U.mat[1][1]=1;U.mat[0][1]=U.mat[1][0]=0;
	int n;scanf("%d",&n);
	build(1,1,n);
	int q;scanf("%d",&q);
	int t,l,r;ll x;
	while(q--){
		scanf("%d",&t);
		if(t==1){
			scanf("%d%d%lld",&l,&r,&x);
			tmp=powm(A,x);
			update(l,r,x,1,1,n);
		}else{
			scanf("%d%d",&l,&r);
			matrix t=query1(l,r,1,1,n);
			printf("%d\n",((t.mat[0][0]+t.mat[1][0])%mod-query2(l,r,1,1,n)+mod)%mod);
		}
	}
	return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 3725ms, 内存消耗: 103840K, 提交时间: 2019-04-28 20:12:33

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e5+10;
const int mod=1e8+7;
int n,q;
struct matrix
{
	ll a[4][4];
	matrix(){memset(a,0,sizeof a);}
	void init()
	{
		memset(a,0,sizeof a);
		for(int i=0;i<4;i++)a[i][i]=1;
	}
    void solve(){a[0][0]=a[0][1]=a[1][0]=a[2][0]=a[2][2]=a[3][2]=a[3][3]=1;}
}d[maxn<<2],b[maxn<<2],base;
matrix operator +( matrix a,matrix b)
{
	matrix res;
	for(int i=0;i<4;i++)
		for(int j=0;j<4;j++)
  		    res.a[i][j]=(a.a[i][j]+b.a[i][j])%mod;
	return res;
}
matrix operator *( matrix a,matrix b)
{
	matrix res;
	for(int i=0;i<4;i++)
		for(int j=0;j<4;j++)
			for(int k=0;k<4;k++)
				res.a[i][j]=(res.a[i][j]+a.a[i][k]*b.a[k][j])%mod;
	return res;
}

void build(int l,int r,int p)
{
	b[p].init();
	if(l==r) {d[p].init();return ;}
	int m=(l+r)>>1;build(l,m,p<<1);build(m+1,r,p<<1|1);
	d[p]=d[p<<1]+d[p<<1|1];
}
void update(int l,int r,int s,int t,int p,matrix c)
{
	if(l==s&&t==r){d[p]=d[p]*c,b[p]=b[p]*c;return;}
	int m=(s+t)>>1;
	if(r<=m)update(l,r,s,m,p<<1,c);
	else if(m<l)update(l,r,m+1,t,p<<1|1,c);
	else update(l,m,s,m,p<<1,c),update(m+1,r,m+1,t,p<<1|1,c);
	d[p]=(d[p<<1]+d[p<<1|1])*b[p];
}
matrix query(int l,int r,int s,int t,int p)
{
	if(l==s&&t==r)return d[p];
	int m=(s+t)>>1;
	if(r<=m) return query(l,r,s,m,p<<1)*b[p];
	else if(m<l) return query(l,r,m+1,t,p<<1|1)*b[p];
	else return b[p]*(query(l,m,s,m,p<<1)+query(m+1,r,m+1,t,p<<1|1));
}
matrix fpow(matrix a,ll b)
{
	matrix res;res.init();
	while(b)
	{
		if(b&1)res=res*a;
		a=a*a;
		b>>=1;
	}
	return res;
}
int main()
{
	matrix base;base.solve();
	scanf("%d",&n);build(1,n,1);
	for(int i=1;i<=n;i++){int x;scanf("%d",&x);update(i,i,1,n,1,fpow(base,x+2));}
	scanf("%d",&q);
    while(q--)
    {
    	int p;scanf("%d",&p);
    	if(p==1){int l,r,x; scanf("%d%d%d",&l,&r,&x),update(l,r,1,n,1,fpow(base,x));}
    	if(p==2){int l,r;scanf("%d%d",&l,&r),printf("%lld\n",query(l,r,1,n,1).a[3][1]);}
    }
	return 0;
}

详情