求助

#include<bits/stdc++.h>
#define ri register int
#define ls(t) t<<1
#define rs(t) t<<1|1
#define maxn 50001
#define mod 19940417
using namespace std;
typedef long long ll;
template<typename T>inline void read(T &x)
{
	x=0;register char c=getchar();register bool f=false;
	while(!isdigit(c)&&c!='-')c=getchar();
	if(c=='-')f=true,c=getchar();
	while(isdigit(c))x=(x<<3)+(x<<1)+c-'0',c=getchar();
	x=f?-x:x;
}
int n,m;
inline ll ksm(ll x,int y)
{
	if(x<=1)return x;
	ll ans=1;
	for(ri i=y;i;i>>=1)
	{
		if(i&1)ans=ans*x%mod;
		x=x*x%mod;
	}
	return ans;
}
ll c[21][maxn];
struct seg
{
	ll f[21],tg1;
	int len;
	bool tg2;
	seg(){for(ri i=1;i<21;i++)f[i]=0;f[0]=1;len=tg1=tg2=0;}
	inline seg operator+(seg x)
	{
		seg y;
		y.len=len+x.len;
		for(ri i=1;i<=min(y.len,20);i++)for(ri j=i;j>=0;j--)y.f[i]=(y.f[i]+f[j]*x.f[i-j]%mod)%mod;
		return y;
	}
}st[maxn<<2];
inline void build(int l,int r,int t)
{
	if(l==r)
	{
		read(st[t].f[1]);
		st[t].f[1]=(st[t].f[1]%mod+mod)%mod;
		st[t].len=1;
		return;
	}
	int mid=(l+r)>>1;
	build(l,mid,ls(t));
	build(mid+1,r,rs(t));
	st[t]=st[ls(t)]+st[rs(t)];
}
inline void reserve(int t)
{
	for(ri i=1;i<=min(st[t].len,20);i+=2)st[t].f[i]=(mod-st[t].f[i])%mod;
	st[t].tg1=(mod-st[t].tg1)%mod;
	st[t].tg2^=1;
}
inline void add(ll x,int t)
{
	register ll temp;
	for(ri i=min(st[t].len,20);i>=1;i--)
	{
		temp=0;
		for(ri j=0;j<=i;j++)temp=(temp+st[t].f[i-j]*c[j][st[t].len-i+j]%mod*ksm(x,j)%mod)%mod;
		st[t].f[i]=temp;
	}
	st[t].tg1=(st[t].tg1+x)%mod;
}
inline void pushdown(int l,int r,int t)
{
	if(!st[t].tg1&&!st[t].tg2)return;
	if(st[t].tg2)
	{
		reserve(ls(t));
		reserve(rs(t));
		st[t].tg2=false;
	}
	if(st[t].tg1)
	{
		add(st[t].tg1,ls(t));
		add(st[t].tg1,rs(t));
		st[t].tg1=0;
	}
}
inline void update(int nl,int nr,int k,int l,int r,int t)
{
	if(nl<=l&&r<=nr)
	{
		add(k,t);
		return;
	}
	pushdown(l,r,t);
	int mid=(l+r)>>1;
	if(nl<=mid)update(nl,nr,k,l,mid,ls(t));
	if(nr>mid)update(nl,nr,k,mid+1,r,rs(t));
	st[t]=st[ls(t)]+st[rs(t)];
}
inline void change(int nl,int nr,int l,int r,int t)
{
	if(nl<=l&&r<=nr)
	{
		reserve(t);
		return;
	}
	pushdown(l,r,t);
	int mid=(l+r)>>1;
	if(nl<=mid)change(nl,nr,l,mid,ls(t));
	if(nr>mid)change(nl,nr,mid+1,r,rs(t));
	st[t]=st[ls(t)]+st[rs(t)];
}
inline seg query(int nl,int nr,int l,int r,int t)
{
	if(nl<=l&&r<=nr)return st[t];
	pushdown(l,r,t);
	int mid=(l+r)>>1;
	seg ans;
	if(nl<=mid)ans=ans+query(nl,nr,l,mid,ls(t));
	if(nr>mid)ans=ans+query(nl,nr,mid+1,r,rs(t));
	return ans;
}
int main()
{
	for(ri i=0;i<=50000;i++)c[0][i]=1;
	for(ri i=1;i<=20;i++)for(ri j=i;j<=50000;j++)c[i][j]=(c[i-1][j-1]+c[i][j-1])%mod;
	read(n);
	read(m);
	build(1,n,1);
	register char ch;
	int x0,y0,z0;
	for(ri i=1;i<=m;i++)
	{
		for(ch=getchar();ch!='I'&&ch!='R'&&ch!='Q';ch=getchar());
		read(x0);
		read(y0);
		switch(ch)
		{
		case 'I':
			read(z0);
			update(x0,y0,(z0%mod+mod)%mod,1,n,1);
			break;
		case 'R':
			change(x0,y0,1,n,1);
			break;
		default:
			read(z0);
			printf("%d\n",query(x0,y0,1,n,1).f[z0]);
		}
	}
	return 0;
}