P4247

样例输出第二个数对了，但是第一个输出随机数

调吐了已经

代码：

#include<cstdio>
#include<cstring>
#define int long long
const int M=500010;
const int mod=19940417;
int min(int A,int B){
	return A<B?A:B;
}

int n,q,x[M],C[M][21];
void calc(){//随机数
	C[0][0]=1;
	for(int i=1;i<M;i++){
		C[i][0]=1;
		for(int j=1;j<=min(20,i);j++) C[i][j]=(C[i-1][j]+C[i-1][j-1])%mod;
	}
}

struct node{
	int l,r,len,add,f[21];
	bool rev;
}tr[M<<2];
void pushup(int k){
	memset(tr[k].f,0,sizeof tr[k].f);
	for(int i=0;i<=min(20,tr[k<<1].len);i++)
		for(int j=0;i+j<=20 and j<=tr[k<<1|1].len;j++) tr[k].f[i+j]+=tr[k<<1].f[i]*tr[k<<1|1].f[j];
	for(int i=0;i<=20 and i<=tr[k].len;i++) tr[k].f[i]%=mod;
}
void build(int k,int l,int r){
	tr[k].l=l,tr[k].r=r,tr[k].len=r-l+1;
	tr[k].add=0,tr[k].rev=false;
	if(l==r){
		tr[k].f[0]=1,tr[k].f[1]=(x[l]%mod+mod)%mod;
		return;
	}
	int mid=(l+r)>>1;
	build(k<<1,l,mid);
	build(k<<1|1,mid+1,r);
	pushup(k);
}
void pushadd(int k,int v){//下传加法懒标记
	if(!k or !v) return;
	int pow[21];pow[0]=1;
	for(int i=1;i<=min(20,tr[k].len);i++) pow[i]=(pow[i-1]*v)%mod;
	for(int i=min(20,tr[k].len);i;i--)
		for(int j=0;j<i;j++) tr[k].f[i]=(tr[k].f[i]+tr[k].f[j]*pow[i-j]%mod*C[tr[k].len-j][i-j])%mod;
	tr[k].add=(tr[k].add+v)%mod;
}
void pushrev(int k){//下传取反懒标记
	if(!k) return;
	for(int i=1;i<=min(tr[k].len,20);i+=2) tr[k].f[i]=mod-tr[k].f[i];
	tr[k].add=mod-tr[k].add;
	tr[k].rev=!tr[k].rev;
}
void pushdown(int k){
	if(tr[k].rev){
		pushrev(k<<1);
		pushrev(k<<1|1);
		tr[k].rev=false;
	}
	if(tr[k].add){
		pushadd(k<<1,tr[k].add);
		pushadd(k<<1|1,tr[k].add);
		tr[k].add=0;
	}
}
void update_add(int k,int l,int r,int v){
	if(l<=tr[k].l and tr[k].r<=r){
		pushadd(k,v);
		return;
	}
	pushdown(k);
	int mid=(tr[k].l+tr[k].r)>>1;
	if(l<=mid) update_add(k<<1,l,r,v);
	if(r>mid)  update_add(k<<1|1,l,r,v);
	pushup(k);
}
void update_rev(int k,int l,int r){
	if(l<=tr[k].l and tr[k].r<=r){
		pushrev(k);
		return;
	}
	pushdown(k);
	int mid=(tr[k].l+tr[k].r)>>1;
	if(l<=mid) update_rev(k<<1,l,r);
	if(r>mid)  update_rev(k<<1|1,l,r);
	pushup(k);
}
node merge(node A,node B){
	node C;
	C.len=A.len+B.len;
	for(int i=0;i<=min(20,A.len);i++)
		for(int j=0;i+j<=20 and j<=B.len;j++) C.f[i+j]=(C.f[i+j]+A.f[i]*B.f[j])%mod;
	return C;
}
node query(int k,int l,int r){
	printf("query(%lld,%lld,%lld)\n",k,l,r);
	if(l<=tr[k].l and tr[k].r<=r) return tr[k];
	pushdown(k);
	int mid=(tr[k].l+tr[k].r)>>1;
	if(r<=mid) return query(k<<1,l,r);
	else if(l>mid) return query(k<<1|1,l,r);
	else return merge(query(k<<1,l,r),query(k<<1|1,l,r));
}

signed main(){
	tr[0].f[0]=1;
	calc();
	scanf("%lld%lld",&n,&q);
	for(int i=1;i<=n;i++) scanf("%lld",&x[i]);
	build(1,1,n);
	for(int i=1,a,b,c;i<=q;i++){
		char opt[2];
		scanf(" %s",opt);
		if(opt[0]=='I'){
			scanf(" %lld%lld%lld",&a,&b,&c);
			c=(c%mod+mod)%mod;
			update_add(1,a,b,c);
		}
		if(opt[0]=='R'){
			scanf(" %lld%lld",&a,&b);
			update_rev(1,a,b);
		}
		if(opt[0]=='Q'){
			scanf(" %lld%lld%lld",&a,&b,&c);
			printf("%lld\n",(query(1,a,b).f[c]%mod+mod)%mod);
		}
	}
	return 0;
}