For a fixed \(n\), we want binary circles in which every \(n\)-bit block appears exactly once as a cyclic substring. The problem asks for the sum of the binary integers represented by all such circles, using the canonical representation chosen by the solver.
The implementation does not search the space of bit strings directly. Instead, it models the problem as an Eulerian-cycle search in a De Bruijn graph and enumerates every valid cycle with depth-first backtracking.
A binary circle of order \(n\) is a cyclic bit sequence whose cyclic length-\(n\) substrings are exactly the \(2^n\) possible \(n\)-bit patterns. That condition is naturally encoded by the De Bruijn graph of order \(n\).
The graph has:
$$|V|=2^{n-1},\qquad |E|=2^n.$$
Each vertex is an \((n-1)\)-bit string. Each edge is an \(n\)-bit string, viewed as a transition from its first \(n-1\) bits to its last \(n-1\) bits.
If the current node is \(u\) and we append a bit \(b\in\{0,1\}\), then the next edge label is
$$e=((u\ll 1)\,|\,b)\ \&\ (2^n-1),$$
and the next node is its suffix of length \(n-1\):
$$v=e\ \&\ (2^{n-1}-1).$$
So the DFS is literally walking through the De Bruijn graph one edge at a time, where every edge corresponds to one \(n\)-bit block.
Traversing every edge exactly once means that every \(n\)-bit pattern appears exactly once. That is precisely the definition of the required binary circle.
Conversely, any binary circle determines a closed walk in the graph, because consecutive length-\(n\) windows overlap in their last \(n-1\) bits. Therefore the problem is equivalent to enumerating Eulerian cycles in this directed graph.
Cycles are circular, so the same cycle can be rotated. The solver removes this rotational ambiguity by fixing the starting block to be \(0^n\). In the code this is done by marking edge 0 as already used and starting the DFS at node 0.
This anchor gives one canonical representative per cycle. Without it, the same circle would be found multiple times under different rotations.
The recursive search keeps:
1. a boolean array of used edges,
2. the current node,
3. the partial bit sequence being built.
At each step it tries bit 0 and bit 1. If the corresponding edge has not been used, it marks the edge, appends the bit, and recurses to the suffix node. After returning, it undoes the choice and continues with the next branch.
This is a standard backtracking enumeration of all Eulerian cycles from the fixed root.
The invariant is simple: the set of used edges is exactly the set of edges already traversed in the partial walk, and the current node is the suffix of the last traversed edge.
If all \(2^n\) edges have been used and the walk returns to node 0, then the partial walk is a closed Eulerian cycle. If any edge remains unused, then the walk is incomplete and cannot yet represent a valid binary circle.
Because the DFS tries every unused outgoing edge at every step, every Eulerian cycle rooted at \(0^n\) is enumerated exactly once.
The code stores the current bit stream in sequence. Once a full cycle has been found, the first \(2^n\) bits of that stream are interpreted as a binary integer:
$$X=\sum_{i=0}^{2^n-1} b_i\,2^{2^n-1-i}.$$
That value is added to the running total. The solver therefore sums the canonical integer representative of every valid binary circle.
A tiny worked example is \(n=2\). The unique anchored cycle produces the bit prefix
$$0011,$$
whose cyclic windows are
$$00,\ 01,\ 11,\ 10.$$
These are exactly the four 2-bit patterns, and the canonical integer is
$$0011_2=3,$$
which matches the checkpoint \(S(2)=3\).
The program verifies two sample values:
$$S(2)=3,\qquad S(3)=52.$$
These checks are useful because they confirm both the graph construction and the integer-conversion logic before larger searches are attempted.
For \(n=3\), the two canonical cycles found by the solver are
$$00010111_2=23,\qquad 00011101_2=29,$$
so
$$S(3)=23+29=52.$$
The program accepts --n and --skip-checkpoints. solve(n) first computes the edge count \(2^n\) and the node mask \(2^{n-1}-1\). The array used_edge marks which \(n\)-bit blocks have already been traversed. The vector sequence starts with \(n\) zero bits, which is the anchored \(0^n\) block.
The lambda dfs explores the two possible extensions from the current node. When a candidate edge is unused, it is marked, its trailing bit is appended, and the recursion continues from the suffix node. Once all edges are used and the walk has returned to node 0, the solver converts the collected bit stream into a binary integer and adds it to total.
The checkpoint routine simply compares the results of solve(2) and solve(3) against the expected sample values.
The solver enumerates Eulerian cycles by backtracking, so the running time is exponential in \(n\). That is unavoidable here because the number of valid binary circles itself grows rapidly with \(n\).
Memory usage is \(O(2^n)\), dominated by the edge-usage array and the current bit sequence. The recursion depth is also proportional to the cycle length.
Für ein festes \(n\) werden binäre Kreise gesucht, in denen jedes \(n\)-Bit-Muster genau einmal als zyklischer Teilstring vorkommt. Das Programm summiert die binären Ganzzahlen, die durch alle solchen Kreise repräsentiert werden.
Statt Bitfolgen direkt zu durchsuchen, formuliert der Solver das Problem als Eulerkreis-Suche in einem De-Bruijn-Graphen und enumeriert alle Lösungen per DFS.
Ein binärer Kreis der Ordnung \(n\) ist eine zyklische Bitfolge, deren zyklische Länge-\(n\)-Fenster genau die \(2^n\) möglichen \(n\)-Bit-Muster bilden. Genau das wird durch den De-Bruijn-Graphen der Ordnung \(n\) modelliert.
Der Graph besitzt
$$|V|=2^{n-1},\qquad |E|=2^n.$$
Jeder Knoten ist ein \((n-1)\)-Bit-Wort, jede Kante ein \(n\)-Bit-Wort.
Aus dem aktuellen Knoten \(u\) und einem angehängten Bit \(b\in\{0,1\}\) entsteht die Kante
$$e=((u\ll 1)\,|\,b)\ \&\ (2^n-1),$$
und der Folgeknoten ist der Suffix-Knoten
$$v=e\ \&\ (2^{n-1}-1).$$
Die DFS läuft also direkt über den Graphen und benutzt jede Kante als genau ein \(n\)-Bit-Fenster.
Jede Kante genau einmal zu durchlaufen bedeutet, dass jedes \(n\)-Bit-Muster genau einmal erscheint. Das ist exakt die gesuchte Bedingung.
Umgekehrt liefert jede gültige Kreisfolge einen geschlossenen Walk im Graphen, weil benachbarte \(n\)-Bit-Fenster um \(n-1\) Bits überlappen. Daher ist das Problem äquivalent zur Enumeration aller Eulerkreise.
Da Kreise rotierbar sind, würde dieselbe Lösung sonst mehrfach auftreten. Der Solver fixiert deshalb den Startblock \(0^n\). Im Code geschieht das durch das Vormarkieren von Kante 0 und den Start der DFS am Knoten 0.
Damit erhält jede Kreislösung genau einen kanonischen Repräsentanten.
Die Rekursion verwaltet:
1. ein Bool-Array für benutzte Kanten,
2. den aktuellen Knoten,
3. die bisher aufgebaute Bitfolge.
Für jedes Bit 0 und 1 wird geprüft, ob die zugehörige Kante noch frei ist. Falls ja, wird sie markiert, das Bit angehängt und rekursiv weitergesucht. Nach der Rückkehr wird die Entscheidung zurückgenommen.
Die Invariante ist klar: Benutzte Kanten sind genau die bereits durchlaufenen Kanten des partiellen Walks, und der aktuelle Knoten ist der Suffix der letzten Kante.
Sind alle \(2^n\) Kanten benutzt und ist der Walk wieder bei Knoten 0, dann ist ein Eulerkreis gefunden. Solange noch Kanten fehlen, ist die Folge unvollständig und noch kein gültiger Kreis.
Da die DFS an jeder Stelle alle unbenutzten Ausgänge ausprobiert, wird jeder bei \(0^n\) verankerte Eulerkreis genau einmal enumeriert.
Die aktuelle Bitfolge wird im Vektor sequence gespeichert. Nach einem vollständigen Kreis werden die ersten \(2^n\) Bits als Binärzahl gelesen:
$$X=\sum_{i=0}^{2^n-1} b_i\,2^{2^n-1-i}.$$
Dieser Wert wird zur Gesamtsumme addiert.
Ein kleines durchgerechnetes Beispiel ist \(n=2\). Der eindeutige verankerte Kreis erzeugt das Bitpräfix
$$0011,$$
dessen zyklische Fenster
$$00,\ 01,\ 11,\ 10$$
sind. Das sind genau alle vier 2-Bit-Muster, und der kanonische ganzzahlige Repräsentant ist
$$0011_2=3,$$
was exakt zum Checkpoint \(S(2)=3\) passt.
Das Programm prüft die Beispielwerte
$$S(2)=3,\qquad S(3)=52.$$
So werden Graphkonstruktion und Zahlenumrechnung vor größeren Läufen verifiziert.
Für \(n=3\) findet der Solver die beiden kanonischen Kreise
$$00010111_2=23,\qquad 00011101_2=29,$$
also
$$S(3)=23+29=52.$$
Das Programm akzeptiert --n und --skip-checkpoints. solve(n) berechnet zunächst \(2^n\) und die Maske \(2^{n-1}-1\). Das Array used_edge markiert bereits besuchte \(n\)-Bit-Blöcke. Der Vektor sequence beginnt mit \(n\) Nullen und repräsentiert damit den verankerten Block \(0^n\).
Die Lambda-Funktion dfs probiert die beiden möglichen Fortsetzungen aus. Ist eine Kandidatenkante noch unbenutzt, wird sie markiert, ihr letztes Bit angehängt und dann vom Folgeknoten aus weitergesucht. Sobald alle Kanten benutzt sind und der Walk zum Knoten 0 zurückkehrt, wird die Bitfolge in eine Ganzzahl umgerechnet und zu total addiert.
Die Checkpoints vergleichen lediglich solve(2) und solve(3) mit den bekannten Werten.
Die Suche enumeriert Eulerkreise per Backtracking, daher ist die Laufzeit exponentiell in \(n\). Das ist hier unvermeidlich, weil auch die Anzahl der gültigen Kreise schnell wächst.
Der Speicherbedarf ist \(O(2^n)\), dominiert durch Kantenmarkierungen und die aktuelle Bitfolge. Auch die Rekursionstiefe wächst proportional zur Kreislänge.
Sabit bir \(n\) için, her \(n\)-bit bloğunun döngü üzerinde tam bir kez göründüğü ikili çevrimler aranır. Çözüm, bu çevrimlerin temsil ettiği tamsayıları toplar.
Kod, bit dizilerini doğrudan taramak yerine problemi De Bruijn grafı üzerinde Euler çevrimi sayımına dönüştürür ve bütün geçerli çevrimleri DFS ile üretir.
Derecesi \(n\) olan bir binary circle, döngüsel uzunluğu \(n\) olan blokların tüm \(2^n\) olası \(n\)-bit desenleri birer kez içerdiği çevrimsel bir bit dizisidir. Bu yapı De Bruijn grafıyla tam olarak modellenir.
Grafın boyutları:
$$|V|=2^{n-1},\qquad |E|=2^n.$$
Her düğüm \(n-1\) bitlik bir durumdur, her kenar ise \(n\) bitlik bir geçiştir.
Mevcut düğüm \(u\) iken bit \(b\in\{0,1\}\) eklenirse yeni kenar
$$e=((u\ll 1)\,|\,b)\ \&\ (2^n-1),$$
ve yeni düğüm
$$v=e\ \&\ (2^{n-1}-1)$$
olur. DFS bu geçişi birebir uygular.
Her kenarı tam bir kez gezmek, her \(n\)-bit desenin tam bir kez görünmesi demektir. Bu da istenen koşuldur.
Tersine, geçerli her çevrim art arda gelen \(n\)-bit pencerelerin \(n-1\) bit üst üste binmesi nedeniyle graf üzerinde kapalı bir yol verir. Yani cevaplar tam olarak Euler çevrimleridir.
Döngüsel yapıda aynı çözüm farklı rotasyonlarla tekrar eder. Bu tekrarları kaldırmak için başlangıç bloğu \(0^n\) sabitlenir. Kodda bu, 0 numaralı kenarın baştan kullanılmış işaretlenmesi ve DFS'nin 0 düğümünden başlamasıyla sağlanır.
Özyineleme üç şeyi saklar:
1. kullanılmış kenarlar,
2. mevcut düğüm,
3. kurulan bit dizisi.
Her adımda 0 ve 1 denenir. Uygun kenar kullanılmamışsa işaretlenir, bit eklenir ve bir sonraki düğüme geçilir. Geri dönünce seçim geri alınır.
İndüksiyon değişmezi şudur: kullanılan kenarlar, kısmi turun geçtiği kenarlarla aynıdır ve mevcut düğüm son kenarın suffix'idir.
Tüm \(2^n\) kenar kullanılmış ve yol tekrar 0 düğümüne dönmüşse bir Euler çevrimi bulunmuştur. Henüz kullanılmamış kenar varsa tur tamamlanmamıştır.
DFS her düğümde tüm kullanılmamış çıkışları denediği için, 0^n'e sabitlenmiş her Euler çevrimi tam bir kez üretilir.
Geçerli tur bulununca bit dizisi sequence içinde tutulur. Sonra ilk \(2^n\) bit ikili sayı olarak okunur:
$$X=\sum_{i=0}^{2^n-1} b_i\,2^{2^n-1-i}.$$
Bu değer toplam cevaba eklenir.
Küçük bir çalışan örnek \(n=2\) durumudur. Tek kanonik çevrim şu bit önekini üretir:
$$0011,$$
bunun döngüsel pencereleri de
$$00,\ 01,\ 11,\ 10$$
olur. Bunlar dört adet 2-bit desenin tamamıdır. Kanonik tamsayı da
$$0011_2=3$$
olur; bu da \(S(2)=3\) checkpoint'iyle tam uyuşur.
Program şu örnekleri doğrular:
$$S(2)=3,\qquad S(3)=52.$$
Böylece hem grafik kurulumu hem de sayı üretimi test edilmiş olur.
\(n=3\) için solver'ın bulduğu iki kanonik çevrim
$$00010111_2=23,\qquad 00011101_2=29$$
olduğundan
$$S(3)=23+29=52$$
elde edilir.
Program --n ve --skip-checkpoints seçeneklerini destekler. solve(n) önce \(2^n\) kenar sayısını ve \(2^{n-1}-1\) maske değerini hesaplar. used_edge dizisi hangi \(n\)-bit bloklarının kullanıldığını tutar. sequence vektörü \(n\) sıfır bit ile başlar; bu da sabitlenmiş \(0^n\) bloğudur.
dfs lambdası mevcut düğümden 0 ve 1 uzantılarını dener. Uygun kenar boştaysa işaretlenir, son biti eklenir ve komşu düğüme özyinelemeli geçilir. Tüm kenarlar bittiğinde ve düğüm 0'a döndüğünde, oluşturulan bit dizisi sayıya çevrilip total'a eklenir.
Checkpoint rutini yalnızca solve(2) ve solve(3) sonuçlarını beklenen değerlerle karşılaştırır.
Arama, Euler çevrimlerini backtracking ile ürettiği için zaman karmaşıklığı \(n\)'e göre üstel büyür. Bu kaçınılmazdır; çünkü geçerli binary circle sayısı da hızla artar.
Bellek kullanımı, kenar işaretleri ve geçici bit dizisi nedeniyle \(O(2^n)\)'dir. Özyineleme derinliği de tur uzunluğu kadar büyür.
Para un \(n\) fijo, se buscan ciclos binarios en los que cada bloque de \(n\) bits aparezca exactamente una vez como subcadena cíclica. La solución suma los enteros binarios representados por todos esos ciclos.
El programa no explora cadenas de bits directamente; traduce el problema a un conteo de ciclos eulerianos en un grafo de De Bruijn y los enumera con DFS.
Un círculo binario de orden \(n\) es una secuencia cíclica en la que los bloques cíclicos de longitud \(n\) son exactamente los \(2^n\) patrones posibles. Eso se modela de forma natural con el grafo de De Bruijn de orden \(n\).
El grafo tiene
$$|V|=2^{n-1},\qquad |E|=2^n.$$
Cada vértice es una cadena de \(n-1\) bits y cada arista es una cadena de \(n\) bits.
Si el nodo actual es \(u\) y se añade un bit \(b\in\{0,1\}\), la arista es
$$e=((u\ll 1)\,|\,b)\ \&\ (2^n-1),$$
y el nuevo nodo es
$$v=e\ \&\ (2^{n-1}-1).$$
La DFS sigue exactamente esta transición.
Recorrer cada arista exactamente una vez equivale a ver cada patrón de \(n\) bits exactamente una vez. Esa es justo la condición del problema.
Recíprocamente, cualquier ciclo válido produce un paseo cerrado en el grafo porque las ventanas consecutivas de longitud \(n\) se solapan en \(n-1\) bits. Por tanto, la tarea es enumerar ciclos eulerianos.
Como un ciclo puede rotarse, la misma solución aparecería varias veces. Para eliminar ese duplicado, el solver fija el bloque inicial \(0^n\). En el código esto se hace marcando la arista 0 como usada y empezando la DFS en el nodo 0.
La búsqueda mantiene:
1. un arreglo booleano de aristas usadas,
2. el nodo actual,
3. la secuencia parcial de bits.
En cada paso prueba los bits 0 y 1. Si la arista correspondiente no ha sido usada, la marca, añade el bit y continúa recursivamente. Al volver, deshace la elección.
La invariante es simple: las aristas usadas son exactamente las ya recorridas en el paseo parcial, y el nodo actual es el sufijo de la última arista.
Si se han usado las \(2^n\) aristas y el paseo vuelve al nodo 0, entonces se ha encontrado un ciclo euleriano. Si aún queda alguna arista sin usar, el paseo no está completo.
Como la DFS prueba todas las salidas no usadas en cada estado, cada ciclo euleriano anclado en \(0^n\) se genera exactamente una vez.
La secuencia de bits se guarda en sequence. Cuando se encuentra un ciclo completo, los primeros \(2^n\) bits se interpretan como un entero binario:
$$X=\sum_{i=0}^{2^n-1} b_i\,2^{2^n-1-i}.$$
Ese valor se suma al total.
Un ejemplo pequeño completamente resuelto es \(n=2\). El único ciclo anclado produce el prefijo de bits
$$0011,$$
cuyas ventanas cíclicas son
$$00,\ 01,\ 11,\ 10.$$
Esos son exactamente los cuatro patrones de 2 bits, y el entero canónico es
$$0011_2=3,$$
lo que coincide exactamente con el checkpoint \(S(2)=3\).
El programa comprueba
$$S(2)=3,\qquad S(3)=52.$$
Así se valida tanto el grafo como la conversión final.
Para \(n=3\), el solver encuentra los dos ciclos canónicos
$$00010111_2=23,\qquad 00011101_2=29,$$
por lo tanto
$$S(3)=23+29=52.$$
El programa acepta --n y --skip-checkpoints. solve(n) calcula primero el número de aristas \(2^n\) y la máscara de nodos \(2^{n-1}-1\). used_edge marca qué bloques de \(n\) bits ya se han visitado. sequence empieza con \(n\) ceros, que representan el bloque anclado \(0^n\).
La lambda dfs explora las dos extensiones posibles desde el nodo actual. Si una arista candidata está libre, se marca, se añade su último bit y se continúa desde el nodo sufijo. Cuando todas las aristas están usadas y el paseo regresa a 0, la secuencia se convierte en entero y se suma a total.
Los checkpoints sólo comparan solve(2) y solve(3) con sus valores esperados.
La búsqueda enumera ciclos eulerianos mediante backtracking, así que el tiempo es exponencial en \(n\). Esto es inevitable porque el número de ciclos válidos también crece muy rápido.
La memoria es \(O(2^n)\), dominada por las marcas de aristas y la secuencia actual de bits. La profundidad de la recursión también es proporcional a la longitud del ciclo.
给定固定的 \(n\)，要求找出那些二进制环：在环上每个 \(n\)-bit 块都恰好出现一次。程序把每个合法环解释成一个二进制整数，并把所有这些整数求和。
代码并不是直接枚举位串，而是把问题转化为 De Bruijn 图上的 Euler 回路搜索，再用 DFS 回溯枚举所有合法回路。
一个 \(n\) 阶二进制环，是一个循环位串，其中所有循环长度为 \(n\) 的子串恰好对应全部 \(2^n\) 种 \(n\)-bit 模式。这正好由 De Bruijn 图建模。
图的规模为
$$|V|=2^{n-1},\qquad |E|=2^n.$$
每个顶点是 \(n-1\) 位字符串，每条边是 \(n\) 位字符串。
若当前节点是 \(u\)，并追加位 \(b\in\{0,1\}\)，则得到边
$$e=((u\ll 1)\,|\,b)\ \&\ (2^n-1),$$
下一节点是其长度为 \(n-1\) 的后缀：
$$v=e\ \&\ (2^{n-1}-1).$$
DFS 正是按这个规则沿图移动。
每条边恰好走一次，就意味着每个 \(n\)-bit 模式恰好出现一次，这正是题目的要求。
反过来，任何合法二进制环都会在图上形成闭合走法，因为相邻的 \(n\)-bit 窗口会重叠 \(n-1\) 位。所以问题等价于枚举 Euler 回路。
环是可以旋转的，因此同一个解会出现多次。为了去掉旋转重复，程序把起始块固定为 \(0^n\)。代码里对应的是：边 0 先标记已使用，DFS 从节点 0 开始。
递归搜索维护三样东西：
1. 已使用边的布尔数组，
2. 当前节点，
3. 正在构造的位序列。
每一步尝试 0 和 1 两个分支。如果对应边未被使用，就标记它、追加该位，再递归进入后缀节点。回溯时撤销选择。
不变式很简单：已用边正好是部分路径经过的边，而当前节点就是最后一条边的后缀。
如果所有 \(2^n\) 条边都已经用完，并且路径回到节点 0，那么就找到了一条 Euler 回路。若还有边未用完，则路径还不完整，不能算合法答案。
由于 DFS 在每一步都尝试所有未使用的出边，所以每个固定起点为 \(0^n\) 的 Euler 回路都会且只会被枚举一次。
位串保存在 sequence 中。找到完整回路后，前 \(2^n\) 位被解释为一个二进制整数：
$$X=\sum_{i=0}^{2^n-1} b_i\,2^{2^n-1-i}.$$
然后把这个值加到总和里。
一个很小的完整例子是 \(n=2\)。唯一的锚定回路给出位前缀
$$0011,$$
它的循环窗口是
$$00,\ 01,\ 11,\ 10.$$
这正好是全部四种 2-bit 模式，而其规范整数就是
$$0011_2=3,$$
与 checkpoint \(S(2)=3\) 完全一致。
程序检查两个样例：
$$S(2)=3,\qquad S(3)=52.$$
这可以同时验证图建模和数值转换是否正确。
当 \(n=3\) 时，solver 找到的两个规范回路是
$$00010111_2=23,\qquad 00011101_2=29,$$
所以
$$S(3)=23+29=52.$$
程序支持 --n 和 --skip-checkpoints。solve(n) 先计算边数 \(2^n\) 和节点掩码 \(2^{n-1}-1\)。used_edge 记录每条 \(n\)-bit 边是否已经走过。sequence 初始为 \(n\) 个 0，也就是锚定的 \(0^n\) 块。
lambda dfs 会从当前节点尝试两个扩展。如果候选边还没用过，就把它标记、加入最后一位，然后从后缀节点继续搜索。等所有边都使用完且路径回到 0 节点时，位序列被转成整数并加入 total。
检查点只比较 solve(2) 和 solve(3) 与预期值是否一致。
搜索使用回溯枚举 Euler 回路，因此时间复杂度对 \(n\) 是指数级的。这是不可避免的，因为合法二进制环的数量本身也增长很快。
空间复杂度为 \(O(2^n)\)，主要来自边标记数组和当前位序列。递归深度也与回路长度成正比。
Для фиксированного \(n\) нужно найти бинарные циклы, в которых каждый \(n\)-битный блок встречается ровно один раз по окружности. Программа суммирует целые числа, представленные всеми такими циклами в канонической записи.
Вместо прямого перебора битовых строк решение сводит задачу к поиску эйлеровых циклов в графе де Брёйна и перечисляет все подходящие циклы с помощью DFS.
Бинарный круг порядка \(n\) - это циклическая битовая последовательность, у которой циклические блоки длины \(n\) образуют все \(2^n\) возможных шаблонов. Это естественно моделируется графом де Брёйна порядка \(n\).
Размеры графа:
$$|V|=2^{n-1},\qquad |E|=2^n.$$
Каждая вершина - это строка длины \(n-1\), каждое ребро - строка длины \(n\).
Если текущий узел равен \(u\) и мы добавляем бит \(b\in\{0,1\}\), то получаем ребро
$$e=((u\ll 1)\,|\,b)\ \&\ (2^n-1),$$
а следующий узел равен его суффиксу длины \(n-1\):
$$v=e\ \&\ (2^{n-1}-1).$$
DFS буквально идет по этим переходам.
Проход по каждому ребру ровно один раз означает, что каждый \(n\)-битный шаблон встречается ровно один раз. Это и есть требуемое условие.
Обратно, любой корректный бинарный круг задает замкнутый обход графа, потому что соседние окна длины \(n\) перекрываются на \(n-1\) битах. Значит, задача эквивалентна перечислению эйлеровых циклов.
Поскольку цикл можно вращать, одна и та же последовательность появлялась бы много раз. Чтобы убрать эту повторяемость, solver фиксирует начальный блок \(0^n\). В коде это реализовано как заранее использованное ребро 0 и старт DFS из узла 0.
Рекурсия хранит три вещи:
1. массив использованных рёбер,
2. текущий узел,
3. текущую битовую последовательность.
На каждом шаге пробуются биты 0 и 1. Если соответствующее ребро свободно, оно помечается, бит добавляется, и поиск продолжается от суффиксного узла. При возврате выбор откатывается.
Инвариант прост: использованные рёбра - это ровно рёбра, уже пройденные частичным путём, а текущий узел - суффикс последнего ребра.
Если использованы все \(2^n\) рёбра и путь возвращается в узел 0, найден эйлеров цикл. Если хотя бы одно ребро ещё свободно, путь неполон.
Поскольку DFS в каждой точке пробует все неиспользованные выходы, каждый эйлеров цикл, закреплённый за \(0^n\), перечисляется ровно один раз.
Битовая последовательность хранится в sequence. После нахождения полного цикла первые \(2^n\) бит интерпретируются как двоичное число:
$$X=\sum_{i=0}^{2^n-1} b_i\,2^{2^n-1-i}.$$
Это значение добавляется к сумме.
Небольшой полностью разобранный пример - случай \(n=2\). Единственный закреплённый цикл даёт битовый префикс
$$0011,$$
чьи циклические окна равны
$$00,\ 01,\ 11,\ 10.$$
Это ровно все четыре 2-битных шаблона, а канонический целочисленный представитель равен
$$0011_2=3,$$
что точно совпадает с checkpoint'ом \(S(2)=3\).
Программа проверяет:
$$S(2)=3,\qquad S(3)=52.$$
Так проверяются и граф, и преобразование в число.
Для \(n=3\) solver находит два канонических цикла
$$00010111_2=23,\qquad 00011101_2=29,$$
следовательно
$$S(3)=23+29=52.$$
Программа поддерживает параметры --n и --skip-checkpoints. solve(n) сначала вычисляет число рёбер \(2^n\) и маску узла \(2^{n-1}-1\). Массив used_edge хранит, какие \(n\)-битные блоки уже использованы. Вектор sequence начинается с \(n\) нулей, то есть с анкерованного блока \(0^n\).
Lambda dfs пробует два продолжения из текущего узла. Если кандидатное ребро ещё не использовано, оно помечается, его последний бит добавляется, и поиск продолжается от суффиксного узла. Когда все рёбра использованы и путь возвращается к 0, последовательность превращается в целое число и добавляется к total.
Проверки сравнивают solve(2) и solve(3) с ожидаемыми значениями.
Поиск перечисляет эйлеровы циклы методом backtracking, поэтому время экспоненциально по \(n\). Это неизбежно, потому что число допустимых бинарных кругов тоже растёт очень быстро.
Память составляет \(O(2^n)\), в основном за счёт массива отметок рёбер и текущей битовой последовательности. Глубина рекурсии пропорциональна длине цикла.
لـ \(n\) ثابت، نبحث عن دورات ثنائية يظهر فيها كل نمط بطول \(n\) بت مرة واحدة فقط على نحو دائري. ثم نجمع الأعداد الصحيحة الثنائية التي تمثلها جميع هذه الدورات في التمثيل الكانوني الذي يعتمده الحل.
لا يتعامل البرنامج مع سلاسل البتات بشكل مباشر؛ بل يحول المسألة إلى عدّ دورات Euler في رسم De Bruijn ثم يعدد كل دورة صحيحة ببحث عمقي رجوعي.
الدورة الثنائية من الرتبة \(n\) هي سلسلة بتات دائرية، تكون فيها المقاطع الدائرية بطول \(n\) هي بالضبط كل الأنماط الممكنة وعددها \(2^n\). هذا يُنمذج طبيعيًا برسم De Bruijn من الرتبة \(n\).
أبعاد الرسم هي:
$$|V|=2^{n-1},\qquad |E|=2^n.$$
كل عقدة تمثل سلسلة بطول \(n-1\) بت، وكل حافة تمثل سلسلة بطول \(n\) بت.
إذا كانت العقدة الحالية \(u\) وأضفنا البت \(b\in\{0,1\}\)، فإن الحافة الناتجة هي
$$e=((u\ll 1)\,|\,b)\ \&\ (2^n-1),$$
والعقدة التالية هي لاحقتها بطول \(n-1\):
$$v=e\ \&\ (2^{n-1}-1).$$
الـ DFS يتبع هذه القاعدة حرفيًا.
المرور على كل حافة مرة واحدة فقط يعني أن كل نمط بطول \(n\) يظهر مرة واحدة فقط. وهذه هي بالضبط شروط المسألة.
وعكس ذلك صحيح أيضًا: أي دورة صالحة تعطي مسارًا مغلقًا في الرسم، لأن النوافذ المتتالية بطول \(n\) تتداخل في \(n-1\) بت. لذا فالمطلوب هو تعداد دورات Euler.
بما أن الدورة قابلة للدوران، فالنمط نفسه سيظهر بعدة إزاحات. لإزالة هذا التكرار يثبت الحل البداية عند \(0^n\). وفي الكود يتم ذلك عبر تعليم الحافة 0 كأنها مستخدمة مسبقًا والبدء من العقدة 0.
يحتفظ البحث الرجوعي بثلاثة أشياء:
1. مصفوفة منطقية للحواف المستخدمة،
2. العقدة الحالية،
3. تسلسل البتات الجاري بناؤه.
في كل خطوة تُجرَّب القيمتان 0 و1. إذا كانت الحافة المقابلة غير مستخدمة، تُعلَّم، ويُضاف آخر بت، ثم يستمر البحث من عقدة اللاحقة. وعند الرجوع تُلغى هذه الاختيارات.
الثابت (invariant) بسيط: الحواف المستخدمة هي نفسها الحواف التي مر بها المسار الجزئي، والعقدة الحالية هي لاحقة آخر حافة.
إذا استُخدمت جميع الحواف \(2^n\) وعاد المسار إلى العقدة 0، فلدينا دورة Euler كاملة. وإذا بقيت حافة غير مستخدمة فالمسار غير مكتمل.
وبما أن الـ DFS يجرّب جميع الخروجيات غير المستخدمة في كل حالة، فإن كل دورة Euler مثبتة عند \(0^n\) تُولَّد مرة واحدة فقط.
يُخزن تسلسل البتات في sequence. وبعد العثور على دورة كاملة، تُقرأ أول \(2^n\) بتات كعدد ثنائي:
$$X=\sum_{i=0}^{2^n-1} b_i\,2^{2^n-1-i}.$$
ثم تُضاف هذه القيمة إلى المجموع الكلي.
مثال صغير محلول بالكامل هو الحالة \(n=2\). فالدورة المثبتة الوحيدة تعطي بادئة البتات
$$0011,$$
ونوافذها الدائرية هي
$$00,\ 01,\ 11,\ 10.$$
وهذه بالضبط جميع الأنماط الأربعة ذات الطول 2، والتمثيل الصحيح الكانوني هو
$$0011_2=3,$$
وهذا يطابق تمامًا نقطة التحقق \(S(2)=3\).
يتحقق البرنامج من القيمتين:
$$S(2)=3,\qquad S(3)=52.$$
وهكذا يتم فحص بناء الرسم والتحويل العددي معًا.
ولـ \(n=3\) يجد الحل الدورتين الكانونيتين
$$00010111_2=23,\qquad 00011101_2=29,$$
ومن ثم
$$S(3)=23+29=52.$$
يدعم البرنامج الخيارين --n و--skip-checkpoints. تبدأ الدالة solve(n) بحساب عدد الحواف \(2^n\) وقناع العقد \(2^{n-1}-1\). المصفوفة used_edge تسجل أي مقاطع \(n\)-بت استُخدمت بالفعل. أما sequence فتبدأ بـ \(n\) أصفار، أي الكتلة المثبتة \(0^n\).
تجرب الدالة المجهولة dfs الامتدادين الممكنين من العقدة الحالية. إذا كانت الحافة المرشحة غير مستخدمة، تُعلَّم، ويُضاف آخر بت منها، ثم يستمر البحث من عقدة اللاحقة. وعندما تُستخدم كل الحواف ويعود المسار إلى 0، يتحول التسلسل إلى عدد صحيح ويضاف إلى total.
التحقق فقط يقارن solve(2) وsolve(3) بالقيم المتوقعة.
البحث يعدّد دورات Euler بالبحث الرجوعي، لذا فالزمن أُسّي بالنسبة إلى \(n\). وهذا لا يمكن تجنبه لأن عدد الدورات الثنائية الصحيحة نفسه ينمو بسرعة كبيرة.
الذاكرة من رتبة \(O(2^n)\)، ويسيطر عليها مصفوفة تعليم الحواف وتسلسل البتات الحالي. وعمق الاستدعاء الرجوعي يتناسب مع طول الدورة.