Description
有一个长度为n的序列，有三个操作1.I a b c表示将[a,b]这一段区间的元素集体增加c，2.R a b表示将[a,b]区间内所有元素变成相反数，3.Q a b c表示询问[a,b]这一段区间中选择c个数相乘的所有方案的和mod 19940417的值。
Input
第一行两个数n，q表示序列长度和操作个数。
第二行n个非负整数，表示序列。
接下来q行每行输入一个操作I a b c或者 R a b或者Q a b c意义如题目描述。
Output
对于每个询问，输出选出c个数相乘的所有方案的和mod19940417的值。
Sample Input
5 5
1 2 3 4 5
I 2 3 1
Q 2 4 2
R 1 5
I 1 3 -1
Q 1 5 1
1 2 3 4 5
I 2 3 1
Q 2 4 2
R 1 5
I 1 3 -1
Q 1 5 1
Sample Output
40
19940397
样例说明
做完第一个操作序列变为1 3 4 4 5。
第一次询问结果为3*4+3*4+4*4=40。
做完R操作变成-1 -3 -4 -4 -5。
做完I操作变为-2 -4 -5 -4 -5。
第二次询问结果为-2-4-5-4-5=-20。
19940397
样例说明
做完第一个操作序列变为1 3 4 4 5。
第一次询问结果为3*4+3*4+4*4=40。
做完R操作变成-1 -3 -4 -4 -5。
做完I操作变为-2 -4 -5 -4 -5。
第二次询问结果为-2-4-5-4-5=-20。
HINT
100%的数据n<=50000,q<=50000,初始序列的元素的绝对值<=109，I
a b c中保证[a,b]是一个合法区间，|c|<=109，R a b保证[a,b]是个合法的区间。Q a b
c中保证[a,b]是个合法的区间1<=c<=min(b-a+1,20)。
每个区间维护F[i]表示当c=i时这个区间的答案。
然后可以暴力合并区间的答案，上传和查询同理。
难点在于两个修改。
取相反数的操作显然只对i为奇数的F[i]取相反数，偶数不变。
区间加x时，假设从${a,b,c}$到${a+x,b+x,c+x}$，那么$(a+x)*(b+x)+(b+x)*(c+x)+(a*x)+(c*x)=ab+ac+bc+2x(a+b+c)+3x^{2}$。
有一些是我们已经知道的信息，剩下的那些x的系数是组合数，预处理出来即可。
代码：
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
#define N 50050
#define mod 19940417
#define ls p<<1
#define rs p<<1|1
int n,m,C[N][22];
struct node {
int add,rev,s[22],siz;
node() {memset(s,0,sizeof(s));rev=add=siz=0;}
node operator + (const node &x) const {
node re;
int i,j;
for(i=0;i<=20;i++) {
for(j=0;i+j<=20;j++) {
re.s[i+j]=(re.s[i+j]+1ll*s[i]*x.s[j]%mod+mod)%mod;
}
}
re.siz=siz+x.siz;
return re;
}
void rev_() {
int i;
for(i=1;i<=20;i+=2) s[i]=(mod-s[i])%mod;
}
void add_(int d) {
int i,j;
int t;
for(i=min(siz,20);i;i--) {
for(t=d,j=1;j<i;j++,t=1ll*t*d%mod) s[i]=(s[i]+1ll*t*s[i-j]%mod*C[siz-i+j][j]%mod)%mod;
s[i]=(s[i]+1ll*C[siz][i]*t%mod)%mod;
}
}
}t[N<<2];
void pushdown(int p) {
if(t[p].rev) {
t[ls].rev_(); t[rs].rev_();
t[ls].add=(mod-t[ls].add)%mod; t[rs].add=(mod-t[rs].add)%mod;
t[ls].rev^=1; t[rs].rev^=1;
t[p].rev=0;
}
if(t[p].add) {
int d=t[p].add;
t[ls].add_(d); t[rs].add_(d);
t[ls].add=(t[ls].add+d)%mod; t[rs].add=(t[rs].add+d)%mod;
t[p].add=0;
}
}
void build(int l,int r,int p) {
if(l==r) {
int x;
scanf("%d",&x);
x=(x%mod+mod)%mod;
t[p].s[0]=1; t[p].s[1]=x; t[p].siz=1;
return ;
}
int mid=(l+r)>>1;
build(l,mid,ls); build(mid+1,r,rs);
t[p]=t[ls]+t[rs];
}
node query(int l,int r,int x,int y,int p) {
if(x<=l&&y>=r) return t[p];
pushdown(p);
int mid=(l+r)>>1;
if(y<=mid) return query(l,mid,x,y,ls);
if(x>mid) return query(mid+1,r,x,y,rs);
return query(l,mid,x,y,ls)+query(mid+1,r,x,y,rs);
}
void update(int l,int r,int x,int y,int v,int p) {
if(x<=l&&y>=r) {
t[p].add_(v); (t[p].add+=v)%=mod;
return ;
}
pushdown(p);
int mid=(l+r)>>1;
if(x<=mid) update(l,mid,x,y,v,ls);
if(y>mid) update(mid+1,r,x,y,v,rs);
t[p]=t[ls]+t[rs];
}
void reverse(int l,int r,int x,int y,int p) {
if(x<=l&&y>=r) {
t[p].rev_(); t[p].rev^=1; t[p].add=(mod-t[p].add)%mod;
return ;
}
pushdown(p);
int mid=(l+r)>>1;
if(x<=mid) reverse(l,mid,x,y,ls);
if(y>mid) reverse(mid+1,r,x,y,rs);
t[p]=t[ls]+t[rs];
}
char opt[10];
int main() {
int i,x,y,z,j;
scanf("%d%d",&n,&m);
for(i=0;i<=n;i++) C[i][0]=C[i][i]=1;
for(i=1;i<=n;i++) {
int t=min(20,i);
for(j=1;j<=t;j++) C[i][j]=(C[i-1][j]+C[i-1][j-1])%mod;
}
build(1,n,1);
while(m--) {
scanf("%s%d%d",opt,&x,&y);
if(opt[0]!='R') scanf("%d",&z);
if(opt[0]=='I') {
z=(z%mod+mod)%mod;
update(1,n,x,y,z,1);
}else if(opt[0]=='R') {
reverse(1,n,x,y,1);
}else {
printf("%d\n",(query(1,n,x,y,1).s[z]%mod+mod)%mod);
}
}
}