2021省赛 E. 回路计数

题意

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

状态压缩dp板子题，求方案数，权值就是方案数，每次加上走到k的权值即可

由于每个数都和1互质，所以都有一条通往1的路，所以统计每个点的dp值即可
ps:
- 不仅需要判断去除j点后，k是否存在，还要判断j,k是否有边

代码

'''
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)