题意简述：
-
给定一个长度为 (n) 的序列，支持 (n) 个操作
- ( ext{I a b c}) 表示将 ([a,b]) 这一段区间的元素集体增加 (c)；
- ( ext{R a b}) 表示将 ([a,b]) 区间内所有元素变成相反数；
- ( ext{Q a b c}) 表示询问 ([a,b]) 这一段区间中选择 (c) 个数相乘的所有方案的和 (mod 19940417) 的值。
想了 ( ext{1h30min+}) 的细节才做出来，果然我还是组合数学菜鸡啊/dk
前两个操作还算正常，和 [模板]线段树2 是本质相同的，都是相互影响的操作。观察一下，定义取相反数的优先级更高即可。
加上第三个操作就变得棘手了很多，不妨想想只有第三个操作的做法。
注意到 (c) 很小，显然是一个基于 (c) 的时间复杂度的做法。可以想到 ( ext{DP}) ，设 (f[l,r,i]) 为 ([l,r]) 中选 (i) 个相乘，所有方案的和。那么有
其中 (j) 为枚举的一个常数。由于这个 (j) 可以取任何数，所以我们可以令这个 (j) 在任何时候都取线段中点 (mid)。
根据上式，在已经有了 ([l,mid],[mid+1,r]) 两个区间的信息以后，我们可以合并这两个区间 ([l,mid]) 和 ([mid+1,r]) ( o[l,r])。看上去是不是很像线段树的 ( ext{pushup})？那么我们可以把这个 (f) 放在线段树上维护，如果只有第三个操作时，我们可以做到 (O(nc^2 log n))，相比暴力的 (O(n^2c))，这个时间复杂度是非常优秀的。
那么考虑加入前两个操作。对于第一个操作，列举出一些情况，我们发现它的情况像是这个样子：(c=2) 时，(a_1a_2+a_2a_3+a_1a_3 o (a_1+val)(a_2+val)+(a_2+val)(a_3+val)+(a_1+val)(a_3+val))。(a_i) 显然是常数，那么这是一个关于 (val) 的 (c) 次多项式。将 (val) 的不同次项分开计算，可得：
其中 (f'[l,r,i]) 为区间加操作之后的 (f[l,r,i])。
对于第二个操作，其实就是反转正负性，将答案中每个部分的符号写出来，观察并证明，可以得到当 (c) 为奇数时，正负性不变，(c) 为偶数时，正负性改变，形式化的表达：
那么根据以上三个柿子维护 (f) ，再稍微考虑一下 (1,2) 两个操作的优先级，这题就做完了。
-
序列的绝对值(leq 10^9)，而非序列 (leq 10^9) ，注意对初始序列的取模
（我才不会告诉你我被这个卡了 2h -
(19970417) 不是质数，不能使用费马小定理，而应使用杨辉三角求组合数
-
对取模等操作进行封装会把程序卡 ( exttt{TLE})，本题需要一定的卡常功底请慎重食用
（我才不会告诉你我被这个卡了一晚上
Show the Code
#include<cstdio>
#define ls p<<1
#define rs p<<1|1
#define min(a,b) ((a)<(b)? (a):(b))
typedef long long ll;
const ll mod=19940417;
int a[50005],C[50005][25];
struct Segment {Segment() {l=r=add=0;rev=1;f[0]=1;for(register int i=1;i<=20;++i) f[i]=0;} int l,r,rev,add; int f[25];} t[200005];
inline char _read() {register char s=getchar();while(s>'Z'||s<'A') s=getchar();return s;}
inline int read() {
register int x=0,f=1;register char s=getchar();
while(s>'9'||s<'0') {if(s=='-') f=-1;s=getchar();}
while(s>='0'&&s<='9') {x=x*10+s-'0';s=getchar();}
return x*f;
}
inline void work_add(int p,int v) {
int n=t[p].r-t[p].l+1,lim=min(n,20); v=(v%mod+mod)%mod;
for(register int i=lim;i>=1;--i) for(register int k=1,now=v;k<=i;++k,now=(ll)now*(ll)v%mod) t[p].f[i]=(t[p].f[i]+(((ll)C[n-(i-k)][k]*(ll)t[p].f[i-k]%mod)*(ll)now%mod))%mod;
t[p].add=(t[p].add+v)%mod;
}
inline void work_rev(int p) {int lim=min(t[p].r-t[p].l+1,20);for(register int i=1;i<=lim;i+=2) t[p].f[i]=((mod-t[p].f[i])%mod+mod)%mod;t[p].add=((mod-t[p].add)%mod+mod)%mod;t[p].rev*=-1;}
inline void pushup(int p) {int lim=min(t[p].r-t[p].l+1,20);for(register int i=1;i<=lim;++i) {t[p].f[i]=0;for(register int k=0;k<=i;++k) t[p].f[i]=(t[p].f[i]+((ll)t[ls].f[k]*(ll)t[rs].f[i-k]%mod))%mod;}}
inline void spread(int p) {
if(t[p].rev!=1) {work_rev(ls);work_rev(rs);t[p].rev=1;}
if(t[p].add) {work_add(ls,t[p].add);work_add(rs,t[p].add);t[p].add=0;}
}
inline void build(int p,int l,int r) {
t[p].rev=1; t[p].add=0; t[p].l=l; t[p].r=r; t[p].f[0]=1; if(l==r) {t[p].f[1]=a[l];return;}
int mid=l+r>>1; build(ls,l,mid); build(rs,mid+1,r); pushup(p);
}
inline void modify_add(int p,int l,int r,int val) {
int L=t[p].l,R=t[p].r,mid=L+R>>1;
if(l<=L&&R<=r) {work_add(p,val);return;} spread(p);
if(l<=mid) modify_add(ls,l,r,val);
if(r>mid) modify_add(rs,l,r,val);
pushup(p);
}
inline void modify_rev(int p,int l,int r) {
int L=t[p].l,R=t[p].r,mid=L+R>>1;
if(l<=L&&R<=r) {work_rev(p);return;} spread(p);
if(l<=mid) modify_rev(ls,l,r);
if(r>mid) modify_rev(rs,l,r);
pushup(p);
}
inline Segment ask(int p,int l,int r) {
int L=t[p].l,R=t[p].r,mid=L+R>>1; Segment res;
if(l<=L&&R<=r) return t[p]; spread(p);
if(r<=mid) return ask(ls,l,r); if(l>mid) return ask(rs,l,r);
Segment x=ask(ls,l,mid),y=ask(rs,mid+1,r); int lim=min(R-L+1,20);
for(register int i=1;i<=lim;++i) {res.f[i]=0;for(register int k=0;k<=i;++k) res.f[i]=(res.f[i]+((ll)x.f[k]*(ll)y.f[i-k]%mod))%mod;}
return res;
}
signed main() {
int n=read(),T=read();
for(register int i=0;i<=20;++i) {C[i][0]=1;for(register int j=1;j<=i;++j) C[i][j]=(C[i-1][j]+C[i-1][j-1])%mod;}
for(register int i=21;i<=n;++i) {C[i][0]=1;for(register int j=1;j<=20;++j) C[i][j]=(C[i-1][j]+C[i-1][j-1])%mod;}
for(register int i=1;i<=n;++i) a[i]=(read()%mod+mod)%mod; build(1,1,n);
while(T--) {
char op=_read(); int l=read(),r=read();
if(op=='I') {int x=read();modify_add(1,l,r,x);}
else if(op=='R') {modify_rev(1,l,r);}
else {int x=read();printf("%d
",ask(1,l,r).f[x]);}
}
return 0;
}