一、关于状压 dp

为了规避不确定性，我们将需要枚举的东西放入状态。当不确定性太多的时候，我们就需要将它们压进较少的维数内。

常见的状态：

• 天生二进制（开关、选与不选、是否出现……）
• 爆搜出状态，给它们编号

1. 状态跟某一个信息集合内的每一条都有关。（如 dp 套 dp）

2. 若干条精简而相互独立的信息压在一起处理。 (如每个数字是否出现)

在使用状压 dp 的题目当中，往往能一眼看到一些小数据范围的量，切人点明确。而有些题，这样的量并不明显，需要更深人地分析题目性质才能找到。

二、预备知识

1. 位运算

二进制数 S 从低（0-based）到高第 i 位的值：(S>>i)&1

二进制数 S 从低（0-based）到高第 i 位的值变为 1：S|(1<<i)

二进制数 S 从低（0-based）到高第 i 位的值变为 0：S&(~(1<<i)) 或 ~((~S)|(1<<i))

二进制数 S 从低（0-based）到高第 i 位的值取反：S^(1<<i)

2. 枚举子集

for(int i=S;i!=0;i=(i-1)&S)

复杂度：

(2n-1) 的子集：2n

(2n-1) 的子集的子集和：3n

(2n-1) 的子集的子集的子集和：4n

……

三、例题

1. TSP（旅行商问题）

题目大意：一个 n 个点的带权的有向图，求一条路径，使得这条路径经过每个点恰好一次，并且路径上边的权值和最小。n≤16。

Solution：

设 dp[i][S] 表示目前走到节点 i，已经经过节点的集合为 S 的最小边权。

枚举所有的边 (i,j)∈E，令 w(i,j) 表示它的边权。

if j∉S（因为要满足经过每个点恰好一次，即不能重复经过，所以要满足 j 没有被经过），dp[i][S]+w(i,j)→dp[j][S∪{j}]

若 S&(1<>j)&1 是否为 1。

初始化一个节点的路径 dp[i][1<<i]=0（节点编号为 0~n-1）或 dp[i][1<<(i-1)]=0（节点编号为 1~n），其他的设为 ∞。

把 j 加入到 S：S +/|/^ (1<<j)。因为已经确认了 S 的这一位是 0，则 +，|，^ 都是可以的。

时间复杂度：O(2n·n2)

2. [USACO06NOV] 玉米田 Corn Fields

题目大意：有一个 N*M 的网格图，已知若干个格子不能选、不能有相邻的格子被选。在不限制所选格子总数的前提下，求方案数。N,M≤12。

Solution：

由于限制在相邻的格子上，若按行或按列 dp，就不需要维护之前已经决策过的格子的状态，而是维护一行或一列的格子的状态。

令 dp[i][j] 表示目前 dp 到第 i 行，这一行的状态是 j，所有 1~i 行内的格子被选的方案数。

枚举 i+1 行的状态 k，判断 k 与 j 是否有冲突（是否出现某个格子的上面一个格子被选了的情况，即是否有相邻的格子被选），只需判断 j&k 是否为 1（j 的二进制数与 k 的二进制数是否有在相同的位置同时等于 1）。

dp[i][j]→dp[i+1][k]

预处理出没有相邻的两列同时被选的状态。在一行 12 个格子的网格图中，没有相邻的两列同时被选的合法的状态大概有 377 个。

int ans=0;
for(int i=0;i<(1<<12);i++){ bool flag=1; for(int j=1;j<=11;j++) if(((i>>(j-1))&1)&&((i>>j)&1)) flag=0;
if(flag) ++ans;
}
printf("%lld\n",ans);
//Output:377

所以通过预处理，可以通过此题。

Code：

#include
#define int long long
using namespace std;
const int N=13,M=(1<<12)+5,mod=1e9; int n,m,a[N][N],p[N],f[N][M],ans; bool v[M]; signed main(){ scanf("%lld%lld",&m,&n),f[0][0]=1; for(int i=1;i<=m;i++) for(int j=1;j<=n;j++){ scanf("%lld",&a[i][j]); p[i]=(p[i]<<1)+a[i][j]; //记录第 i 行土地的状态 } for(int i=0;i<(1<>(j-1))&1)&&((i>>j)&1)) v[i]=0;
} //记录状态 i 是否合法（预处理出没有相邻的两列同时被选的状态）
for(int i=1;i<=m;i++) //枚举行
for(int j=0;j<(1<<n);j++) //枚举这行的状态
if(v[j]&&(j&p[i])==j) //判断状态 j 是否合法以及是否在肥沃的土地上
for(int k=0;k<(1<<n);k++) //枚举上一行的状态
if(!(k&j)) f[i][j]=(f[i][j]+f[i-1][k])%mod;
for(int i=0;i<(1<<n);i++)
ans=(ans+f[m][i])%mod; //前 m 行的方案数累加
printf("%lld\n",ans);
return 0;
}

