退背包介绍
之前居然完全没了解过“退背包”，其实是个很易于接受的思路，看了下最简单的板子题居然是个黄题，离谱。
退背包的原理在于根据题意与状态设计，阶段顺序并不影响最终的答案，因此之前某个阶段的贡献是可以撤销的。
具体撤销的方法就是通过原先从 \(f_{i-1}\) 转移到 \(f_i\) 的状态转移方程进行代数推导推出由 \(f_i\) 转移到 \(f_{i-1}\) 的转移式。具体步骤不难，但要有“阶段是可以撤回的”这个意识，并且要分清楚什么时候是“阶段顺序不影响结果”什么时候是影响的。
通过下面这道题我们来感受一下退背包的思路与流程。
例题
涉及知识点：动态规划、回退背包
题意
有 \(n\ (\leq10^6)\) 个顾客，每个顾客要么买 \(x\in[1,a_i]\) 幅彩色画，要么买 \(y\in[1,b_i]\) 幅黑白画，要求至少有 \(C\ (\leq50)\) 个人买彩色画，求有多少种买画方案，对 \(10^9+7\) 取模。
思路
首先发现 \(C\) 非常小，突破点就在 \(C\)。我们反过来，将总共的购买方案数减去买了少于 \(C\) 幅彩色画的方案数，因此我们现在只需要求出后者。如果没有修改，DP 已经呼之欲出了。
设 \(f[i][j]\) 为第 \(i\) 个人，共有 \(j\) 个人买了彩色画的方案数，转移方程如下：
\[f[i][j]=f[i-1][j]*b_i+f[i-1][j-1]*a_{i} \]怎么处理修改呢？我们会发现，由于其组合意义，把任何一个人当作最后一个人都可以，因此假设我们要删去某个人 \(p\) 的贡献：
\[f[i-1][j]=\frac{f[i][j]-f[i-1][j-1]*a_p}{b_p} \]注意上式计算 \(f[i-1][j]\) 时用到了 \(f[i-1][j-1]\)，那么 \(f[i-1][j-1]\) 又是怎么求出来的呢？
可以发现当 \(j=0\) 的时候，要删去某个人的贡献直接除以它的 \(b_i\) 即可，因此我们就算出来了 \(f[i-1][0]\)，接着递推即可。
那么对于题目中的修改操作，我们就处理为先倒推撤销修改前那个人的贡献，再正推算出修改后那个人的贡献即可，修改一次的复杂度仅为 \(O(C)\)，完全足够通过本题。
代码
#include<bits/stdc++.h>
using namespace std;
#ifdef ONLINE_JUDGE
#define getchar __getchar
inline char __getchar(){
static char ch[1<<20],*l,*r;
return (l==r&&(r=(l=ch)+fread(ch,1,1<<20,stdin),l==r))?EOF:*l++;
}
#endif
template<class T>inline void rd(T &x){
T res=0,f=1;
char ch=getchar();
while(ch<'0' || ch>'9'){if(ch=='-')f=-1; ch=getchar();}
while('0'<=ch && ch<='9'){res=res*10+ch-'0';ch=getchar();}
x=res*f;
}
template<class T>inline void wt(T x,char endch='\0'){
static char wtbuff[20];
static int wtptr;
if(x==0){
putchar('0');
}
else{
if(x<0){x=-x;putchar('-');}
wtptr=0;
while(x){wtbuff[wtptr++]=x%10+'0';x/=10;}
while(wtptr--) putchar(wtbuff[wtptr]);
}
if(endch!='\0') putchar(endch);
}
typedef long long LL;
typedef pair<int,int> pii;
const LL P=1e9+7;
const int MAXN=1e6+5,MAXC=55;
int n,c,q;
LL tot=1,f[MAXC];
pii cus[MAXN];
inline LL qpow(LL a,LL b=P-2){
LL res=1;
a%=P;
while(b){
if(b&1) res=res*a%P;
a=a*a%P;
b/=2;
}
return res;
}
int main(){
// freopen("pic.in","r",stdin);
// freopen("pic.out","w",stdout);
rd(n);rd(c);
for(int i=1;i<=n;i++) rd(cus[i].first);
for(int i=1;i<=n;i++) rd(cus[i].second);
f[0]=1;
for(int i=1;i<=n;i++){
tot=tot*(cus[i].first+cus[i].second)%P;
for(int j=c-1;j>=0;j--){
f[j]=(f[j]*cus[i].second%P + (j?f[j-1]*cus[i].first%P:0))%P;
}
}
rd(q);
int id,a,b;
while(q--){
rd(id);rd(a);rd(b);
LL sum=0,invb=qpow(cus[id].second);
tot=tot*qpow(cus[id].first+cus[id].second)%P;
for(int i=0;i<c;i++){
f[i]=(f[i] - (i?f[i-1]*cus[id].first%P:0) +P)%P*invb%P;
}
cus[id]=make_pair(a,b);
tot=tot*(cus[id].first+cus[id].second)%P;
for(int i=c-1;i>=0;i--){
f[i]=(f[i]*cus[id].second%P + (i?f[i-1]*cus[id].first%P:0))%P;
}
for(int i=0;i<c;i++) sum=(sum+f[i])%P;
wt((tot-sum+P)%P,'\n');
}
return 0;
}