\(Link\)

题意略。（懒了

\(1.\)假做法：

先不考虑修改，只看查询。

若现在有 \(n\) 个数 \(a_1 \dots a_n\)，要选 \(k\) 个，答案是什么？

我们设 \(s_i=\sum_{j=1}^n a_j^i\)，\(f(k)\) 为选 \(k\) 个数时的答案（\(f(0)=1\)）。

然后一通找规律加容斥，发现一个优美的性质：

\[f(k)=\dfrac{1}{k}\sum_{i=1}^k (-1)^{i-1}*s_i*f(k-i) \]

配合上记忆化，求单个 \(f(k)\) 的时间是 \(O(k^2)\)，但是 \(k\) 只有\(20\)，完全可以。

接着把修改加进去，套上线段树，于是我们只用维护每个区间的 \(s\) 值了！

而这个就用二项式定理乱搞亿下就可以维护了！

好像可以解决了呀！这就是黑题吗？

然而 \(mod=19940417=7\times 2848631\)

于是 7 和 14 没有逆元。

然后求 \(\dfrac{1}{k}\) 的部分也就凉凉了。。。。

/悲

\(2.\)真做法：

直接维护每个区间选 1 到 20 个时的答案 \(f_1 \dots f_{20}\)，然后可以轻松区间合并。

设当前为 \(p\)，左儿子为 \(ls\)，右儿子为 \(rs\)。

于是区间合并：

\[p_{f_i}=\sum_{j=0}^{i}ls_{f_j} \times rs_{f_{i-j}} \]

区间加的话，以 \(i=5\) 为例，设原来的 5 个数是 \(a,b,c,d,e\)，权值是 \(f_5=abcde\)。

然后加上 \(s\)，变成 \((a+s)(b+s)(c+s)(d+s)(e+s)\)。

然后我们要求 \(f_3=f_3+f_{2}*s*\binom{3}{1}+f_{1}*s^2*\binom{4}{2}+f_{0}*s^3*\binom{5}{3}\)。

于是可以发现\(f_i=\sum_{j=0}^{i}s^{i-j}*\binom{len-j}{i-j}*f_j\)。

然后可以杨辉三角处理出组合数，倒着更新 \(f_i\)。

区间取反，发现 \(i\) 为奇数的时候 \(f_i\) 取反，否则不变。

最后开两个懒标记记录加的和取反，正常线段树就行了。

\(Code:\)

// Problem: P4247 [清华集训2012]序列操作
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P4247
// Memory Limit: 250 MB
// Time Limit: 6000 ms
// Author: jimmyywang
//

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define f(i,a,b) for(ll i=a;i<=b;i++)
#define wt int tt=d;while(tt--)
#define py puts("Yes")
#define pn puts("No")
#define fe(i,e) for(int i=0;i<e.size();i++)
#define vi vector<ll>
inline ll rd() {
	ll x=0,f=1;
	char c=getchar();
	while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
	while(isdigit(c))x=x*10+c-'0',c=getchar();
	return x*f;
}
#define d rd()
#define pb push_back
const ll N=300010;
struct edge{ll v,w,nx;}e[N<<1];
ll hd[N],cnt;
void add(ll u,ll v,ll w){e[++cnt]=(edge){v,w,hd[u]};hd[u]=cnt;}
ll qp(ll a,ll b,ll p){
	ll ans=1;while(b){
		if(b&1)ans=ans*a%p;
		a=a*a%p;b>>=1;
	}return ans;
}ll n,m;
struct node{
	ll s[21];
}t[50010<<2];
ll a[50010];
const ll mod=19940417;
node merge(node a,node b){
	node ans;ans.s[0]=1;
	f(i,1,20){
		ans.s[i]=0;
		f(j,0,i)ans.s[i]=(ans.s[i]+a.s[j]*b.s[i-j]%mod+mod)%mod;
	}
	return ans;
}
ll C[50010][25];
ll ls(ll p){return p<<1;}
ll rs(ll p){return p<<1|1;}
void upd(ll p){t[p]=merge(t[ls(p)],t[rs(p)]);}
ll tga[50010<<2];
ll tgb[50010<<2];
void build(ll l,ll r,ll p){
	if(l==r){f(i,0,20)t[p].s[i]=0;
	t[p].s[1]=(a[l]%mod+mod)%mod,t[p].s[0]=1;return;}
	ll mid=(l+r)>>1;
	build(l,mid,ls(p));
	build(mid+1,r,rs(p));
	upd(p);
}
void rev(ll p,ll len){
	if(!p)return;
	f(i,1,min(len,20ll))if(i&1)t[p].s[i]=mod-t[p].s[i];
	tgb[p]=mod-tgb[p],tga[p]^=1;
}
void adi(ll p,ll x,ll len){
	if(!p||!x)return;
	for(int i=min(len,20ll);i>=1;i--){
		ll tmp=x;for(int j=i-1;j>=0;j--)
		t[p].s[i]=(t[p].s[i]+t[p].s[j]*tmp%mod*C[len-j][i-j]%mod)%mod,
		t[p].s[i]=(t[p].s[i]+mod)%mod,tmp=tmp*x%mod;
	}tgb[p]=(tgb[p]+x)%mod;
}
void pd(ll p,ll l,ll r){ll mid=(l+r)>>1;
	if(tga[p])rev(ls(p),mid-l+1),rev(rs(p),r-mid),tga[p]=0;
	if(tgb[p])adi(ls(p),tgb[p],mid-l+1),adi(rs(p),tgb[p],r-mid),tgb[p]=0;
}
void add(ll l,ll r,ll p,ll L,ll R,ll k){
	if(L<=l&&r<=R){adi(p,k,r-l+1);return;}
	pd(p,l,r);ll mid=(l+r)>>1;
	if(mid>=L)add(l,mid,ls(p),L,R,k);
	if(mid<R)add(mid+1,r,rs(p),L,R,k);
	upd(p);
}void rv(ll l,ll r,ll p,ll L,ll R){
	if(L<=l&&r<=R){rev(p,r-l+1);return;}
	pd(p,l,r);ll mid=(l+r)>>1;
	if(mid>=L)rv(l,mid,ls(p),L,R);
	if(mid<R)rv(mid+1,r,rs(p),L,R);
	upd(p);
}
node ask(ll l,ll r,ll p,ll L,ll R){
	if(L<=l&&r<=R)return t[p];
	pd(p,l,r);ll mid=(l+r)>>1;
	if(mid>=R)return ask(l,mid,ls(p),L,R);
	if(mid<L)return ask(mid+1,r,rs(p),L,R);
	return merge(ask(l,mid,ls(p),L,R),ask(mid+1,r,rs(p),L,R));
}
int main(){
	n=d,m=d;
	f(i,1,n)a[i]=d%mod;
	C[0][0]=1;
	f(i,1,n){
		C[i][0]=1;
		f(j,1,min(20ll,i))C[i][j]=(C[i-1][j]+C[i-1][j-1])%mod;
	}
	build(1,n,1);
	while(m--){
		char c;cin>>c;
		if(c=='I'){
			ll l=d,r=d,x=(d%mod+mod)%mod;
			add(1,n,1,l,r,x);
		}if(c=='R'){
			ll l=d,r=d;
			rv(1,n,1,l,r);
		}if(c=='Q'){
			ll l=d,r=d,k=d;
			printf("%lld\n",(ask(1,n,1,l,r).s[k]%mod+mod)%mod);
		}
	}
	return 0;
}