2021年蓝桥杯A组省赛-回路计数

题目

题解

动态规划。

最经典的哈密顿回路的题就是ACwing动态规划基础课的题和算法进阶指南中的了，都是用于讲解状压dp的。（但我还是没想到）

f [ i ] [ j ] f[i][j] f[i][j] 表示从起点（任意）走到 j j j ，经过的所有点用状态 i i i 表示，所有的方案数。 i i i 被我们认为是个二进制数，每一位表示从起点到 j j j 是否经过对应的点。从最低位到最高位分别对应点 0 ∼ n − 1 0\sim n-1 0∼n−1，状态 i i i 的第 k k k 位（从低到高，从 0 0 0 开始）二进制位为 1 1 1 表示状态 i i i 经了第 k k k 个点（从 0 0 0 开始），当对应位为 0 0 0 时同理。

转移方程本质上就是由倒数第二个点来推出 j j j。假设当前计算 f [ i ] [ j ] f[i][j] f[i][j]，那么经过状态 i i i 到达 j j j 的方案数等于从起点不经过点 j j j 到达全部与 j j j 点可达的点 k k k 方案数，也就是 s → . . . → k → j s\rightarrow...\rightarrow k\rightarrow j s→...→k→j。显然，如果不可达就不能加。

初始化， f [ s ] [ 0 ] = 1 f[s][0]=1 f[s][0]=1，表示自己到自己是一种方案。

最后我们只需要累加经过全部点，且能与起点可达的方案数即可。因为本题的起点是 1 1 1，所以与任何数的最大公因子都是 1 1 1，即与任意一点都可达，所以将全部非起点的方案数累加即可。

一定要注意对于解决哈密顿回路问题的状压dp是单源解法，即只能计算固定起点到其他点的方案数或最小路径等。而且起点信息并不体现在状态定义和状态转移中。

代码

#include
using namespace std;
typedef long long LL;
const int N = 22;

int n = 5;
LL ans;
int st[N][N];
LL f[1