棋牌型状压dp与集合型状压dp

状压dp

概述

状压dp就是把自然语言中难以用1个数字表示的dp状态使用一个数字表示的dp。状压只是个把戏，关键还是在转移。转移的过程在思考时很正常，在实现的时候一般需要依托位运算，所以对于基本的位运算要比较清楚，并且要积累一些位运算本身的坑点。

常见考法与技巧

棋盘型状压dp（基于连通性的dp）

这种类型的dp常常是需要我们往一个棋盘里面放棋子，存在相对禁止位置与绝对禁止位置，问我们至多能放多少个棋子/有多少种放棋子的方案。

解决这种问题的一般思路是一行一行地递推，算出来前i行已经填好，且第i行的填法是j的这类方案（也有可能需要考虑更前面的行是怎么填的，这个根据题目的相对禁止位置规则来决定）最多能填多少/方案有多少。在递推的时候，枚举第i - 1行的状态，然后看看能否转移到第i行的j状态，能的话则计入贡献。

这种类型的dp在实现的时候需要注意的细节就是确定哪些状态是合法状态，哪些转移是合法转移。我们一般可以预处理出所有的合法状态，在转移的时候只枚举每行的合法状态就好了。如果还想优化常数/方便转移（由于状压dp是指数复杂度，故很多时候我们不得不做这一点），我们甚至可以预处理出能够转移到某状态j的其他的所有合法状态，以邻接表的形式存储下来，这样我们的dp转移的时候会更好实现（由此我们也可以看出dp和图论之间的巨大联系）。

集合型状压dp

这种类型的状压dp需要我们记录的状态一般是之前我们做过了哪些操作/选过了哪些东西，而这些操作/东西的选法是被压成一个整数来表示的。最典型的例子便是哈密顿回路计数以及重复覆盖问题。

以哈密顿回路计数为例子：

有一张图，共有1-21这21个点，对于图中的任意两点i和j，当$\gcd(i, j) = 1$时，i和j之间存在一条双向路径。求从1号点出发存在多少条哈密顿回路（从1号出发，访问其他各个点恰好一次，最终返回1号点）。

参考代码：

#include <bits/stdc++.h>

using namespace std;

const int N = 22;

typedef long long ll;

vector<int> g[N];

ll dp[N][(1 << N)], n;

ll gcd(ll a, ll b) {
    if (b == 0) return a;
    return gcd(b, a % b);
}

void print(int u, int state) {
    printf("(%d, ", u);
    for (int i = 0; i < n; i++) {
        printf("%d", state & 1);
        state >>= 1;
    }
    printf(")\n");
}

void dfs(int u, int state) {
    // print(u, state);
	
    if (state == 0) {
        if (u == 1) {
            dp[u][0] = 1;
        } else {
            dp[u][0] = 0;
        }
        return;
    }
	
    if (dp[u][state] >= 0) {
        return;
    }
	
    dp[u][state] = 0;
    for (int i = 0; i < (int) g[u].size(); i++) {
        int j = g[u][i];
        if (((state >> (j - 1)) & 1) != 0) {
            int s = (state & (~(1 << (j - 1))));
            dfs(j, s);
			
            dp[u][state] += dp[j][s];
        }
    }
}

int main() {
    cin >> n;
	
    for (int i = 1; i <= n; i++) {
        for (int j = i + 1; j <= n; j++) {
            if (gcd(i, j) == 1) {
                g[i].push_back(j);
                g[j].push_back(i);
            }
        }
    }
	
    memset(dp, -1, sizeof dp);
	
    // 设dp[i][j]表示当前在点i，且之前走过的所有点的点集是j的点的集合
    // 的走法数
    // 采用记忆化搜索控制转移顺序
    // 初始化dp[1][0] = 1， 其他的都为未计算，其他的dp[i][0]被要求计算时直接赋值0
    // 最终关心的答案是dp[1][(1 << n) - 1]
	
	
    dfs(1, (1 << n) - 1);
	
    printf("%lld\n", dp[1][(1 << n) - 1]);
	
    return 0;
}

这里我又写了记忆化，因为我想不太清楚到底应该按照什么样的循环顺序去递推。dp优化你别过来呀