题目描述

蓝桥学院由 $21$ 栋教学楼组成，教学楼编号 $11$​​ 到 $21$​​。对于两栋教学楼$a$和$b$​，当$a$和$b$互质时，$a$和$b$之间有一条走廊直接相连，两个方向皆可通行，否则没有直接连接的走廊。

小蓝现在在第一栋教学楼，他想要访问每栋教学楼正好一次，最终回到第一栋教学楼（即走一条哈密尔顿回路），请问他有多少种不同的访问方案？

两个访问方案不同是指存在某个 $i$，小蓝在两个访问方法中访问完教学楼 $i$后访问了不同的教学楼。

提示：建议使用计算机编程解决问题。

答案提交

这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

运行限制

最大运行时间：1s
最大运行内存: 128M

思路和参考代码

本题可以使用动态规划的方法解决。

我们用$1,2,...,21$表示某1栋楼，设全集 A = { 1 , 2 , . . . , 21 } A = \{1,2,...,21\} A={1,2,...,21}。设状态$S_{V,l}$表示访问了子集$V$中的全部路径（每个点均只访问1次）且最后一次落点在$l$处的可行解的个数，其中$V\subseteq A$，$l\in V$。即有动态规划方程
S V , l = ∑ a ∈ V 且 a , l 互质 S V − { l } , a S { 1 } , 1 = 1 S_{V,\ l} = \sum_{a\in V且a,l互质} S_{V- \{l\},\ a} \\S_{\{1\},\ 1 }= 1 SV, l​=a∈V且a,l互质∑​SV−{l}, a​S{1}, 1​=1

最终的答案为${\sum }_{i=2}^{21}{S}_{A,i}$。由于只有21栋楼，因此在实现时路径集合$V$只需要使用位集压缩在1个int变量中，如经过了完整的21栋楼，经过的路径为0x1fffff。

完整实现如下：

public class Main {static boolean[][] isConnected = new boolean[22][22];static final int MAXN = 0x1fffff;static long[][] counts = new long[MAXN + 1][22];static void init() {for (int i = 1; i <= 21; i++) {for (int j = i + 1; j <= 21; j++) {boolean flag = false;for (int k = 2; k <= i; k++) {if (i % k == 0 && j % k == 0) {flag = true;break;}}if (!flag) {isConnected[i][j] = isConnected[j][i] = true;}}}}static void debug() {for (int i = 1; i <= 21; i++) {for (int j = i + 1; j <= 21; j++) {if (isConnected[i][j])System.out.printf("%d %d\n", i, j);}}}static void dp() {counts[1][1] = 1;for (int i = 1; i <= MAXN; i++) {for (int j = 1; j <= 21; j++) {if (((i >> (j - 1)) & 1) == 0)continue;for (int k = 1; k <= 21; k++) {if (((1 << (k - 1)) & i) != 0 || !isConnected[j][k])continue;counts[i | (1 << (k - 1))][k] += counts[i][j];}}}}static void printAnswer() {long cnt = 0;for (int i = 1; i <= 21; i++) {if (isConnected[i][1])cnt += counts[MAXN][i];}System.out.println(cnt);}public static void main(String[] args) {init();
//        debug();dp();printAnswer();}
}