第十二届蓝桥杯 ——回路计数

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

业余算法学徒

6616人浏览 · 2021-05-14 21:07:09

业余算法学徒 · 2021-05-14 21:07:09 发布

问题描述
蓝桥学院由 21 栋教学楼组成，教学楼编号 1 到 21。

对于两栋教学楼 a 和 b，当 a 和 b 互质时，a 和 b 之间有一条走廊直接相连，两个方向皆可通行，否则没有直接连接的走廊。

小蓝现在在第一栋教学楼，他想要访问每栋教学楼正好一次，最终回到第一栋教学楼（即走一条哈密尔顿回路），

请问他有多少种不同的访问方案？两个访问方案不同是指存在某个 i，小蓝在两个访问方法中访问完教学楼 i 后访问了不同的教学楼。

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

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

答案：881012367360

题解
状压DP：

f[i][j]：从 1 走到 j，且经过的点的状态为 i 的方案数；

#include <iostream>
using namespace std;

typedef long long LL;

const int N = 22, M = 1 << N;

LL f[M][N];
bool e[N][N];

int gcd(int a, int b)
{
	return b ? gcd(b, a % b) : a;
}

int main()
{
	for (int i = 1; i <= 21; i ++)
		for (int j = 1; j <= 21; j ++)
			if(gcd(i, j) == 1)
				e[i][j] = true;
				
	f[2][1] = 1;
	for (int i = 2; i <= M - 2; i ++)
		for (int j = 1; j <= 21; j ++)
			if(i >> j & 1)
				for (int k = 1; k <= 21; k ++)
					if(i - (1 << j) >> k & 1 && e[k][j])
						f[i][j] += f[i - (1 << j)][k];
	
	LL ans = 0;
	for (int i = 2; i <= 21; i ++)
		ans += f[M - 2][i];
	
	cout << ans << endl;		
	return 0;								
}

ps：要运行 13 秒，但是可以将 1 ~ 21 映射成 0 ~ 20，效率会快一倍，代码如下；

#include <iostream>
using namespace std;

typedef long long LL;

const int N = 21, M = 1 << N;

LL f[M][N];
bool e[N][N];

int gcd(int a, int b)
{
	return b ? gcd(b, a % b) : a;
}

int main()
{
	for (int i = 1; i <= 21; i ++)
		for (int j = 1; j <= 21; j ++)
			if(gcd(i, j) == 1)
				e[i - 1][j - 1] = true;
				
	f[1][0] = 1;
	for (int i = 1; i <= M - 1; i ++)
		for (int j = 0; j <= 20; j ++)
			if(i >> j & 1)
				for (int k = 0; k <= 20; k ++)
					if(i - (1 << j) >> k & 1 && e[k][j])
						f[i][j] += f[i - (1 << j)][k];
	
	LL ans = 0;
	for (int i = 1; i <= 20; i ++)
		ans += f[M - 1][i];
	
	cout << ans << endl;	
	return 0;								
}