蓝桥杯2021回路计数

本文是针对2021年蓝桥杯省赛回路计数的题解

回路计数

一. 题目

题目链接

二. 题目分析

​ 从一个固定的点走过其他点再回到起点的方案数，总计21个点

思路：

• 根据题意得出邻接矩阵

• 利用回溯dfs递归求解，很明显思路很清晰但是现实很骨感，最差得是21的阶乘，得到结果都猴年马月了

• 放弃dfs的想法，查阅资料题解基本采用状态压缩dp

  先了解一下什么叫状态压缩，就是使用某种方法，简明扼要地以最小代价来表示某种状态，通常是用一串01数字（二进制数）来表示各个点的状态。这就要求使用状态压缩的对象的点的状态必须只有两种，0 或 1。

  其实很容易联想到要用状压，每栋楼是否被访问就可以用0和1表示

  而状压dp就是使用状态压缩的动态规划

  动态规划问题大体分为两种，一种是对递归化问题的记忆求解，另一种是把大问题看作是多阶段的决策求解，这里应该算第二种，存储之前的状态再由状态及状态对应的值推演出状态转移方程得出最终解

• 具体求解思路

  看dp，将原问题划分成多个子问题进行求解

  原问题为 访问完每栋教学楼一次，又回到一号教学楼的不同方案数，那么21个1(111..11)可以表示为访问了所有教学楼一次，题意说明每个教学楼都可以回到一号教学楼(互质，这里不做解释)，所以可以进行划分

  当访问状态为全1时的方案数 == 该状态且最后一次访问的楼是2号楼的方案数加上该状态最后一次为3，4，5…..的方案数和

  dp[i] [j] += dp[i - (1>>j)] [1到21(两点间有边且该点符合i状态也就是在i中是被访问过的)]

• 题目分析完毕 开干

三. 代码

import math

def huzhi(a, b):
    if math.gcd(a, b) == 1:
        return True
    else:
        return False

tu = [[0 for i in range(22)] for j in range(22)]
for i in range(2, 22):
    tu[1][i] = 1

for i in range(2, 22):
    # 这里第二层循环从i+1开始 其实也没什么必要 影响不大
    for j in range(i + 1, 22):
        if huzhi(i, j):
            tu[i][j] = 1
         
for i in range(2, 22):
    for j in range(1, i):
        tu[i][j] = tu[j][i]
# 以上为求邻接矩阵部分 

# for i in range(1, 22):
#     for j in range(1, 22):
#         print(tu[i][j], end=" ")
#     print()

# 采用dfs 21的阶乘不行
# ans = 0
# visit = [0] * 22
# 
# def dfs(step, np):
#     global ans
#     if step == 21:
#         if np == 1:
#             ans += 1
#         return
#     else:
#         for i in range(1,22):
#             if np == i or visit[i] == 1 or tu[np][i] == 0:
#                 continue
#             visit[i] = 1
#             dfs(step + 1, i)
#             visit[i] = 0
# dfs(0,1)
# 上述dfs代码没有测试 应该思路就是这个

# 采用状态压缩dp

dp = [[0] * 21 for i in range(1 << 21)]
dp[1][0] = 1 #状态只访问过一号楼且现在在一号楼有一种方案
for i in range(1 << 21):
    for j in range(21):
        if i >> j & 1:#判断j是否在i这个状态中被访问过
            for k in range(21):
                if tu[j + 1][k + 1] == 1 and i >> k & 1:
                    dp[i][j] += dp[i - (1 << j)][k]

print(sum(dp[(1 << 21) - 1]) - dp[(1 << 21) - 1][0])

得出最终结果：881012367360