蓝桥杯省赛2021 回路计数 python

题目描述

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

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

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

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

状压 dp。

由于教学楼的个数很少，我们考虑用一个二进制位数等于 21的数来表示教学楼的访问状态。

对于该二进制数，如果它的第 i位（二进制下）的值为 1，则表示当前状态下第 i栋教学楼已经访问过一次了；若它的第 i 位（二进制下）的值为 0，则表示当前状态下第 ii 栋教学楼还未访问。

于是可以定义 dp[i][j] 表示当前的状态为 i，最后走到的教学楼为 j 的方案数。

那么转移方程为：

dp[i + 1 <

其中需满足对于状态 i，教学楼 k并未访问过（即 (i >> k & 1) = 0 ） 且 j,k间存在路径（g[j][k]!=0）

最后答案为 ∑​dp[(1<<21)−1][i]=881012367360(0<=i<=20)

终点可以在任意一点：因为1与任何数都互质，所以无论在哪，最终都要回到起点。

# python 跑的相当慢，不过这是道填空题就无所谓了
import math
n=1<<21
dp = [[0] * (22) for i in range(n+1)]
g = [[0 for i in range(22)] for i in range(22)]

for i in range(1, 22):
    for j in range(1, 22):
        if math.gcd(i, j) == 1:
            g[i - 1][j - 1] = g[j - 1][i - 1] = 1
dp[1][0] = 1
i = 1
while i < n:
    for j in range(0, 21):
        if (i >> j & 1) == 0:
            continue
        for k in range(0, 21):
            if g[j][k] == 0 or (i >> k & 1) != 0:
                continue
            dp[(i + (1 << k))][k] += dp[i][j]
    i += 1
res = 0
for i in range(0, 21):
    res += dp[n - 1][i]
print(res)

1.建邻接表，判断两个教学楼之间是否有路

2.利用状压dp开始走

3.计算方案数