Project Euler 265

发表于 2022-07-04 更新于 2023-07-03 分类于 Project Euler 阅读次数： 144 本文字数： 811 阅读时长 ≈ 1 分钟

Project Euler 265

题目

Binary Circles

$2^{N}$ binary digits can be placed in a circle so that all the $N$ -digit clockwise subsequences are distinct.

For $N = 3$ , two such circular arrangements are possible, ignoring rotations:

For the first arrangement, the $3$ -digit subsequences, in clockwise order, are: $000, 001, 010, 101, 011, 111, 110$ and $100$ .

Each circular arrangement can be encoded as a number by concatenating the binary digits starting with the subsequence of all zeros as the most significant bits and proceeding clockwise. The two arrangements for $N = 3$ are thus represented as $23$ and $29$ :

$\begin{array}{r} 00010111_{2} = 23 \\ 00011101_{2} = 29 \end{array}$

Calling $S (N)$ the sum of the unique numeric representations, we can see that $S (3) = 23 + 29 = 52$ . Find $S (5)$ .

解决方案

本题没有太多需要注意的地方。直接把一个个二进制数视为一个节点，每个节点都有两条出边。然后再在图上寻找哈密顿回路即可。

OEIS 上的数列 A016031 提到， $2^{N}$ 个 $N$ 比特串上述的环排列一共有 $2^{2^{N - 1} - N}$ 个。

代码

N = 5
M = 1 << N
mask = (1 << N) - 1
g = [[i << 1 & mask, (i << 1 | 1) & mask] for i in range(M)]
vis = [0 for i in range(M)]
vis[0] = 1
ans = 0


def dfs(f: int, u: int, s: int):
    if f == M - 1:
        if u == (M >> 1):
            global ans
            ans += s >> (N - 1)
        return
    for v in g[u]:
        if vis[v]:
            continue
        vis[v] = 1
        dfs(f + 1, v, s << 1 | (v & 1))
        vis[v] = 0


dfs(0, 0, 0)
print(ans)