3. TopCoder RainbowGraph

题目大意：给出一张 N 个点 M 条边的无向图。每个点有一个颜色。一条路径是合法的当且仅当它按顺序经过的节点的颜色序列写下来，同种颜色出现的位置是连续的。计算合法的经过每个节点恰好一次的路径条数。N≤100，Color≤10（颜色数），对于任意的 i，Cnt(v|Colorv=i)≤10（每种颜色的节点数）。

Solution：

既然同种颜色出现的位置是连续的。我们不妨将问题划分成两个小问题考虑：

• 对于颜色 c，从 i 出发到 j 结束，同时遍历完所有该颜色节点的路径条数是多少。
• 对于全局，有多少种安排颜色的方法、及安排颜色之间“接口”的方法。

第一个问题：将同种颜色内的串起来。

要求：（1）每个点恰好出现一次（2）相邻两点之间有边相连

令 dp[i][j][S] 表示从 i 号点出发，在 j 号点结束，经过的节点集合为 S 的路径条数。

for(int i=0;i>p)&1)&&G[j][p]) //p 在状态中没有出现过（之前没有经过这个点）并且之前路径的终点 j 能够到达下一个点 p
dp[i][p][S|(1<<p)]+=dp[i][j][S];

注：这里所有的节点编号，为了方便体现，直接写成了 i 之类的。事实上，需要开一个数组维护，把全局当中的颜色为当前颜色的节点转化到 0~k 的范围内。

第二个问题：将每种颜色串起来。

要求：（1）每种颜色恰好出现一次（则需记录颜色状态 2C）（2）相邻颜色的首尾节点间有边相连（则需记录终点 N）

对于一种颜色 c，我们使用 f[c][i][j] 来代表之前的 dp[全局中编号为 i 的点][全局中编号为 j 的点][(1<<k)-1]。

令 dp[i][S] 表示以节点 i 结尾，已经经过的颜色集合为 S 的总方案数。

for(int c=0;c>c)&1)) //这个颜色在之前的状态中没有出现过
for(int j=0;j<k[c];j++) //枚举下一个颜色的起点
if(G[i][id[j]]) //当前的终点与下一个起点有边可以到达
for(int q=0;q<k[c];q++) //枚举下一个颜色的终点
dp[id[q]][S|(1<<c)]+=dp[i][S]*f[c][j][q];

4. TopCoder CheeseRolling

题目大意：N 个人打淘汰赛。N 是 2 的幂次。给出两两单挑的胜负情况。一共有 N! 种赛程安排方案，对于每个人，你需要输出有多少种方案使他最终获胜。n≤16。

Solution：

令 dp[i][S] 表示编号为 i 的选手是选手集合 S 中的优胜者的方案数。

那么最后每个点的答案就是 dp[i][(1<<N)-1]

枚举 i 能够战胜的对手 j，然后将集合 S 等分为两个一个包含 i 一个包含 j 的集合。

for(int i=0;i>i)&1) //集合 S 包含 i
for(int j=0;j<N;j++) //枚举 i 所击败的对手 j
if(i!=j&&G[i][j]) //i 和 j 不是同一个人并且 i 能够击败 j
for(int k=(S-1)&S;k!=0;k=(k-1)&S) //枚举子集
dp[i][S]+=2LL*dp[i][k]*dp[j][S^k];

复杂度为 O(3n·n2)，偏高，需要优化。

• 优化 1：valid 这部分有很多冗余状态，可以预处理出来有效的部分。
• 优化 2：把子集改成 dfs 精确枚举等分子集。

5. AtCoder 058E Iroha and Haiku

题目大意：

一个有 N 个元素且每个元素的取值都在 1~10 范围内的序列被称为好的当且仅当存在下标 x,y,z,w（0≤x<y<z<w≤N）

• ax+ax+1+…+ay-1=X
• ay+ay+1+…+az-1=Y
• az+az+1+…+aw-1=Z

