可逆背包
问题简介
考虑这样一个问题：有 $n$ 个物品，体积分别是 $w_1,w_2,\cdots,w_n$，背包容量为 $m$，共有 $n$ 次询问，第 $i$ 次询问要求不选物品 $i$ 时共有多少选法装满背包。
思路分析
如果对于每个询问依次求 01 背包问题，单次询问需要 $O(nm)$ 的时间，总复杂度 $O(n^2m)$。而退背包能让我们不需要对于每个询问都进行完整的 DP，而是用 $O(m)$ 时间去掉选择了物品 $i$ 的方案数，那么整个过程需要一次 $O(nm)$ 的DP和 $n$ 次 $O(m)$ 的退背包/加背包过程，整体复杂度就降到了 $O(nm)$。
算法步骤
1. 执行一次 01 背包算法过程
for(int j=m;j>=w[i];--j)
f[j]+=f[j-w[i]];
2. 对每个物品，将其看作是最后一个加入背包的物品，然后减掉它的方案数
memcpy(g,f,sizeof f);
for(int j=w[i];j<=m;++j)
g[j]-=g[j-w[i]];
例题
例 1
题意
有 $n$ 个物品，体积分别是 $w_1,w_2,\cdots,w_n$，现第 $i$ 个物品丢失，用剩下的 $n-1$ 个物品装满容积为 $x$ 的背包，有几种方法。把答案记为 $cnt(i,x)$，要得到所有 $i\in[1,n],x\in[1,m]$ 的 $cnt(i,x)$ 表格。输出 $n\times m$ 的矩阵，表示 $cnt(i,x)$ 的末位数字。
$1\le n,m\le 2000$。
题解
令 $f[j][0]$ 表示不算消失的物品组成容积为 $j$ 的方案数，即 01 背包问题，令 $f[j][1]$ 表示删掉某个物品后组成容积为 $j$ 的方案数。初始化是 $f[0][0]=f[0][1]=1$，即容积为 0 时方案数为 1
#include<bits/stdc++.h>
using namespace std;
const int N=2e3+5;
int f[N][2],w[N];
int main(){
int n,m;
scanf("%d %d",&n,&m);
for(int i=1;i<=n;i++) scanf("%d",&w[i]);
f[0][0]=f[0][1]=1;
for(int i=1;i<=n;i++){
for(int j=m;j>=w[i];j--){
f[j][0]=(f[j][0]+f[j-w[i]][0])%10;
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(j-w[i]>=0) f[j][1]=(f[j][0]-f[j-w[i]][1]+10)%10;
else f[j][1]=f[j][0]%10;
printf("%d",f[j][1]);
}
puts("");
}
return 0;
}
例 2
题意
给定一个长度为偶数的由大小写字母组成的字符串 $s$，一个“好”字符串可通过重排字母顺序使得所有相同字母的位置都在 $s$ 的同一半（$[1,n/2] or [n/2+1,n]$）来生成。$q$ 个询问，给定一对 $(i,j)$，要求字母 $s[i],s[j]$ 也在 $s$ 的同一半的“好”字符串数量。
题解
注意到询问本质上最多只有 $52^2$ 种可能，则考虑先把所有询问算出来，最后 $O(1)$ 回答询问。
令 $k$ 为字母种数，统计各字母的出现次数 $c_1,c_2,\cdots,c_k$，若有 $i_1,i_2,\cdots,i_p$ 使得 $c_{i_1}+c_{i_2}+\cdots+c_{i_p}=\dfrac{n}{2}$，则把它们放到第一组，剩下的放到第二组，第一组的排列数为 $\dfrac{(\dfrac{n}{2})!}{c_{i_1}!c_{i_2}!\cdots c_{i_p}!}$，第二组排列数为 $\dfrac{(\dfrac{n}{2})!}{c_{j_1}!c_{j_2}!\cdots c_{j_s}!}$，总方法数为 $W=\dfrac{(\dfrac{n}{2})!(\dfrac{n}{2})!}{c_1!c_2!\cdots c_k!}$；
注意到 $c_i$ 求和为 $\dfrac{n}{2}$ 的组合数可用 01 背包来求，在没有 $(i,j)$ 限制下的“好”字符串数量为 $W*dp[n/2]*2$；
现考虑 $(i,j)$ 的限制，即字母 $s[i]$ 和 $s[j]$ 需在同一组中，等价于去掉字母 $s[i]$ 和 $s[j]$ 的 01 背包问题，即作了一次 01 背包问题后，再枚举 $i,j$ 做退背包过程，将去掉 $(i,j)$ 的 DP 值记作 $ans[i][j]$；
最后对每个询问直接 $O(1)$ 输出答案即可。
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5,mod=1e9+7;
typedef long long ll;
ll fastpow(ll x,ll y){
ll ret=1;
for(;y;x=x*x%mod,y>>=1)
if(y&1) ret=ret*x%mod;
return ret;
}
int conv(int x){
if(x>='a') return x-'a'+26;
return x-'A';
}
ll dp[N],fac[N],inv[N],temp_dp[N];
ll ans[55][55];
ll w[55];
int main(){
string s;
cin>>s;
int n=s.length();
fac[0]=1;
w[conv(s[0])]++;
for(int i=1;i<n;i++){
w[conv(s[i])]++;
fac[i]=fac[i-1]*i%mod;
}
fac[n]=fac[n-1]*n%mod;
inv[n]=fastpow(fac[n],mod-2);
for(int i=n-1;i>=0;i--) inv[i]=inv[i+1]*(i+1)%mod;
ll W=fac[n/2]*fac[n/2]%mod;
for(int i=0;i<52;i++){
if(w[i]) W=W*inv[w[i]]%mod;
}
dp[0]=1;
for(int i=0;i<52;i++){
if(w[i]){
for(int j=n;j>=w[i];j--){
dp[j]=(dp[j]+dp[j-w[i]])%mod;
}
}
}
for(int i=0;i<52;i++) ans[i][i]=dp[n/2];
for(int i=0;i<52;i++){
if(!w[i]) continue;
for(int k=0;k<=n;k++) temp_dp[k]=dp[k];
for(int k=w[i];k<=n;k++) temp_dp[k]=(temp_dp[k]-temp_dp[k-w[i]]+mod)%mod;
for(int j=i+1;j<52;j++){
if(!w[j]) continue;
for(int k=w[j];k<=n;k++) temp_dp[k]=(temp_dp[k]-temp_dp[k-w[j]]+mod)%mod;
ans[i][j]=2ll*temp_dp[n/2]%mod;
ans[j][i]=ans[i][j];
for(int k=n;k>=w[j];k--) temp_dp[k]=(temp_dp[k]+temp_dp[k-w[j]])%mod;
}
}
int q;
scanf("%d",&q);
while(q--){
int x,y;
scanf("%d%d",&x,&y);
int l=conv(s[x-1]);
int r=conv(s[y-1]);
printf("%lld\n",W*ans[l][r]%mod);
}
return 0;
}
