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{aligned} 00010111_2 = 23\\ 00011101_2 = 29 \end{aligned}\]

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)