计数。并对 109+7 取模。3≤N≤40，1≤X≤5，1≤Y≤7，1≤Z≤5。

Solution：

做法 1：当你不知道如何优雅地设计状态/不知道状态的规模有多大时，不妨暴力一点。

因为 X≤5，Y≤7，Z≤5，所以 X+Y+Z≤5+7+5，即 X+Y+Z≤17，ax+ax+1+…+ay-1+ay+ay+1+…+az-1+az+az+1+…+aw-1≤17。

只需维护取值 1~10，和≤17 的序列。

#include
#define int long long
using namespace std;
int cnt;
void dfs(int x){
if(x>17) return ;
++cnt;
for(int i=1;i<=10;i++) dfs(x+i);
}
signed main(){
dfs(0),printf("%lld\n",cnt);
return 0;
}
//Output:130624

大约 105 个状态，做法就显而易见了。

一个 dp 序列当中的元素，每次只保留最靠后的值不超过 17 的元素队列。

dp[i][S][0/1] 表示当前 dp 到序列中第 i 个元素，队列的状态为 S，是否出现过题中所述条件。

一些优化：

• 优化 1：每个状态是否满足题中条件可预处理。
• 优化 2：每个状态遇到了 1~10 后转移到什么状态可预处理。（需要一个作用在 vector上的 map 或是 set、二分等）
• 优化 3：状态当中的第三维可以通过求补集而去掉。

不难观察得到，算法的复杂度瓶颈主要是由状态的 vector 形态带来的。

做法 2：思路和前面类似，只不过考虑换个形式表示“和不超过 17”这个状态。

如果我们将这“X+Y+Z”点贡献展开看成一条长度为 X+Y+Z 的格子，一个数可以占领 1~10 个格子。那么我们关心的即为位置在 X、X+Y、X+Y+Z 的三个格子是否是一个数所占领格子的末尾。我们考虑将一个数末尾标为 1，其他格子标为 0。

例子：X=Y=Z=2，后缀状态：

2+2+2

010101

1+1+2+2

110101

2+1+1+2

011101

1+2+2+1

101011

Code：

//开始的格子为 1 的写法
#include
#define int long long
using namespace std;
const int N=50,M=(1<<17)+5,mod=1e9+7;
int n,x,y,z,st,dp[N][M],sum=1,k,ans;
signed main(){
scanf("%lld%lld%lld%lld",&n,&x,&y,&z);
st=((1<<(x+y+z-1)))|(1<<(y+z-1))|(1<<(z-1)); //目标从后往前数的第 X+Y+Z、Y+Z、Z 的位置为 1
dp[0][0]=1;
for(int i=1;i<=n;i++){
sum=sum*10%mod; //计算总方案数（n 位数字，就有 10^n 种方案）
for(int S=0;S<(1<<(x+y+z));S++) //枚举状态
if(dp[i-1][S]&&(S&st)!=st)
for(int c=1;c<=10;c++){ //枚举第 i 位添加的数字
k=((S<<c)|(1<<(c-1)))&((1<<(x+y+z))-1);
//(S<<c)|(1<<(c-1)): 比如 4 的二进制数为 1000，4 后面加上 2 为 4 2，用 100010 表示，即将 4 的二进制向前两位再加上 10。
//…&((1<<(x+y+z))-1: 防止溢出
dp[i][k]=(dp[i][k]+dp[i-1][S])%mod;
}
}
for(int S=0;S<(1<<(x+y+z));S++)
if((S&st)!=st) ans=(ans+dp[n][S])%mod;
printf("%lld\n",(sum-ans)%mod); //总方案数减不符合条件的方案
return 0;
}

6. AtCoder XOR Tree

题目大意：给出一棵 N 个节点的树，每条树边有一个边权。.每次操作你可以将一条路径上的边权异或上某个值。问最少进行多少次操作可以达到边权全 0。N≤105，0≤边权≤15。

Solution：

首先定义一个点的点权为与其相邻的所有边的边权异或和。

容易证明边权全为 0 等价于点权全为0。

• 边权为 0→点权为 0：根据定义显然
• 点权为 0→边权为 0：来自树的性质，总是存在叶子结点。叶子结点上的点权为 0 可推出一条边权为 0。删去后重复这一过程。

每次操作就可以看成是将任意两个点异或上同一个数。

• 如果是两个相同的数，一次操作就可以直接将这俩消去。
• 如果是两个不同的数 a,b，那么一次操作可以消去一个，剩下一个 a^b。

