WA on #8
查看原帖
WA on #8
754311
zhangjiting楼主2024/6/25 17:18

求助,可能是模少了。

#include<bits/stdc++.h>
#define int long long
#define endl '\n'
#define debug(x) cout<<#x<<':'<<x<<endl
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
using namespace std;
const int N=1e5+5,mod=1e9+7;
int n,m;
int a[N];
int C[6][6];
int qpow(int a,int b){
	int res=1;
	while(b){
		if(b&1) (res*=a)%=mod;
		a=(a*a)%mod;
		b>>=1;
	}
	return res;
}
#define ls p<<1
#define rs p<<1|1
struct node{
	int l,r;
	int sum[6],hlp[6];
	int tag;
}tree[N<<2];
void push_up(int p){
	for(int i=0;i<=5;i++){
		tree[p].hlp[i]=(tree[ls].hlp[i]+tree[rs].hlp[i])%mod;
		tree[p].sum[i]=(tree[ls].sum[i]+tree[rs].sum[i])%mod;
	}
}
void insert(int p,int k){
	for(int i=0;i<=5;i++) tree[p].sum[i]=(tree[p].hlp[i]*k)%mod;
	tree[p].tag=k;
}
void push_down(int p){
	if(tree[p].tag==-1) return;
	insert(ls,tree[p].tag);
	insert(rs,tree[p].tag);
	tree[p].tag=-1;
}
void build(int p,int l,int r){
	tree[p].l=l,tree[p].r=r,tree[p].tag=-1;
	if(l==r){
		for(int i=0;i<=5;i++){
			tree[p].hlp[i]=qpow(l,i);
			tree[p].sum[i]=(tree[p].hlp[i]*a[l])%mod;
		}
		return;
	}
	int mid=(l+r)>>1;
	build(ls,l,mid);
	build(rs,mid+1,r);
	push_up(p);
}
void cover(int p,int l,int r,int k){
	if(l<=tree[p].l&&tree[p].r<=r){
		insert(p,k);
		return;
	}
	push_down(p);
	int mid=(tree[p].l+tree[p].r)>>1;
	if(l<=mid) cover(ls,l,r,k);
	if(r>mid) cover(rs,l,r,k);
	push_up(p);
}
int q[6];
void ask(int p,int l,int r,int k){
	if(l<=tree[p].l&&tree[p].r<=r){
		for(int i=0;i<=k;i++) (q[i]+=tree[p].sum[i])%=mod;
		return;
	}
	push_down(p);
	int mid=(tree[p].l+tree[p].r)>>1;
	if(l<=mid) ask(ls,l,r,k);
	if(r>mid) ask(rs,l,r,k);
}
signed main(){
	C[0][0]=1;
	for(int i=1;i<=5;i++){
		C[i][0]=1;
		for(int j=1;j<=i;j++) C[i][j]=(C[i-1][j]+C[i-1][j-1])%mod;
	}
	cin>>n>>m;
	for(int i=1;i<=n;i++) cin>>a[i];
	build(1,1,n);
	char op;
	for(int _=1,l,r,k;_<=m;_++){
		cin>>op>>l>>r>>k;
		if(op=='=') cover(1,l,r,k);
		else{
			int ans=0;
			memset(q,0,sizeof(q));
			ask(1,l,r,k);
			for(int i=0;i<=k;i++){
				ans=(ans+C[k][i]%mod*qpow(1-l,k-i)%mod*q[i]%mod)%mod;
			}
			cout<<ans<<endl;
		}
	}
	return 0;
}

2024/6/25 17:18
加载中...