首页 > 代码库 > bzoj4597: [Shoi2016]随机序列

bzoj4597: [Shoi2016]随机序列

2024-08-12 04:30:18   217人阅读

容易推出答案为$\sum_{i=1}^{n-1}2*3^{n-i-1}\prod_{j=1}^{i}a_{j}+\prod_{j=1}^{n}a_{j}$。然后随便怎么维护都行，我没多想直接用的区间乘区间和来搞，其实可以直接维护乘积和答案。

#include<cstdio>#define Z int l=1,int r=n,int k=1#define N 100005#define M (l+r>>1)#define P (k<<1)#define S (k<<1|1)#define L l,M,P#define R M+1,r,Sint n,m,s,t;typedef long long ll;const ll p=1e9+7;ll f[N],e[N],a[N];ll u[N*4],v[N*4];void apply(ll a,int k){	u[k]=u[k]*a%p;	v[k]=v[k]*a%p;}void devolve(int k){	if(v[k]!=1){		apply(v[k],P);		apply(v[k],S);		v[k]=1;	}}void update(int k){	u[k]=(u[P]+u[S])%p;}void build(Z){	if(l==r)		u[k]=a[l];	else{		build(L);		build(R);		update(k);	}	v[k]=1;}void amend(ll a,int s,int t,Z){	if(s<=l&&r<=t)		apply(a,k);	else{		devolve(k);		if(s<=M)			amend(a,s,t,L);		if(t>M)			amend(a,s,t,R);		update(k);	}}ll pow(ll u,ll k){	ll a=1;	for(;k;k>>=1){		if(k%2)a=a*u%p;		if(k/2)u=u*u%p;	}	return a;}int main(){	scanf("%d%d",&n,&m);	for(int i=1;i<=n;++i)		scanf("%lld",e+i);	f[f[0]=a[0]=1]=2;	for(int i=2;i<n;++i)		f[i]=f[i-1]*3%p;	for(int i=1;i<=n;++i)		a[i]=a[i-1]*e[i]%p;	for(int i=1;i<=n;++i)		a[i]=a[i]*f[n-i]%p;	build();	while(m--){		scanf("%d%d",&s,&t);		t=t*pow(e[s],p-2)%p;		amend(t,s,n);		e[s]=e[s]*t%p;		printf("%lld\n",u[1]);	}}

　　

bzoj4597: [Shoi2016]随机序列


联系
我们