【题解】P4247 [清华集训]序列操作(线段树修改DP)
一道神仙数据结构(DP)题。
题目大意
给定你一个序列，会区间加和区间变相反数，要你支持查询一段区间内任意选择\(c\)个数乘起来的和。对19940417取膜。
咋做
我们这一类题看来有一个套路就是用线段树维护一个DP数组，然后线段树节点合并就用一点组合的技巧..
设\(dp(i)\)表示在该区间里选择\(i\)个乘起来的和，考虑如何合并区间，很简单就是
\[dp(i)=\sum_{j=0}dp'(j)dp''(i-j)
\]
\]
先考虑加法怎么办，可以这样考虑，每个数加上一个\(\Delta x\) 相当于从\((a)(b)(c)\)变成\((a+\Delta x)(b+\Delta x)(\Delta c+x)\)，把式子拆一下就是变成
\[(\Delta x)^3+(a+b+c)(\Delta x)^2+(ab+ac+bc)\Delta x+abc
\]
\]
观察一下括号里面的东西，发现就是\(dp(?)\)，就是随意选取\(?\)个的和，还要乘上一个组合数。所以可以直接在\(dp\)数组里更新。
\[dp'(i)=\sum_{j=0}^i {len-i+j\choose j}\times dp(j)\times x^j
\]
\]
再阐释一下这个式子的组合意义，拆上面那个括号，可以这样看，每次贡献都是从左往右每个括号里，我可以随意选择一个字母或者\(\Delta x\)贡献一下，一次选择了\(k\)个\(\Delta x\)的贡献就是不同选择字母情况的\((\Delta x)^k\times (\underbrace {ab\dots z}_{len-k\text{个}})\) 。的和，而我们之前维护的\(dp(len-k)\)就可以用了。又因为一个\(dp(i)\)数组里不一定只有\((a)(b)(c)\)，可能还会有\((\alpha)(\beta)(\theta)\)，所以还要一个组合数。
再考虑取反怎么办，显然就是\(dp(\text{奇数})\)取反就好了。顺便把lazytag取反。
代码
//@winlere
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define lef l,mid,pos<<1
#define rgt mid+1,r,pos<<1|1
#define all 1,n,1
#define midd register int mid=(l+r)>>1
using namespace std; typedef long long ll; typedef const int& ct;
inline int qr(){
register int ret=0,f=0;
register char c=getchar();
while(c<48||c>57)f|=c==45,c=getchar();
while(c>=48&&c<=57) ret=ret*10+c-48,c=getchar();
return f?-ret:ret;
}
const int maxn=5e4+1;
const int mod=19940417;
int add[maxn<<2|1];
int anti[maxn<<2|1];
int c[maxn][21];
int temp[21];
struct DP{
int dp[21];
DP(){memset(dp,0,sizeof dp);dp[0]=1;}
inline void debug(){
puts("Debug=");
for(register int t=1;t<=20;++t)
printf("%d ",dp[t]);
putchar('\n');
}
inline int& operator[](int x){return dp[x];}
inline void upd(DP&a,DP&b){
for(register int t=1;t<=20;++t) dp[t]=0;
dp[0]=1;
for(register int t=1;t<=20;++t)
for(register int i=0;i<=t;++i)
dp[t]=(dp[t]+1ll*a[i]*b[t-i]%mod)%mod;
}
inline void upd(DP a){
for(register int t=0;t<=20;++t) temp[t]=0;
temp[0]=1;
int*dp1=a.dp;
for(register int t=1;t<=20;++t)
for(register int i=0;i<=t;++i)
temp[t]=(temp[t]+1ll*dp[i]*dp1[t-i]%mod)%mod;
for(register int t=0;t<=20;++t)
dp[t]=temp[t];
}
}data[maxn<<2];
inline void pushup(const int&pos){
data[pos].upd(data[pos<<1],data[pos<<1|1]);
}
inline void getadd(const int&pos,const int&AD,const int&l,const int&r){
int* dp=data[pos].dp;
for(register int t=min(r-l+1,20),w,t1;t;--t){
w=1;t1=0;
for(register int i=0;i<=t;++i,w=1ll*w*AD%mod)
t1=(t1+1ll*dp[t-i]*c[r-l+1-t+i][i]%mod*1ll*w%mod);
dp[t]=t1;
}
}
inline void getanti(const int&pos){
int*dp=data[pos].dp;
for(register int t=1;t<=20;t+=2)
dp[t]=(mod-dp[t]%mod)%mod;
}
inline void pushdown(const int&pos,const int&l,const int&mid,const int&r){
if(anti[pos]){
anti[pos<<1]^=1;anti[pos<<1|1]^=1;
getanti(pos<<1);getanti(pos<<1|1);
add[pos<<1]=(mod-add[pos<<1]%mod)%mod;
add[pos<<1|1]=(mod-add[pos<<1|1]%mod)%mod;
anti[pos]=0;
}
if(add[pos]){
getadd(pos<<1,add[pos],l,mid);
getadd(pos<<1|1,add[pos],mid+1,r);
add[pos<<1]=(add[pos<<1]+add[pos]%mod)%mod;
add[pos<<1|1]=(add[pos<<1|1]+add[pos]%mod)%mod;
add[pos]=0;
}
}
void build(ct l,ct r,ct pos){midd;
if(l==r){data[pos][1]=(qr()%mod+mod)%mod;return;}
build(lef);build(rgt);
pushup(pos);
}
DP RET;
void que(ct L,ct R,ct l,ct r,ct pos){
if(L>r||R<l)return;
if(L<=l&&r<=R){RET.upd(data[pos]);return;}
midd;pushdown(pos,l,mid,r);
que(L,R,lef),que(L,R,rgt);
}
void upd(ct L,ct R,ct k,ct l,ct r,ct pos){
if(L>r||R<l)return;
if(L<=l&&r<=R){
add[pos]=(add[pos]+k)%mod;
getadd(pos,k,l,r);
return;
}midd;
pushdown(pos,l,mid,r);
upd(L,R,k,lef);upd(L,R,k,rgt);
pushup(pos);
}
void upd(ct L,ct R,ct l,ct r,ct pos){
if(L>r||R<l)return;
if(L<=l&&r<=R){
anti[pos]^=1;
getanti(pos);
add[pos]=(mod-add[pos])%mod;
return;
}midd;
pushdown(pos,l,mid,r);
upd(L,R,lef);upd(L,R,rgt);
pushup(pos);
}
inline char cinchar(){
register char c=getchar();
while(c!='I'&&c!='R'&&c!='Q') c=getchar();
return c;
}
int main(){
for(register int t=0;t<maxn;++t) c[t][0]=1;
for(register int t=1;t<maxn;++t)
for(register int i=1;i<=20;++i)
c[t][i]=(c[t-1][i-1]+c[t-1][i])%mod;
int n=qr(),q=qr();
build(all);
for(register int t=1,t1,t2,t3;t<=q;++t){
register char c=cinchar();
if(c=='I'){
t1=qr();t2=qr();t3=(qr()%mod+mod)%mod;
upd(t1,t2,t3,all);
}
if(c=='R'){
t1=qr();t2=qr();
upd(t1,t2,all);
}
if(c=='Q'){
t1=qr(),t2=qr();t3=qr();
RET=::DP();
que(t1,t2,all);
printf("%d\n",RET[t3]);
}
}
return 0;
}