2021蓝桥杯省赛C++A组试题E 回路计数 状态压缩DP

题目描述

蓝桥学院由21栋教学楼组成，教学楼编号1到21。对于两栋教学楼a和b，当a和b互质时，a和b之间有一条走廊直接相连，两个方向皆可通行，否则没有直接连接的走廊。
小蓝现在在第一栋教学楼，他想要访问每栋教学楼正好一次，最终回到第一栋教学楼（即走一条哈密尔顿回路)，请问他有多少种不同的访问方案?两个访问方案不同是指存在某个i，小蓝在两个访问方法中访问完教学楼i后访问了不同的教学楼。
提示:建议使用计算机编程解决问题。

解题思路

哈密尔顿回路是经典的NP难问题，暴力搜索效率太低，到后面时间非常长。采用状态压缩DP，可以在2秒左右完成遍历求解，时间可以接受。
dp数组解释：dp[i][j]表示当前正在i结点，走过的路径为j时的方案数。
状态转移方程：dp[j][S|(1<
解释：从i结点转移到j结点，当前到达j结点，S为到达i结点时所走过的结点序列（二进制表示，如10101表示走过了1、 3、 5三结点，没有走过2、 4两个结点），则dp[j][S|(1<即下一个结点的访问方案数为其所有前驱结点访问方案数的和。

注意：本题结果数字很大，dp数组和结果都要使用long long类型

答案

881012367360

代码实现

（关键代码已加注释）

#include
using namespace std;

typedef long long ll;

const int n=21;
bool G[n][n];//边采用邻接矩阵存储
ll dp[n][1<