斐波

C++(g++ 7.5.0) 解法, 执行用时: 2101ms, 内存消耗: 60824K, 提交时间: 2022-10-07 00:29:08

#include<bits/stdc++.h>
using namespace std ;
const int Matrix_Max = 3 ;
const int N = 1e5 + 5 ;
const int mod = 998244353 ;
int n,m ;
struct Matrix
{
	int c[Matrix_Max][Matrix_Max] ;
	Matrix() { memset(c,0,sizeof(c)) ; }
}F,tmp,I ;
struct Segment_Tree
{
	int l,r ;
	Matrix sum,mul,prem,nxtm ;
}t[N<<2] ;
int a[N] ;
Matrix operator *(Matrix A,Matrix B)
{
	Matrix C ;
	for(int i=0;i<Matrix_Max;++i)
	  for(int j=0;j<Matrix_Max;j++)
		for(int k=0;k<Matrix_Max;++k)
		{
			C.c[i][j]+=(long long)A.c[i][k]*B.c[k][j]%mod ;
			if(C.c[i][j]>=mod) C.c[i][j]-=mod ;
			if(C.c[i][j]<0) C.c[i][j]+=mod ;
		}
	return C ;
}
Matrix operator +(Matrix A,Matrix B)
{
	for(int i=0;i<Matrix_Max;++i)
	  for(int j=0;j<Matrix_Max;j++)
		{
			A.c[i][j]+=B.c[i][j] ;
			if(A.c[i][j]>=mod) A.c[i][j]-=mod ;
			if(A.c[i][j]<0) A.c[i][j]+=mod ;
		}
	return A ;
}
Matrix Mat_qsm(Matrix A,long long b)
{
	Matrix ans ;
	for(int i=0;i<Matrix_Max;++i) ans.c[i][i]=1 ;
	while(b)
	{
		if(b&1) ans=ans*A ;
		A=A*A ; b>>=1 ;
	}
	return ans ;
}
void pushup(int p)
{
	int ls=p<<1,rs=p<<1|1 ;
	t[p].mul=t[ls].mul*t[rs].mul ;
	t[p].prem=t[rs].prem*t[ls].mul+t[ls].prem ;
	t[p].nxtm=t[ls].nxtm*t[rs].mul+t[rs].nxtm ;
	t[p].sum=t[ls].sum+t[rs].sum+t[rs].prem*t[ls].nxtm ;
}
void build(int p,int l,int r)
{
	t[p].l=l ; t[p].r=r ;
	if(l==r)
	{
		t[p].sum=t[p].prem=t[p].nxtm=t[p].mul=I+Mat_qsm(tmp,a[l])  ;
		return ;
	}
	int mid=(l+r)>>1 ;
	build(p<<1,l,mid) ; build(p<<1|1,mid+1,r) ;
	pushup(p) ;
}
void modify(int p,int x,int v)
{
	if(t[p].l==t[p].r)
	{
		t[p].sum=t[p].prem=t[p].nxtm=t[p].mul=I+Mat_qsm(tmp,v)  ;
		return ;
	}
	int mid=(t[p].l+t[p].r)>>1 ;
	if(x<=mid) modify(p<<1,x,v) ;
	else modify(p<<1|1,x,v) ;
	pushup(p) ;
}
struct Ans
{
	Matrix mul,prem,nxtm,sum ;
};
Ans ask(int p,int l,int r)
{
	if(l<=t[p].l&&t[p].r<=r) return {t[p].mul,t[p].prem,t[p].nxtm,t[p].sum} ;
	int mid=(t[p].l+t[p].r)>>1 ;
	if(r<=mid) return ask(p<<1,l,r) ;
	else if(l>mid) return ask(p<<1|1,l,r) ;
	else
	{
		Ans L,R ;
		L=ask(p<<1,l,r) ; R=ask(p<<1|1,l,r) ;
		return {L.mul*R.mul,L.mul*R.prem+L.prem,R.mul*L.nxtm+R.nxtm,L.sum+R.sum+L.nxtm*R.prem} ;
	}
}
int main()
{
	scanf("%d%d",&n,&m) ;
	for(int i=1;i<=n;++i) scanf("%d",&a[i]) ;
	F.c[0][0]=0 ; F.c[1][0]=F.c[2][0]=1 ;
	tmp.c[0][0]=tmp.c[0][1]=2 ; tmp.c[0][2]=-1 ;
	tmp.c[1][0]=tmp.c[2][1]=1 ;
	I.c[0][0]=I.c[1][1]=I.c[2][2]=1 ;
	build(1,1,n) ;
	int op,l,r ;
	while(m--)
	{
		scanf("%d%d%d",&op,&l,&r) ;
		if(op==1) modify(1,l,r) ;
		else printf("%d\n",(ask(1,l,r).sum*F).c[0][0]) ;
	}
	return 0 ;
}

