原题回顾

考点

1. 状态压缩DP
2. a与b互质：a与b的最大公约数是1（又是gcd算法）
3. DFS+剪枝（因为是填空题，没有TLE就是暴力的世界）

答案

如有不同答案，请xdm及时指出
881012367360

Code

方法一：dfs+剪枝解法（方法应该没有问题，但是跑的时间太长了）

1. 如果下一个可走楼号和当前楼号不是互质，则进行剪枝
2. dfs慢的解释（援引一下z总 @彩色铅笔的话）：这类问题dfs最多搜到10，DP的记忆化搜索是对它的一种优化

N = 25
state = [0] * N
state[1] = 1  # 总是从1号楼出发的
path = [0] * N
path[1] = 1


def gcd(a, b):
    if b:
        return gcd(b, a % b)
    return a


def dfs(u):
    # 考察第u个位置
    global res
    if u == n + 1:
        res += 1
        return

    # 开始填第u个位置的数
    for i in range(2, n + 1):
        if not state[i]:
            # 如果第i号楼没有走过，先试着走一下
            if gcd(i, path[u - 1]) == 1:   # 剪枝
                path[u] = i
                state[i] = 1
                dfs(u + 1)
                state[i] = 0
                path[u] = 0


if __name__ == "__main__":
    n = int(input())
    res = 0

    dfs(2)
    print(res)

方法二：状态压缩DP解法

1. 集合{i,j}：从$0$到$j$，走过的点用$i$进行存储，的所有路径
2. 属性：数量
3. 状态计算：$f[i][j] = \sum_{k=0}^{n-1} {f[i - \lbrace j \rbrace ][k]}$
4. 已知信息：$f[1][0] = 1$
   注：1 << 22比较大，创建需要大量开销，所以这题主委会把楼的数量定在了21hhh

N = 22
M = 1 << N  # 一共有M种不同的状态，eg："11000...001"
graph = [[-1] * N for _ in range(N)]  # 邻接矩阵
f = [[0] * N for _ in range(M)]  # {i,j}:从1 -> j，经过的点由i存储的所有路径


def gcd(a, b):
    if b:
        return gcd(b, a % b)
    return a


def add(a, b):
    graph[a][b] = graph[b][a] = 1


def DP():
    f[1][0] = 1

    for i in range(1 << n):
        for j in range(n):
            if (i >> j & 1):
                for k in range(n):
                    if (i - (1 << j) >> k & 1) and graph[k][j] == 1:
                        f[i][j] += f[(i - (1 << j))][k]

    res = 0
    for i in range(1, n):
        res += f[(1 << n) - 1][i]

    return res


if __name__ == "__main__":
    n = int(input())
    # 按要求添加边(a与b互质)
    for i in range(1, n + 1):
        for j in range(i + 1, n + 1):
            if gcd(i, j) == 1:
                add(i - 1, j - 1)

    print(DP())