题目描述
有一个长度为\(n\)的序列，有三个操作：
I a b c表示将\([a,b]\)这一段区间的元素集体增加\(c\)；R a b表示将\([a,b]\)区间内所有元素变成相反数；Q a b c表示询问\([a,b]\)这一段区间中选择\(c\)个数相乘的所有方案的和\(\mod 19940417\)的值。
对于100%的数据，\(n \leq 50000, q \leq 50000\)，初始序列的元素的绝对值\(\leq 10^9\)，保证\([a,b]\)是一个合法区间，I操作中\(|c| \leq 10^9\)，Q操作中\(1 \leq c \leq \min(b-a+1,20)\)。
思路
\(1.\) 区间加，线段树基础操作。
\(2.\) 取反，显而易见奇变偶不变。
\(3.\) 查询，发现 \(c\) 的值域很小，我们可直接维护答案。
细节
\(1.\)上传 \(pushup\)
考虑 DP
\(f_{l,r,c}=f_{l,mid,i}* f_{mid+1,r,j}(i+j=c)\)
\(2.\)区间加时更新答案
手写几项展开可发现
\(f_{l,r,c}= \sum\limits_{i=0}^{c}f_{l,r,i} \cdot x^{c-i}\cdot C_{r-l+1-i}^{c-i}\)
可先预处理出杨辉三角形
\(3.\)标记优先级
取反时，要将加标记取反。
取反先于加法
固定模数一定要加const！！！！！
2 h就废在这上面了（算是首黑纪念了）
Code
#include<bits/stdc++.h>
using namespace std;
#define LL long long
#define Ld long double
#define l(p) tree[p].l
#define r(p) tree[p].r
#define sum(p,k) tree[p].sum[k]
#define chg(p) tree[p].chg
#define add(p) tree[p].add
const int N = 60005,M=20005,mod=19940417;
int n,q,y,l,r,pos; `
LL c[N][25],d[50],x;
char op[2];
struct Segment_tree{
int l,r,chg;
LL sum[25],add;
}tree[N*4];
inline int min(int a,int b){
return a<b?a:b
}
inline LL readc(){
char ch=getchar();
while(!((ch>='a'&&ch<='z')||(ch>='A'&&ch<='Z'))) ch=getchar();
return ch;
}
inline LL read(){
LL s=0,w=1;char ch=getchar();
while(ch<'0'||ch>'9') {if(ch=='-') w=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){s=(s<<1)+(s<<3)+ch-'0';ch=getchar();}
return s*w;
}
inline void print(LL x){
char F[200];LL cnt=0;
if(x==0){putchar('0');putchar('\n');return ;}
if(x<0){putchar('-');x=-x;}
while(x){F[++cnt]=x%10;x/=10;}
while(cnt) putchar(F[cnt--]+'0');
putchar('\n');return ;
}
void ad(int p,int k){
if(!k||!p) return ;
int l1=min(20,r(p)-l(p)+1);
d[0]=1;
for(int i=1;i<=l1;i++) d[i]=(d[i-1]*k)%mod;
for(int i=l1;i>=1;i--){
for(int j=0;j<i;j++){
sum(p,i)=(sum(p,i)+((sum(p,j)*d[i-j]%mod)*c[r(p)-l(p)+1-j][i-j])%mod)%mod;
}
}
add(p)=(add(p)+k)%mod;
return ;
}
void ch(int p){
if(!p) return ;
for(int i=1;i<=min(20,r(p)-l(p)+1);i+=2)
sum(p,i)=(mod-sum(p,i))%mod;
add(p)=(mod-add(p))%mod;
chg(p)^=1;
return ;
}
void pushup(int p){
int l1=min(20,r(p)-l(p)+1),l2=min(20,r(p<<1)-l(p<<1)+1),l3=min(20,r(p<<1|1)-l(p<<1|1)+1);
for(int i=0;i<=l1;i++) sum(p,i)=0;
for(int i=0;i<=l2;i++)
for(int j=0;j<=l3;j++){
if(i+j>20) break;
sum(p,i+j)=(sum(p,i+j)+sum(p<<1,i)*sum(p<<1|1,j)%mod)%mod;
}
return ;
}
void pushdown(int p){
if(chg(p)){
ch(p<<1);ch(p<<1|1);
chg(p)=0;
}
if(add(p)){
ad(p<<1,add(p));
ad(p<<1|1,add(p));
add(p)=0;
}
return ;
}
void build(int p,int l,int r){
l(p)=l,r(p)=r;
sum(p,0)=1;
if(l==r){
sum(p,1)=(read()%mod+mod)%mod;
return ;
}
int mid=(l+r)>>1;
build(p<<1,l,mid);
build(p<<1|1,mid+1,r);
pushup(p);
return ;
}
void change(int p,int l,int r,LL x,LL op){
if(l(p)>=l&&r(p)<=r){
if(op==1)
ad(p,x);
else
ch(p);
return ;
}
pushdown(p);
int mid=(l(p)+r(p))>>1;
if(l<=mid) change(p<<1,l,r,x,op);
if(r>mid) change(p<<1|1,l,r,x,op);
pushup(p);
return ;
}
Segment_tree merge(Segment_tree ls,Segment_tree rs,int x){
x=20;
Segment_tree now;
now.r=rs.r,now.l=ls.l;
int l1=min(x,now.r-now.l+1),l2=min(x,ls.r-ls.l+1),l3=min(x,rs.r-rs.l+1);
for(int i=0;i<=l1;i++) now.sum[i]=0;
for(int i=0;i<=l2;i++)
for(int j=0;j<=l3;j++){
if(i+j>x) break;
now.sum[i+j]=(now.sum[i+j]+ls.sum[i]*rs.sum[j]%mod)%mod;
}
return now;
}
Segment_tree query(int p,int l,int r,int x){
if(l(p)>=l&&r(p)<=r) return tree[p];
pushdown(p);
LL mid=(l(p)+r(p))>>1;
if(r<=mid) return query(p<<1,l,r,x);
else
if(l>mid) return query(p<<1|1,l,r,x);
else return merge(query(p<<1,l,r,x),query(p<<1|1,l,r,x),x);
}
int main(){
n=read(),q=read();
c[0][0]=1;c[1][0]=1;c[1][1]=1;
for(int i=2;i<=N-5;i++){
c[i][0]=1;
for(int j=1;j<=min(20,i);j++){
c[i][j]=(c[i-1][j-1]+c[i-1][j])%mod;
}
}
build(1,1,n);
for(int i=1;i<=q;i++){
cin>>op;l=read(),r=read();
if(op[0]=='I'){
x=read();
x%=mod;
change(1,l,r,(x+mod)%mod,1);
}else
if(op[0]=='R'){
change(1,l,r,0,0);
}else
if(op[0]=='Q'){
x=read();
print((query(1,l,r,x).sum[x]+mod)%mod);
}
}
return 0;
}