DP总结-状压dp
状压dp（状态压缩动态规划）是一种dp。（废话）
状压dp的核心就是把若干状态压缩为一个整数
通常要压缩的元素个数不超过 \(15\) ，此时状态数共有 \(2^{15}=32768\) 。
状压dp更多的是一种思想，常见于数位dp等需要记录大量信息的dp中。
集合的整数表示
注意，当集合元素个数较多的时候，可能需要使用
1ll<<n或者1ull<<n。
基本表示：
空集：0
大小为 \(n\) 的全集：
(1 << n) - 1
第 \(i\) 个元素 \(x_i\) ：1 << i
交集：
\(S\cap \{x_i\}\)
：(S >> i) & 1
\(S\cap
T\)：S & T
并集：
\(S \cup \{x_i\}\)
：S | (1 << i)
\(S \cup T\)
：S | T
绝对补集：
\(\sim\!S\) ：U^S 或
U-S 或 (~S) & U ，U为全集
相对补集：
\(S\setminus\{x_i\}\)
：S & (~(1 << i))
\(S\setminus T\) ：
S & (T^U)
集合的基数（元素个数）：
第一种不建议在使用C++20之前的版本使用。（但是可以偷懒）
int __builtin_popcount(unsigned int)
int __builtin_popcountll(unsigned long long)
// 虽然它参数是unsigned，但是可以直接传signed
int S = calc1();
cout << __builtin_popcount(S) << '\n';
long long T = calc2();
cout << __builtin_popcountll(T) << '\n';
第二种推荐使用
int popc(int x)
{
int cnt=0;
for(; x; x &= (x-1)) ++cnt; // 原理：每次去掉最后一位
return cnt;
}下面给出了一份代码，可以用来测试。
状压dp和一般的集合表示不太一样（毕竟是整数表示嘛）
例如 S=0010 表示的是 \(S\) 只有第 \(3\) 个元素
请注意代码均 #define int long long
了，下同。
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)())
void print(int S,int n)
{
for(int i=0; i<n; i++)
((S >> i) & 1) ? (cout << 1) : (cout << 0);
cout << ' ';
}
int popc(int x)
{
int cnt=0;
for(; x; x &= (x-1)) ++cnt;
return cnt;
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
// freopen("check.in","r",stdin);
// freopen("check.out","w",stdout);
int n = 8, S = (1<<1) + (1<<3) + (1<<5);
int U = (1 << n) - 1;
int rS = S ^ U; // S 的绝对补集
cout << "U = "; print(U,n); cout << '\n';
cout << "|U| = " << n << '\n';
cout << "---\n";
cout << "S = "; print(S,n); cout << '\n';
cout << "~S = "; print(rS,n); cout << '\n';
cout << "---\n";
int T = (1<<2) + (1<<5);
cout << "|T| = " << __builtin_popcountll(T) << '\n';
cout << "|T| = " << popc(T) << '\n';
cout << "T = "; print(T,n); cout << '\n';
cout << "---\n";
cout << "S ∩ T = "; print(S&T,n); cout << '\n';
cout << "S ∪ T = "; print(S|T,n); cout << '\n';
return 0;
}输出如下：
---
|T| = 2
|T| = 2
U = 11111111
|U| = 8
---
S = 01010100
~S = 10101011
---
|T| = 2
|T| = 2
T = 00100100
---
S ∩ T = 00000100
S ∪ T = 01110100 集合的枚举
枚举 \(n\) 个元素的所有子集
时间复杂度 \(O(2^n)\)
for(int i=0; i < (1 << n); i++) print(i,n);如果要枚举非空子集就这么写
for(int i=1; i < (1 << n); i++) print(i,n);如果要枚举非空真子集就这么写
for(int i=1; i < (1 << n) - 1; i++) print(i,n);枚举 \(S\) 所有的非空子集
时间复杂度 \({O(2^n)}\)
for(int i=S; i; i = (i-1) & S) print(i,n);如果要枚举非空真子集，只要这么写就行了
for(int i=S&(S-1); i; i = (i-1) & S) print(i,n);枚举大小为 \(n\) 的集合的所有非空子集的非空子集
时间复杂度 \(\color{red}{O(3^n)}\) （证明在下面）
用到了上面那个东西
for(int u=0; u < (1 << n); u++) // 枚举大小为n的集合的子集
{
print(u,n); cout << ": ";
for(int i=u; i; i = (i-1) & u) print(i,n); // 枚举这个子集的子集
cout << '\n';
}
/*
n=3的运行结果如下
000 :
100 : 100
010 : 010
110 : 110 010 100
001 : 001
101 : 101 001 100
011 : 011 001 010
111 : 111 011 101 001 110 010 100
*/复杂度证明：
枚举大小为 \(n\) 的集合 \(S\) 的子集的复杂度 \[ O\left(\sum_{T\subseteq S}2^{|T|}\right) \] 而 \(S\) 中大小为 \(k\) 的子集个数为 \(\binom{n}{k}\) ，则枚举非空子集的复杂度为 \[ O\left(\sum_{i=1}^n\dbinom ni 2^i\right) \] 根据二项式定理 \[ \sum_{i=1}^n\dbinom ni 2^i =\sum_{i=1}^n\dbinom ni 2^i1^{n-i} =(1+2)^n-1 =O(3^n) \qquad\square \]
枚举 \(n\) 个元素的所有大小为 \(k\) 的子集
时间复杂度 \(O(2^n)\)
常数可能小一些，用处不是很大，而且不好记，目前没碰到过有用的地方。
int i = (1<<k)-1;
while(i < (1<<n))
{
int x = i&(-i), y = i+x; print(i,n);
i = ((( i & (~y) ) / x) >> 1) | y;
}可能还有，待补。。咕咕咕。。。
同样的，示例代码：
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)())
void print(int S,int n)
{
for(int i=0; i<n; i++)
((S >> i) & 1) ? (cout << 1) : (cout << 0);
cout << ' ';
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
// freopen("check.in","r",stdin);
// freopen("check.out","w",stdout);
int n = 3,k;
cout << "\n----\n"; cout << "all:\n";
for(int i=0; i < (1<<n); i++) print(i,n); // all
cout << "\n----\n"; cout << "no empty:\n";
for(int i=1; i < (1<<n); i++) print(i,n); // no empty
cout << "\n----\n"; cout << "no empty && no U:\n";
for(int i=1; i < (1<<n)-1; i++) print(i,n); // no empty && no U
cout << "\n----\n";
n = 8;
int S = (1<<0) + (1<<2) + (1<<5);
cout << "S = "; print(S,n); cout << '\n';
// subset (no empty)
for(int i=S; i; i= (i-1) & S) print(i,n);
cout << "\n----\n";
// sub's sub in 3^n
n = 3;
for(int u=0; u < (1 << n); u++)
{
print(u,n); cout << ": ";
for(int i=u; i; i = (i-1) & u) print(i,n);
cout << '\n';
}
cout << "----\n";
n = 3; k = 2;
int i = (1<<k)-1;
while(i < (1<<n))
{
int x = i&(-i), y = i+x; print(i,n);
i = ((( i & (~y) ) / x) >> 1) | y;
}
cout << "\n----\n";
return 0;
}输出（加了个代码高亮便于区分...）
----
all:
000 100 010 110 001 101 011 111
----
no empty:
100 010 110 001 101 011 111
----
no empty && no U:
100 010 110 001 101 011
----
S = 10100100
10100100 00100100 10000100 00000100 10100000 00100000 10000000
----
000 :
100 : 100
010 : 010
110 : 110 010 100
001 : 001
101 : 101 001 100
011 : 011 001 010
111 : 111 011 101 001 110 010 100
----
110 101 011
----斯坦纳树
详见 斯坦纳树 学习笔记
一种较为有趣的状压dp，涉及有关三角不等式的转移。
一些题目
直接在博客里搜状压dp就好了，这里是很久以前写的东西。
状态：压缩状态表示集合中 \(1\sim15\) 是否出现（本题要求拆分出非空集）
转移方程：略
枚举集合，并枚举这个集合所有的真子集
for(int i=1; i<(1<<15); i++) // 所有可能的集合（要非空，不然无须dp，如果强行可能会挂）
{
// do something ... （本题有个判断）
for(int k=(i-1)&i; k; k=(k-1)&i) // 对于每个集合，枚举其所有「非空真子集」
/*if(sxr[k]==0)*/ d[i]=min(d[i],d[k]+d[i^k]);
// 这里的if是本题目需要的判断
// 后面的d[k]+d[i^k]就是将每个拆分成两个不同的非空子集的答案之和
}这里枚举的是一个非可重集中1~15的存在情况（ \(0\) 不影响异或和，所以不管）
而题目中需要知道这个集合的异或和，可以这样写
for(int i=1;i<(1<<15);i++) // 每个集合
for(int j=0;j<15;j++)if((i>>j)&1)sxr[i]^=(j+1);
// j+1就是原来这个数，第j位是状态AT2657 [ARC078D] Mole and Abandoned Mine
详见 AT2657 [ARC078D] Mole and Abandoned Mine 题解
参考文献：
[1] 《挑战程序设计竞赛（第二版）》秋叶拓哉 等
[2] 《离散数学（第六版）》屈婉玲 等
[3] https://yhx-12243.github.io/OI-transit/records/ac2657%3Barc078F.html
[4] https://www.cnblogs.com/CDOI-24374/p/15876755.html
![AT2657 [ARC078D] Mole and Abandoned Mine 题解](/medias/featureimages/p115.png)