2021省赛 E. 回路计数
摘要
Title: 2021省赛 E. 回路计数
Tag: 哈密顿路径、状压dp
Memory Limit: 64 MB
Time Limit: 1000 ms
Powered by:NEFU AB-IN
2021省赛 E. 回路计数
-
题意
蓝桥学院由 21 栋教学楼组成，教学楼编号 1 到 21。对于两栋教学楼 a 和 b，当 a 和 b 互质时，a 和 b之间有一条走廊直接相连，两个方向皆可通行，否则没有直接连接的走廊。
小蓝现在在第一栋教学楼，他想要访问每栋教学楼正好一次，最终回到第一栋教学楼（即走一条哈密尔顿回路），请问他有多少种不同的访问方案？
两个访问方案不同是指存在某个 i，小蓝在两个访问方法中访问完教学楼 i 后访问了不同的教学楼。 -
思路
状态压缩dp板子题，求方案数，权值就是方案数，每次加上走到k的权值即可
由于每个数都和1互质，所以都有一条通往1的路，所以统计每个点的dp值即可
ps:- 不仅需要判断去除j点后，k是否存在，还要判断j,k是否有边
-
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36'''
Author: NEFU AB-IN
Date: 2022-03-16 16:29:18
FilePath: \ACM\LanQiao\2021E.py
LastEditTime: 2022-03-16 16:48:17
'''
N = 21
M = 1 << 21
import math
def gcd(a, b):
return gcd(b, a % b) if b else a
dp = [[0] * N for _ in range(M)]
g = [[0] * N for _ in range(N)]
for i in range(1, 22):
for j in range(i + 1, 22):
if gcd(i, j) == 1:
g[i - 1][j - 1] = g[j - 1][i - 1] = 1
dp[1][0] = 1
for i in range(M):
for j in range(N):
if i >> j & 1:
pre = i - (1 << j)
for k in range(N):
if g[j][k] and (pre >> k & 1):
dp[i][j] += dp[pre][k]
res = 0
for i in range(1, 22):
res += dp[M - 1][i - 1]
print(res)