线段树基础题。

题意：要求维护区间区间中选择$c$个数相乘的所有方案的和($c\le 20$)，支持区间加，区间取负。

---

由于$c\le 20$，因此可以对于每个线段树节点可以暴力维护$21$个$sum$值，合并也很简单，是一个卷积的形式sumi=∑j=0isumjsumi−jsum_i=\sum_{j=0}^isum_jsum_{i-j}sumi​=∑j=0i​sumj​sumi−j​可以用FFT优化一波(滑稽。

区间取负并没有什么难度，对于sumisum_isumi​来说，如果$i$是偶数就并没有什么影响，如果$i$是奇数把sumisum_isumi​变成−sumi-sum_i−sumi​即可。

关键在于区间加。

考虑到区间加对每个$sum$的影响，我们把a1a2...ana_1a_2...a_na1​a2​...an​变成了(a1+x)(a2+x)...(an+x)(a_1+x)(a_2+x)...(a_n+x)(a1​+x)(a2​+x)...(an​+x)，我们设这个区间长度为$len$，那么有组合数学的方法可以将这个式子展开：newsumi=∑j=0iClen−ji−jxjoldsumjnewsum_{i}=\sum_{j=0}^iC_{len-j}^{i-j}x^joldsum_jnewsumi​=∑j=0i​Clen−ji−j​xjoldsumj​ 相当于是枚举每个括号里面$x$的个数来更新答案

然后就没啥了~~注意细节~~

代码：

#include
    
     #define lc (p<<1)#define rc (p<<1|1)#define mid (T[p].l+T[p].r>>1)#define add(a,b) ((a)+(b)>=mod?(a)+(b)-mod:(a)+(b))#define mul(a,b) ((ll)(a)*(b)%mod)#define dec(a,b) ((a)>=(b)?(a)-(b):(a)-(b)+mod)#define ri register intusing namespace std;typedef long long ll;const int mod=19940417,N=5e5+5;int n,m,a[N],C[N][21];inline int read(){
    	int ans=0,w=1;	char ch=getchar();	while(!isdigit(ch)){
    if(ch=='-')w=-1;ch=getchar();}	while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar();	return ans*w;}struct Node{
    int l,r,sum[21],add;bool rev;Node(){
    l=r=add=rev=0;for(ri i=0;i<=20;++i)sum[i]=0;}}T[N<<2];inline Node operator+(const Node&a,const Node&b){
    	Node ret;	ret.l=a.l,ret.r=b.r;	for(ri i=0;i<=20;++i)for(ri j=0;j<=i;++j)ret.sum[i]=add(ret.sum[i],mul(a.sum[j],b.sum[i-j]));	return ret;}inline void pushadd(int p,int v){
    	T[p].add=add(T[p].add,v);	for(ri i=min(T[p].r-T[p].l+1,20),len=T[p].r-T[p].l+1;~i;--i)for(ri j=i-1,mult=v;~j;--j,mult=mul(mult,v))		T[p].sum[i]=add(T[p].sum[i],mul(C[len-j][i-j],mul(mult,T[p].sum[j])));}inline void pushrev(int p){
    	T[p].rev^=1,T[p].add=dec(0,T[p].add);	for(ri i=0;i<=20;++i)if(i&1)T[p].sum[i]=dec(0,T[p].sum[i]);}inline void pushdown(int p){
    	if(T[p].rev)pushrev(lc),pushrev(rc),T[p].rev^=1;	if(T[p].add)pushadd(lc,T[p].add),pushadd(rc,T[p].add),T[p].add=0;}inline void build(int p,int l,int r){
    	T[p].l=l,T[p].r=r;	if(T[p].l==T[p].r){
    T[p].sum[0]=1,T[p].sum[1]=a[l];return;}	build(lc,l,mid),build(rc,mid+1,r),T[p]=T[lc]+T[rc];}inline void update(int p,int ql,int qr,int v){
    	if(ql<=T[p].l&&T[p].r<=qr)return v?pushadd(p,v):pushrev(p);	pushdown(p);	if(qr<=mid)update(lc,ql,qr,v);	else if(ql>mid)update(rc,ql,qr,v);	else update(lc,ql,mid,v),update(rc,mid+1,qr,v);	T[p]=T[lc]+T[rc];}inline Node query(int p,int ql,int qr){
    	if(ql<=T[p].l&&T[p].r<=qr)return T[p];	pushdown(p);	if(qr<=mid)return query(lc,ql,qr);	if(ql>mid)return query(rc,ql,qr);	return query(lc,ql,mid)+query(rc,mid+1,qr);}inline void init(){
    	for(ri i=0;i<=n;++i)C[i][0]=1;	for(ri i=1;i<=n;++i){
    		C[i][1]=i;		for(ri j=2;j<=min(20,i);++j)C[i][j]=add(C[i-1][j],C[i-1][j-1]);	}	build(1,1,n);}int main(){
    	n=read(),m=read();	for(ri i=1;i<=n;++i)a[i]=(read()%mod+mod)%mod;	init();	while(m--){
    		char s[2];		scanf("%s",s);		int l=read(),r=read(),v;		if(s[0]=='I'){
    			v=(read()%mod+mod)%mod;			if(!v)continue;			update(1,l,r,v);		}		else if(s[0]=='R')update(1,l,r,0);		else cout<
     
      <<'\n';	}	return 0;}