线段树全wa求调

#include<bits/stdc++.h>
#define ll long long
#define MOD 19940417
using namespace std;

ll n,Q,a[50005],C[50005][22];

inline ll Mod(ll k){return (k%MOD+MOD)%MOD;}

class{
	public:
		ll pow[22]={1};
		struct Point{
			ll L,R,lz_ad,lz_ml,cse[22];
		}po[200005];
		inline void print(){
			cout<<endl<<"print"<<endl;
			for(ll i=1;i<=9;i++){
				cout<<"i = "<<i<<"   L = "<<po[i].L<<"   R = "<<po[i].R<<"   lz_ad = "<<po[i].lz_ad<<"   lz_ml = "<<po[i].lz_ml<<endl;
				cout<<"cse = ";for(ll j=0;j<=20;j++)cout<<po[i].cse[j]<<" ";cout<<endl;
			}
		}
		void build(ll x,ll y,ll p=1){
			po[p]={x,y,0,0};po[p].cse[0]=1;
			for(ll i=1;i<=20;i++)po[p].cse[i]=0;
			if(x==y)return;
			ll mid=(x+y)>>1;
			build(x,mid,p<<1);
			build(mid+1,y,p<<1|1);
		}
		inline void add(ll p,ll k){
			if(!k)return;
//			cout<<"add_i("<<p<<","<<k<<")"<<endl;
			ll len=min(20ll,po[p].R-po[p].L+1);
			pow[0]=1;
			for(ll i=1;i<=len;i++)pow[i]=Mod(pow[i-1]*k);
			for(ll i=len;i>=1;i--){
//				cout<<"i = "<<i<<endl;
				for(ll j=0;j<i;j++){
					po[p].cse[i]=Mod(po[p].cse[i]+Mod(Mod(po[p].cse[j]*pow[i-j])*C[len-j][i-j]));
//					cout<<"j = "<<j<<"   po[p].cse[i] += "<<po[p].cse[j]<<" * "<<pow[i-j]<<" * "<<C[len-j][i-j]<<endl;
				}
			}
			po[p].lz_ad=Mod(po[p].lz_ad+k);
		}
		inline void mul(ll p,ll k){
			if(!k)return;
//			cout<<"mul("<<p<<","<<k<<")"<<endl;
			po[p].lz_ml^=1;
			po[p].lz_ad=Mod(-po[p].lz_ad);
			for(ll i=1;i<=20;i+=2)
				po[p].cse[i]=Mod(-po[p].cse[i]);
//			cout<<"cse = ";for(ll i=1;i<=20;i++)cout<<po[p].cse[i]<<" ";cout<<endl;
		}
		inline void pushdown(ll p){
			mul(p<<1,po[p].lz_ml);
			mul(p<<1|1,po[p].lz_ml);
			add(p<<1,po[p].lz_ad);
			add(p<<1|1,po[p].lz_ad);
		}
		inline void pushup(ll p){
//			cout<<"pushup("<<p<<")"<<endl;
			for(ll i=1;i<=20;i++){
//				cout<<"i = "<<i<<endl;
				ll res=0;
				for(ll j=0;j<=i;j++){
					res=Mod(res+Mod(po[p<<1].cse[j]*po[p<<1|1].cse[i-j]));
//					cout<<"j = "<<j<<"   res += "<<po[p<<1].cse[j]<<" * "<<po[p<<1|1].cse[i-j]<<endl;
				}
				po[p].cse[i]=res;
			}
		}
		void modify_ad(ll x,ll y,ll k,ll p=1){
			if(po[p].R<x||po[p].L>y)return;
			if(po[p].L>=x&&po[p].R<=y){
//				cout<<"app("<<p<<","<<k<<")"<<endl;
				return add(p,k);
			}
			pushdown(p);
			modify_ad(x,y,k,p<<1);
			modify_ad(x,y,k,p<<1|1);
			pushup(p);
		}
		void modify_ml(ll x,ll y,ll p=1){
			if(po[p].R<x||po[p].L>y)return;
			if(po[p].L>=x&&po[p].R<=y)return mul(p,1);
			pushdown(p);
			modify_ml(x,y,p<<1);
			modify_ml(x,y,p<<1|1);
			pushup(p);
		}
		ll ans[22],csk,out[22];
		inline void bforquery(){
			csk=0;
			memset(ans,0,sizeof(ans));
			ans[0]=1;
		}
		void query(ll x,ll y,ll p=1){
			if(po[p].R<x||po[p].L>y)return;
			if(po[p].L>=x&&po[p].R<=y){
//				cout<<"query_p = "<<p<<endl;
				if(!csk){
					for(ll i=1;i<=20;i++)
						ans[i]=po[p].cse[i];
					csk=1;
				}
				else{
					memset(out,0,sizeof(out));
					for(ll i=0;i<=20;i++)
						for(ll j=0;j<=20;j++){
							if(i+j==0||i+j>20)continue;
							out[i+j]=Mod(out[i+j]+Mod(ans[i]*po[p].cse[j]));
//							cout<<"i = "<<i<<"   j = "<<j<<"   ans[i] = "<<ans[i]<<"   cse[j] = "<<po[p].cse[j]<<"   out["<<i+j<<"] += "<<ans[i]*po[p].cse[j]<<endl;
						}
					for(ll i=1;i<=20;i++)ans[i]=out[i];
				}
//				cout<<"ans = ";for(ll i=1;i<=20;i++)cout<<ans[i]<<" ";cout<<endl;
				return;
			}
			pushdown(p);
			query(x,y,p<<1);
			query(x,y,p<<1|1);
		}
}tr;

signed main(){
	ios::sync_with_stdio(false);
	
	C[0][0]=1;
	for(ll i=1;i<=50005;i++){
		C[i][0]=1;
		for(ll j=1;j<=20;j++)
			C[i][j]=Mod(C[i-1][j]+C[i-1][j-1]);
	}
		
	cin>>n>>Q;
	for(ll i=1;i<=n;i++)cin>>a[i],a[i]=Mod(a[i]);
	
	tr.build(1,n);
//	tr.print();
	for(ll i=1;i<=n;i++){
//		cout<<"tr.modify("<<i<<","<<i<<","<<a[i]<<")"<<endl;
		tr.modify_ad(i,i,a[i]);
//		tr.print();
	}
	
	while(Q--){
		char op;ll x,y,k;
		cin>>op>>x>>y;
		if(op=='I'){
			cin>>k;k=Mod(k);
			tr.modify_ad(x,y,k);
		}
		else if(op=='R')tr.modify_ml(x,y);
		else{
			cin>>k;
			tr.bforquery();
			tr.query(x,y);
			cout<<tr.ans[k]<<endl;
		}
//		tr.print();
	}
	
	return 0;
}