C++(clang++11) 解法, 执行用时: 1035ms, 内存消耗: 77592K, 提交时间: 2020-11-14 12:24:34

#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
const int M = 100005;
const int MOD = 998244353;
int read()
{
	int x=0,f=1;char c;
	while((c=getchar())<'0' || c>'9') {if(c=='-') f=-1;}
	while(c>='0' && c<='9') {x=(x<<3)+(x<<1)+(c^48);c=getchar();}
	return x*f;
}
int n,m;
struct Matrix
{
	int a[4][4];
	Matrix() {memset(a,0,sizeof a);}
	Matrix operator * (const Matrix &b) const
	{
		Matrix r;
		for(int i=1;i<=3;i++)
			for(int j=1;j<=3;j++)
				for(int k=1;k<=3;k++)
					r.a[i][k]=(r.a[i][k]+1ll*a[i][j]*b.a[j][k])%MOD;
		return r;
	}
	Matrix operator + (const Matrix &b) const
	{
		Matrix r;
		for(int i=1;i<=3;i++)
			for(int j=1;j<=3;j++)
				r.a[i][j]=(a[i][j]+b.a[i][j])%MOD;
		return r;
	}
	void print()
	{
		for(int i=1;i<=3;i++,puts(""))
			for(int j=1;j<=3;j++)
				printf("%d ",a[i][j]);
	}
}E,I,A;
struct node
{
	Matrix pr,sf,ml;int ans;
	node() {ans=0;}
	node operator + (const node &b) const
	{
		node r;
		r.ans=(1ll*ans+b.ans+(sf*b.pr).a[2][1])%MOD;
		r.pr=(pr)+(b.pr*ml);
		r.sf=(b.sf)+(sf*b.ml);
		r.ml=ml*b.ml;
		return r;
	}
}tr[4*M],tmp;
Matrix qkpow(Matrix a,int b)
{
	Matrix r=I;
	while(b>0)
	{
		if(b&1) r=r*a;
		a=a*a;
		b>>=1;
	}
	return r;
}
void insert(int i,int l,int r,int id,int v)
{
	if(l==r)
	{
		Matrix t=qkpow(A,v);
		tr[i].ans=t.a[2][1];
		tr[i].pr=tr[i].sf=tr[i].ml=I+t;
		return ;
	}
	int mid=(l+r)>>1;
	if(mid>=id) insert(i<<1,l,mid,id,v);
	else insert(i<<1|1,mid+1,r,id,v);
	tr[i]=tr[i<<1]+tr[i<<1|1];
}
void ask(int i,int l,int r,int L,int R)
{
	if(L>r || l>R) return ;
	if(L<=l && r<=R)
	{
		tmp=tmp+tr[i];
		return ;
	}
	int mid=(l+r)>>1;
	ask(i<<1,l,mid,L,R);
	ask(i<<1|1,mid+1,r,L,R);
}
signed main()
{
	I.a[1][1]=I.a[2][2]=I.a[3][3]=1;A.a[1][3]=2;
	A.a[1][1]=A.a[1][2]=A.a[2][1]=A.a[3][1]=A.a[3][3]=1;
	//qkpow(A,2).print();
	n=read();m=read();
	for(int i=1;i<=n;i++)
		insert(1,1,n,i,read());
	while(m--)
	{
		int id=read(),l=read(),r=read();
		if(id==1)
		{
			insert(1,1,n,l,r);
		}
		else
		{
			tmp.pr=tmp.sf=E;tmp.ml=I;tmp.ans=0;
			ask(1,1,n,l,r);
			printf("%d\n",tmp.ans);
		}
	}
}

详情