【题解】P4247 [清华集训]序列操作(线段树修改DP)

Love The Way You Lie 2021-11-18 01:16 241阅读 0赞

## 【题解】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; }

转载于:https://www.cnblogs.com/winlere/p/11015266.html