思考一下要不要考虑同时异或一个不为 a 也不为 b 的数 x。

因为一共只有 16 种取值，我们先将重复的直接消去。剩下的信息只有 0~15 每个数字是否出现过，可以压成一个 216 的状态。

每次枚举一下要操作哪两个数。

• x^y∉S：转移到的状态就是 S∪x^y，即 S^(1<<(x^y))。
• x^y∈S：此次操作之后就会产生一对相等的 pair，我们直接在此时将它们一并消去，增加一次操作，并将 x^y 从 S 中去掉即可。

7. Codeforces 16E Fish

题目大意：有 n 条鱼，刚开始它们都自由地生活在水里。接下来每一时刻会有两条鱼相遇。所有可能的“鱼对”之间都是等概率出现这一事件的。鱼 i 和鱼 j 相遇后，i 吃掉 j 的概率为 a[i][j]。 反之 j 吃掉 i 的概率为 1-a[i][j]。求每条鱼 i 活到最后的概率。N≤19。

Solution：

令 dp[S] 表示剩下集合中的鱼状态为 S 的概率。

初始化：dp[2n-1]=1（刚开始全部的鱼都存活）

对于任意 1≤i≤n，dp[2i] 为鱼 i 活到最后的概率。

按从大到小枚举状态 S（按时刻进行），设 c 为 S 中 1 的个数，则有 C(c,2) 个可能的“鱼对”。枚举第一条被选的鱼 i 以及第二条被选的鱼 j，这两条鱼相遇的概率为 1/C(c,2)。

• i 吃掉 j：1/C(c,2)·dp[S]·a[i][j]→dp[S-2j]
• j 吃掉 i：1/C(c,2)·dp[S]·a[j][i]→dp[S-2i]

最后输出所有的 dp[2i] 即可。

Code：C(c,2)=c*(c-1)/2

#include
#define int long long
using namespace std;
const int N=20,M=(1<<18)+5; int n,x,cnt; double a[N][N],dp[M]; signed main(){ scanf("%lld",&n),dp[(1<=1;S--){ //枚举状态
cnt=0,x=S;
while(x) cnt+=x&1,x>>=1; //计算 S 中 1 的个数
for(int i=0;i<n;i++) if(S&(1<<i)) //枚举第一条鱼
for(int j=i+1;j<n;j++) if(S&(1<<j)){ //枚举第二条鱼
dp[S-(1<<j)]+=dp[S]*a[i][j]/(1.0*cnt*(cnt-1)/2); //i 吃掉 j
dp[S-(1<<i)]+=dp[S]*a[j][i]/(1.0*cnt*(cnt-1)/2); //j 吃掉 i
}
}
for(int i=0;i<n;i++)
printf("%.6lf%c",dp[1<<i],i==n-1?'\n':' ');
return 0;
}

8. Codeforces 165E Compatible Numbers

题目大意：给出一个长度为 N 的序列，我们称两个数 x,y 是兼容的，当且仅当 x&y=0。对于序列中的每个数，你需要求出任意一个序列中与它兼容的数，或是声明不存在。N≤106，0<a[i]≤4·106。

Solution：

暴力做法：由于数值大小可以存下。令 M 为 >=max{a(i)} 的某个 2k-1。与序列中的某个数 x 兼容的所有数可以表示为 M xor x 的子集。做一下子集枚举，我们得到了一个 O(3k) 的做法。（本题中，k≤22）， 这个做法要跑 3e10。

一点改进：令 f(S) 表示 S 的子集中是否有数出现过。F(x) 表示 x 是否在序列中出现过。

那么有：f(S)=F(S)|⋁i∈S f(S\i)

从小到大枚举 S, 每次计算 f 的值时就不需要枚举子集，只用枚举 S 中的元素 v 即可。还能剪枝，当 f(S) 为真时就不需要再枚举下去了。

9. Codeforces 743E Vladik and cards

题目大意：给出一个长度为 N 个序列，序列中的元素取值为 1~8。求一个最长的子序列满足：

• 每种取值出现在子序列中的位置连续。
• 每种取值出现的次数相差不超过 1。N≤1000。

10. Codeforces 599E Sandy and Nuts

题目大意：有一棵 N 个点的树， 1 号点为根节点。现在你知道 M 条信息：

• 某些树上的边 (u,v)
• 某两个点的LCA (a,b,c)

现在你需要数满足条件的树形态数。N≤13，M≤100。