Let \(\tau : \{0,1\}^6 \to \{0,1\}\) be a Boolean truth table on six input bits. The condition in the problem is
$$\tau(a,b,c,d,e,f)\land\tau\bigl(b,c,d,e,f,a\oplus(b\land c)\bigr)=0,$$
for every 6-bit state \((a,b,c,d,e,f)\). In other words, if we define the state transition
$$T(a,b,c,d,e,f)=\bigl(b,c,d,e,f,a\oplus(b\land c)\bigr),$$
then no state and its successor under \(T\) are both allowed to receive the value 1. The task is to count how many truth tables satisfy this global constraint.
The key point is that the transition graph on the 64 states is not an arbitrary functional graph. It is actually a permutation, so the whole graph splits into disjoint directed cycles. Once those cycle lengths are known, the Boolean counting problem becomes a product of independent cycle counts.
The entire solution is driven by the structure of the six-bit transition. The implementations do not search over truth tables at all; they first decompose the 64 states into cycles, then count admissible 0/1 labelings on each cycle.
Write the output of \(T\) as \((u,v,w,p,q,r)\). By definition,
$$u=b,\quad v=c,\quad w=d,\quad p=e,\quad q=f,\quad r=a\oplus(b\land c).$$
These equations can be inverted immediately:
$$a=r\oplus(u\land v),\qquad (b,c,d,e,f)=(u,v,w,p,q).$$
So every output state has exactly one predecessor. Therefore \(T\) is a bijection on the 64 states, and every connected component of the directed graph is a pure cycle. There are no trees feeding into a cycle, so a cycle decomposition really is the whole story.
Consider one cycle of length \(L\):
$$s_0\to s_1\to \cdots \to s_{L-1}\to s_0.$$
If we set
$$x_i=\tau(s_i)\in\{0,1\},$$
then the constraint says
$$x_i x_{i+1}=0\qquad\text{for all }i\pmod L.$$
So on that cycle we must count binary circular strings with no adjacent 1s. This is the same as counting independent sets of a cycle graph with \(L\) vertices.
Different cycles share no states, so their labelings are independent. If a cycle of length \(L\) contributes \(C_L\) admissible labelings, and the permutation decomposition has cycle lengths \(L_1,L_2,\dots,L_k\), then the total number of valid truth tables is simply
$$\prod_{j=1}^k C_{L_j}.$$
First count binary strings on a path. Let \(P_n\) be the number of length-\(n\) binary strings with no adjacent 1s. A standard last-position split gives
$$P_n=P_{n-1}+P_{n-2},\qquad P_0=1,\quad P_1=2.$$
Hence
$$P_n=F_{n+2},$$
where \(F_0=0\), \(F_1=1\), and \(F_{m+2}=F_{m+1}+F_m\).
Now return to a cycle of length \(L\ge 2\). Split into two cases according to the first position.
If \(x_0=0\), then the remaining \(L-1\) positions form an unrestricted path, contributing \(P_{L-1}\) possibilities.
If \(x_0=1\), then both neighbors \(x_1\) and \(x_{L-1}\) must be 0, leaving a path of length \(L-3\), which contributes \(P_{L-3}\) possibilities.
Therefore
$$C_L=P_{L-1}+P_{L-3}=F_{L+1}+F_{L-1}.$$
The length-1 case also fits this formula: a 1-cycle forces its only state to be 0, so \(C_1=1=F_0+F_2\).
One of the actual cycles generated by \(T\) is
$$000001\to 000010\to 000100\to 001000\to 010000\to 100000\to 000001,$$
so this is a cycle of length 6. The number of admissible truth-table values on these six states is
$$C_6=P_5+P_3=F_7+F_5=13+5=18.$$
You can read this directly from the split above: either the first state gets value 0 and the other five positions behave like a path, or the first state gets value 1 and its two neighbors are forced to 0, leaving only three free positions in the middle.
Running through all 64 states yields the cycle lengths
$$1,\ 2,\ 3,\ 6,\ 6,\ 46.$$
So the full count is
$$C_1\,C_2\,C_3\,C_6^2\,C_{46}.$$
Using \(C_L=F_{L-1}+F_{L+1}\), this becomes
$$1\cdot 3\cdot 4\cdot 18^2\cdot \bigl(F_{45}+F_{47}\bigr).$$
Since \(F_{45}=1134903170\) and \(F_{47}=2971215073\), the final count is
$$15\,964\,587\,728\,784.$$
The C++, Python, and Java implementations encode each 6-bit state as an integer from 0 to 63. For each state they compute the successor by shifting the low five bits left and appending the feedback bit \(a\oplus(b\land c)\). A visited array ensures that every state is processed exactly once.
Because the transition is bijective, starting from any unvisited state and repeatedly applying the transition eventually returns to the starting cycle without encountering a tail. The implementation counts how many states appear before the repetition and records that as one cycle length.
For each recorded length \(L\), the implementation builds Fibonacci values up to \(F_{L+1}\) and evaluates \(F_{L-1}+F_{L+1}\). Those factors are then multiplied together in a 64-bit integer accumulator.
All three language versions follow the same mathematical plan: decompose the permutation on the 64 states, turn each cycle into an independent no-adjacent-1 counting problem, and multiply the resulting factors.
The cycle decomposition visits each of the 64 states once, so that phase costs \(O(64)\) time and \(O(64)\) memory. The Fibonacci preparation for a cycle of length \(L\) costs \(O(L)\), and the total of all cycle lengths is also 64.
Therefore the overall complexity is \(O(64)\) time and \(O(64)\) space, which is constant for this fixed problem size. Numerically, the largest cycle has length 46, so even the Fibonacci step is tiny.
Gesucht ist die Anzahl aller Booleschen Wahrheitstabellen \(\tau : \{0,1\}^6 \to \{0,1\}\), die für jeden 6-Bit-Zustand \((a,b,c,d,e,f)\) die Bedingung
$$\tau(a,b,c,d,e,f)\land\tau\bigl(b,c,d,e,f,a\oplus(b\land c)\bigr)=0$$
erfüllen. Definiert man die Übergangsfunktion
$$T(a,b,c,d,e,f)=\bigl(b,c,d,e,f,a\oplus(b\land c)\bigr),$$
dann dürfen also ein Zustand und sein Nachfolger unter \(T\) niemals gleichzeitig den Wert 1 tragen. Die Aufgabe besteht darin, alle zulässigen Belegungen der 64 Zustände zu zählen.
Der entscheidende strukturelle Punkt ist: Der Zustandsgraph ist kein allgemeiner gerichteter Graph mit Verzweigungen, sondern eine Permutation auf 64 Elementen. Deshalb zerfällt er vollständig in disjunkte Zyklen, und die Gesamtzahl ergibt sich als Produkt von Zykelbeiträgen.
Die Implementierungen durchsuchen den Raum der Wahrheitstabellen nicht direkt. Stattdessen bestimmen sie zuerst die Zykluszerlegung der 64 Zustände und zählen dann für jeden Zyklus separat die zulässigen 0/1-Markierungen.
Schreibe den Ausgabestatus von \(T\) als \((u,v,w,p,q,r)\). Dann gilt per Definition
$$u=b,\quad v=c,\quad w=d,\quad p=e,\quad q=f,\quad r=a\oplus(b\land c).$$
Daraus lässt sich der Vorgänger eindeutig zurückgewinnen:
$$a=r\oplus(u\land v),\qquad (b,c,d,e,f)=(u,v,w,p,q).$$
Also besitzt jeder Zustand genau einen Vorgänger und genau einen Nachfolger. Die Abbildung \(T\) ist damit bijektiv, und jede Zusammenhangskomponente ist bereits ein reiner gerichteter Zyklus. Es gibt keine Vorläuferbäume, die erst in einen Zyklus hineinlaufen.
Betrachte einen Zyklus der Länge \(L\):
$$s_0\to s_1\to \cdots \to s_{L-1}\to s_0.$$
Setzt man
$$x_i=\tau(s_i)\in\{0,1\},$$
so wird die Problembedingung zu
$$x_i x_{i+1}=0\qquad\text{für alle }i\pmod L.$$
Wir müssen auf dem Zyklus also binäre Ringfolgen ohne benachbarte Einsen zählen. Graphentheoretisch ist das genau die Anzahl der unabhängigen Mengen in einem Zyklusgraphen mit \(L\) Knoten.
Verschiedene Zyklen teilen keine Zustände und können deshalb unabhängig voneinander beschriftet werden. Wenn ein Zyklus der Länge \(L\) genau \(C_L\) zulässige Belegungen hat und die Permutation aus Zykluslängen \(L_1,\dots,L_k\) besteht, dann ist die Gesamtzahl
$$\prod_{j=1}^k C_{L_j}.$$
Zunächst betrachten wir Wege statt Zyklen. Sei \(P_n\) die Anzahl der binären Folgen der Länge \(n\) ohne benachbarte Einsen. Eine Fallunterscheidung nach dem letzten Zeichen liefert
$$P_n=P_{n-1}+P_{n-2},\qquad P_0=1,\quad P_1=2.$$
Daher gilt
$$P_n=F_{n+2},$$
wobei \(F_0=0\), \(F_1=1\) und \(F_{m+2}=F_{m+1}+F_m\) die Fibonacci-Zahlen sind.
Nun zum Zyklus der Länge \(L\ge 2\). Falls \(x_0=0\), bleiben \(L-1\) freie Positionen auf einem Weg, also \(P_{L-1}\) Möglichkeiten. Falls \(x_0=1\), dann müssen \(x_1\) und \(x_{L-1}\) beide 0 sein; übrig bleibt ein Weg der Länge \(L-3\), also \(P_{L-3}\) Möglichkeiten.
Somit
$$C_L=P_{L-1}+P_{L-3}=F_{L+1}+F_{L-1}.$$
Auch der Fall \(L=1\) passt: Ein 1-Zyklus darf nur mit 0 markiert werden, also \(C_1=1=F_0+F_2\).
Eine der tatsächlich auftretenden Bahnen ist
$$000001\to 000010\to 000100\to 001000\to 010000\to 100000\to 000001.$$
Das ist also ein Zyklus der Länge 6. Seine Zahl zulässiger Belegungen ist
$$C_6=P_5+P_3=F_7+F_5=13+5=18.$$
Diese 18 entstehen genau aus der obigen Fallunterscheidung: Entweder die erste Position erhält 0 und die restlichen fünf Stellen bilden einen Weg, oder die erste Position erhält 1, wodurch beide Nachbarn zu 0 gezwungen werden und nur noch drei freie Stellen in der Mitte übrig bleiben.
Für die 64 Zustände ergeben sich exakt die Zykluslängen
$$1,\ 2,\ 3,\ 6,\ 6,\ 46.$$
Daraus folgt für die Gesamtzahl zulässiger Wahrheitstabellen
$$C_1\,C_2\,C_3\,C_6^2\,C_{46}.$$
Mit \(C_L=F_{L-1}+F_{L+1}\) wird das zu
$$1\cdot 3\cdot 4\cdot 18^2\cdot \bigl(F_{45}+F_{47}\bigr).$$
Weil \(F_{45}=1134903170\) und \(F_{47}=2971215073\) gilt, erhält man schließlich
$$15\,964\,587\,728\,784.$$
Die C++-, Python- und Java-Implementierungen codieren jeden 6-Bit-Zustand als Zahl zwischen 0 und 63. Der Nachfolger wird berechnet, indem die unteren fünf Bits nach links geschoben und rechts das Rückkopplungsbit \(a\oplus(b\land c)\) angehängt wird. Ein Besuchsarray stellt sicher, dass jeder Zustand genau einmal verarbeitet wird.
Da der Übergang bijektiv ist, führt das wiederholte Anwenden des Nachfolgers von jedem noch unbesuchten Startzustand direkt durch genau einen Zyklus. Die Anzahl der dabei gesehenen Zustände ist die gesuchte Zykluslänge.
Für jede gefundene Länge \(L\) berechnet die Implementierung Fibonacci-Werte bis \(F_{L+1}\) und setzt dann \(F_{L-1}+F_{L+1}\) ein. Alle diese Faktoren werden in einem 64-Bit-Akkumulator multipliziert.
In allen drei Sprachen ist die mathematische Idee identisch: erst die Permutation auf den 64 Zuständen in Zyklen zerlegen, dann jeden Zyklus als unabhängiges „keine benachbarten Einsen“-Problem zählen und schließlich alle Faktoren multiplizieren.
Die Zykluszerlegung besucht jeden der 64 Zustände genau einmal. Das kostet \(O(64)\) Zeit und \(O(64)\) Speicher. Die Fibonacci-Berechnung für einen Zyklus der Länge \(L\) kostet \(O(L)\), und die Summe aller Zykluslängen ist ebenfalls 64.
Damit liegt die Gesamtkosten bei \(O(64)\) Zeit und \(O(64)\) Speicher, also effektiv bei konstantem Aufwand für diese feste Problemgröße. Die längste Bahn hat nur Länge 46, daher ist auch der Zahlenteil sehr klein.
\(\tau : \{0,1\}^6 \to \{0,1\}\) biçiminde, altı bitlik girdilere değer veren bir doğruluk tablosu düşünelim. Sorudaki koşul, her \((a,b,c,d,e,f)\) durumu için
$$\tau(a,b,c,d,e,f)\land\tau\bigl(b,c,d,e,f,a\oplus(b\land c)\bigr)=0$$
olmasını ister. Yani
$$T(a,b,c,d,e,f)=\bigl(b,c,d,e,f,a\oplus(b\land c)\bigr)$$
geçişini tanımlarsak, bir durum ile onun \(T\) altındaki ardılı aynı anda 1 olamaz. Amaç, bu şartı sağlayan bütün doğruluk tablolarının sayısını bulmaktır.
Buradaki belirleyici gözlem şudur: 64 durum üzerindeki geçiş grafiği genel bir fonksiyonel grafik değildir; aslında bir permütasyondur. Bu yüzden tüm yapı ayrık döngülere parçalanır ve toplam sayım, her döngü için bulunan sayının çarpımı olur.
Çözüm, doğruluk tablolarını doğrudan denemek yerine önce altı bitlik geçişin gerçek yapısını çözüyor. Kodların yaptığı şey, 64 durumu döngülere ayırmak ve sonra her döngü üzerindeki geçerli 0/1 atamalarını ayrı ayrı saymaktır.
\(T\)'nin çıktısını \((u,v,w,p,q,r)\) diye yazalım. Tanım gereği
$$u=b,\quad v=c,\quad w=d,\quad p=e,\quad q=f,\quad r=a\oplus(b\land c).$$
Buradan önceki durum tekil olarak geri kazanılır:
$$a=r\oplus(u\land v),\qquad (b,c,d,e,f)=(u,v,w,p,q).$$
Demek ki her çıkışın tam bir öncülü vardır. Başka bir deyişle \(T\), 64 durum üzerinde bijektiftir. Sonuç olarak her bağlantılı bileşen saf bir yönlü döngüdür; döngülere ağaç gibi kuyruklar bağlanmaz.
Uzunluğu \(L\) olan bir döngü düşünelim:
$$s_0\to s_1\to \cdots \to s_{L-1}\to s_0.$$
Bu döngüde
$$x_i=\tau(s_i)\in\{0,1\}$$
olursa, problem koşulu
$$x_i x_{i+1}=0\qquad\text{(indisler }L\text{ modunda)}$$
şekline iner. Yani döngü üzerindeki ikili dizide komşu iki 1 yan yana gelemez. Bu, tam olarak uzunluğu \(L\) olan çevrim grafındaki bağımsız küme sayımıdır.
Farklı döngüler birbirinden tamamen bağımsızdır; bir döngüde hangi durumlara 1 verdiğimiz, başka bir döngüyü etkilemez. Dolayısıyla döngü uzunlukları \(L_1,\dots,L_k\) ise toplam cevap
$$\prod_{j=1}^k C_{L_j}$$
olur; burada \(C_L\), uzunluğu \(L\) olan tek bir döngüdeki geçerli etiketleme sayısıdır.
Önce bir yol üzerinde sayım yapalım. \(P_n\), uzunluğu \(n\) olan ve bitişik iki 1 içermeyen ikili dizilerin sayısı olsun. Son bitten yapılan standart ayrım
$$P_n=P_{n-1}+P_{n-2},\qquad P_0=1,\quad P_1=2$$
reküransını verir. Buradan
$$P_n=F_{n+2}$$
elde edilir; burada \(F_0=0\), \(F_1=1\) ve \(F_{m+2}=F_{m+1}+F_m\) klasik Fibonacci tanımıdır.
Şimdi uzunluğu \(L\ge 2\) olan bir döngüye dönelim. İlk konum için iki olasılık vardır.
Eğer \(x_0=0\) ise kalan \(L-1\) konum doğrusal bir yol gibi davranır; katkı \(P_{L-1}\) olur.
Eğer \(x_0=1\) ise iki komşusu olan \(x_1\) ve \(x_{L-1}\) zorunlu olarak 0 olmalıdır; geriye uzunluğu \(L-3\) olan bir yol kalır ve katkı \(P_{L-3}\) olur.
Bu nedenle
$$C_L=P_{L-1}+P_{L-3}=F_{L+1}+F_{L-1}.$$
\(L=1\) durumu da bu formülle uyumludur: tek düğümlü döngüde o düğüm 1 olamaz, dolayısıyla \(C_1=1=F_0+F_2\).
Gerçekten ortaya çıkan döngülerden biri şudur:
$$000001\to 000010\to 000100\to 001000\to 010000\to 100000\to 000001.$$
Bu yüzden burada \(L=6\). Geçerli etiketleme sayısı
$$C_6=P_5+P_3=F_7+F_5=13+5=18$$
olur. Yani bu altı durum üzerinde \(\tau\)'ya verilebilecek 18 farklı geçerli 0/1 düzeni vardır. Bu sayı, ilk duruma 0 verme ve 1 verme durumlarını ayırınca doğrudan çıkar.
64 durum tarandığında döngü uzunlukları tam olarak
$$1,\ 2,\ 3,\ 6,\ 6,\ 46$$
olarak bulunur. O halde toplam geçerli tablo sayısı
$$C_1\,C_2\,C_3\,C_6^2\,C_{46}$$
şeklindedir. \(C_L=F_{L-1}+F_{L+1}\) formülünü koyarsak
$$1\cdot 3\cdot 4\cdot 18^2\cdot \bigl(F_{45}+F_{47}\bigr)$$
elde edilir. \(F_{45}=1134903170\) ve \(F_{47}=2971215073\) olduğundan son değer
$$15\,964\,587\,728\,784$$
çıkar.
C++, Python ve Java uygulamaları her 6-bit durumu 0 ile 63 arasında bir tam sayı olarak temsil eder. Bir sonraki durum, alt beş biti sola kaydırıp sona \(a\oplus(b\land c)\) geri besleme bitini ekleyerek hesaplanır. Ziyaret dizisi sayesinde her durum yalnızca bir kez işlenir.
Geçiş bijektif olduğu için, herhangi bir ziyaret edilmemiş durumdan başlayıp ardılları izlemek doğrudan tek bir döngüyü dolaşır. Tekrar görülene kadar geçen adım sayısı, o döngünün uzunluğudur.
Bulunan her \(L\) için uygulama \(F_{L+1}\)'e kadar Fibonacci sayılarını üretir ve \(F_{L-1}+F_{L+1}\) değerini hesaplar. Sonra tüm bu çarpanlar 64 bitlik bir tamsayıda çarpılır.
Üç dildeki uygulamaların yaptığı matematik aynıdır: önce durum permütasyonunu ayrıştırmak, sonra her döngü için “komşu 1 yok” sayımını yapmak, en sonda da tüm katkıları çarpmak.
Döngü ayrıştırması 64 durumun her birini tam bir kez ziyaret eder; bu aşama \(O(64)\) zaman ve \(O(64)\) bellek kullanır. Uzunluğu \(L\) olan bir döngü için Fibonacci hazırlığı \(O(L)\) sürer ve bütün döngü uzunluklarının toplamı yine 64'tür.
Dolayısıyla toplam maliyet \(O(64)\) zaman ve \(O(64)\) bellek, yani bu sabit problem boyutu için pratikte \(O(1)\)'dir. En büyük döngü uzunluğu 46 olduğu için yardımcı aritmetik de çok küçüktür.
Sea \(\tau : \{0,1\}^6 \to \{0,1\}\) una tabla de verdad booleana sobre seis bits. La restricción del problema exige que, para todo estado \((a,b,c,d,e,f)\), se cumpla
$$\tau(a,b,c,d,e,f)\land\tau\bigl(b,c,d,e,f,a\oplus(b\land c)\bigr)=0.$$
Si definimos la transición
$$T(a,b,c,d,e,f)=\bigl(b,c,d,e,f,a\oplus(b\land c)\bigr),$$
eso significa que un estado y su sucesor bajo \(T\) nunca pueden recibir simultáneamente el valor 1. Hay que contar cuántas tablas de verdad cumplen esta condición para los 64 estados posibles.
La observación decisiva es que el grafo de estados no es un grafo funcional arbitrario: \(T\) es en realidad una permutación de los 64 estados. Por eso toda la estructura se descompone en ciclos disjuntos, y el conteo total se convierte en un producto de conteos por ciclo.
Las implementaciones no intentan explorar las \(2^{64}\) tablas posibles. Primero analizan la permutación inducida por la transición de seis bits y luego cuentan, ciclo por ciclo, cuántas asignaciones binarias respetan la prohibición de tener dos 1 consecutivos en la órbita.
Escribamos la salida de \(T\) como \((u,v,w,p,q,r)\). Entonces
$$u=b,\quad v=c,\quad w=d,\quad p=e,\quad q=f,\quad r=a\oplus(b\land c).$$
Estas ecuaciones se invierten de manera directa:
$$a=r\oplus(u\land v),\qquad (b,c,d,e,f)=(u,v,w,p,q).$$
Así, cada estado de salida tiene un único predecesor. La aplicación \(T\) es biyectiva sobre los 64 estados, de modo que cada componente conexa del grafo dirigido es un ciclo puro. No aparecen ramas ni colas que desemboquen en un ciclo.
Consideremos un ciclo de longitud \(L\):
$$s_0\to s_1\to \cdots \to s_{L-1}\to s_0.$$
Si definimos
$$x_i=\tau(s_i)\in\{0,1\},$$
la condición del problema se traduce en
$$x_i x_{i+1}=0\qquad\text{para todo }i\pmod L.$$
Por tanto, en cada ciclo debemos contar cadenas binarias circulares sin unos adyacentes. En lenguaje de teoría de grafos, eso es contar conjuntos independientes en un ciclo de \(L\) vértices.
Como los ciclos son disjuntos, sus elecciones son independientes entre sí. Si un ciclo de longitud \(L\) aporta \(C_L\) configuraciones válidas, y la descomposición total tiene longitudes \(L_1,\dots,L_k\), entonces el número buscado es
$$\prod_{j=1}^k C_{L_j}.$$
Primero resolvemos el problema análogo en un camino. Sea \(P_n\) el número de cadenas binarias de longitud \(n\) sin unos consecutivos. Separando según el último bit se obtiene
$$P_n=P_{n-1}+P_{n-2},\qquad P_0=1,\quad P_1=2.$$
De aquí se deduce
$$P_n=F_{n+2},$$
donde \(F_0=0\), \(F_1=1\) y \(F_{m+2}=F_{m+1}+F_m\) son los números de Fibonacci.
Ahora volvamos a un ciclo de longitud \(L\ge 2\). Hay dos casos naturales.
Si \(x_0=0\), las otras \(L-1\) posiciones se comportan como un camino libre, así que aportan \(P_{L-1}\) configuraciones.
Si \(x_0=1\), entonces los dos vecinos \(x_1\) y \(x_{L-1}\) quedan forzados a 0. Solo queda un camino interno de longitud \(L-3\), con \(P_{L-3}\) posibilidades.
Por lo tanto,
$$C_L=P_{L-1}+P_{L-3}=F_{L+1}+F_{L-1}.$$
El caso \(L=1\) también encaja: un 1-ciclo no puede etiquetarse con 1, de modo que \(C_1=1=F_0+F_2\).
Uno de los ciclos reales de la permutación es
$$000001\to 000010\to 000100\to 001000\to 010000\to 100000\to 000001.$$
Su longitud es 6, así que el número de etiquetados válidos sobre esos seis estados es
$$C_6=P_5+P_3=F_7+F_5=13+5=18.$$
Ese 18 sale exactamente de la partición anterior: o bien el primer estado recibe 0 y quedan cinco posiciones lineales, o bien recibe 1, con lo que sus dos vecinos quedan fijados en 0 y solo restan tres posiciones libres.
Al recorrer los 64 estados aparecen exactamente las longitudes
$$1,\ 2,\ 3,\ 6,\ 6,\ 46.$$
Así, el número total de tablas válidas es
$$C_1\,C_2\,C_3\,C_6^2\,C_{46}.$$
Sustituyendo \(C_L=F_{L-1}+F_{L+1}\), obtenemos
$$1\cdot 3\cdot 4\cdot 18^2\cdot \bigl(F_{45}+F_{47}\bigr).$$
Como \(F_{45}=1134903170\) y \(F_{47}=2971215073\), el total final es
$$15\,964\,587\,728\,784.$$
Las implementaciones en C++, Python y Java codifican cada estado de 6 bits como un entero entre 0 y 63. El sucesor se obtiene desplazando a la izquierda los cinco bits inferiores y añadiendo al final el bit de realimentación \(a\oplus(b\land c)\). Un arreglo de visitados garantiza que cada estado se procese una sola vez.
Como la transición es biyectiva, empezar en cualquier estado no visitado y seguir sucesores recorre directamente un único ciclo. El número de pasos hasta volver a un estado ya visto es precisamente la longitud de ese ciclo.
Para cada longitud \(L\), la implementación genera Fibonacci hasta \(F_{L+1}\) y evalúa \(F_{L-1}+F_{L+1}\). Después multiplica todos esos factores en un acumulador de 64 bits.
Las tres versiones siguen la misma idea matemática: descomponer la permutación de los 64 estados, convertir cada ciclo en un conteo independiente de cadenas circulares sin unos adyacentes y multiplicar todas las contribuciones.
La descomposición en ciclos visita cada uno de los 64 estados una sola vez, así que cuesta \(O(64)\) tiempo y \(O(64)\) memoria. El cálculo de Fibonacci para un ciclo de longitud \(L\) cuesta \(O(L)\), y la suma de todas las longitudes también es 64.
En consecuencia, el algoritmo completo usa \(O(64)\) tiempo y \(O(64)\) espacio, es decir, costo constante para este tamaño fijo del problema. El ciclo más largo tiene longitud 46, por lo que la parte numérica también es muy pequeña.
设 \(\tau : \{0,1\}^6 \to \{0,1\}\) 是定义在六位二进制状态上的布尔真值表。题目的约束是：对每个状态 \((a,b,c,d,e,f)\)，都必须满足
$$\tau(a,b,c,d,e,f)\land\tau\bigl(b,c,d,e,f,a\oplus(b\land c)\bigr)=0.$$
如果把状态转移写成
$$T(a,b,c,d,e,f)=\bigl(b,c,d,e,f,a\oplus(b\land c)\bigr),$$
那么这句话的含义就是：任意状态与它在 \(T\) 下的后继状态，不能同时被 \(\tau\) 标记为 1。我们要计算的是，64 个六位状态上的所有真值表中，有多少个满足这个全局限制。
关键观察是，这个 64 状态系统并不是一个带分叉的普通函数图，而是一个置换。也就是说，每个状态既有唯一后继，也有唯一前驱，因此整个图会完全分解成若干互不相交的有向环。只要知道这些环的长度，原问题就会变成若干独立环上的组合计数，再把结果相乘即可。
实现并不会去枚举 \(2^{64}\) 张可能的真值表，而是先分析六位状态转移的结构，然后在每个环上单独计算合法的 0/1 赋值数量。真正的数学核心只有两步：先把状态空间分解成环，再求一个长度为 \(L\) 的环上有多少种“相邻位置不能同时为 1”的标记方式。
把 \(T\) 的输出写成 \((u,v,w,p,q,r)\)。根据定义有
$$u=b,\quad v=c,\quad w=d,\quad p=e,\quad q=f,\quad r=a\oplus(b\land c).$$
由此可以唯一地反推出输入：
$$a=r\oplus(u\land v),\qquad (b,c,d,e,f)=(u,v,w,p,q).$$
因此每个输出状态都只有一个前驱，\(T\) 在 64 个状态上是双射。结论非常重要：状态图中不会出现“树状分支汇入一个环”的情况，每个连通部分本身就是一个纯粹的有向环。
设某个环的长度为 \(L\)，写成
$$s_0\to s_1\to \cdots \to s_{L-1}\to s_0.$$
在这个环上定义
$$x_i=\tau(s_i)\in\{0,1\}.$$
那么题目条件就变成
$$x_i x_{i+1}=0\qquad\text{对所有 }i\pmod L.$$
也就是说，在同一个环上，相邻两个位置不能同时取 1。于是问题等价于：长度为 \(L\) 的二进制环形串中，不含相邻两个 1 的方案数是多少？从图论角度看，这正是 \(L\) 个顶点的环图上的独立集个数。
不同的环之间没有共享状态，所以每个环上的选择完全独立。若一个长度为 \(L\) 的环贡献 \(C_L\) 种合法赋值，而整个置换分解得到的环长为 \(L_1,L_2,\dots,L_k\)，那么总答案就是
$$\prod_{j=1}^k C_{L_j}.$$
先处理线性链而不是环。设 \(P_n\) 表示长度为 \(n\) 的二进制串中，不含相邻两个 1 的方案数。按最后一位分类可得递推
$$P_n=P_{n-1}+P_{n-2},\qquad P_0=1,\quad P_1=2.$$
因此
$$P_n=F_{n+2},$$
这里 \(F_0=0\)、\(F_1=1\)，并满足 \(F_{m+2}=F_{m+1}+F_m\)。
现在回到一个长度 \(L\ge 2\) 的环。对第一个位置分情况：
如果 \(x_0=0\)，其余 \(L-1\) 个位置形成一条普通的链，因此有 \(P_{L-1}\) 种可能。
如果 \(x_0=1\)，那么它的两个相邻位置 \(x_1\) 和 \(x_{L-1}\) 都被迫为 0，中间只剩下一段长度为 \(L-3\) 的链，所以有 \(P_{L-3}\) 种可能。
于是得到
$$C_L=P_{L-1}+P_{L-3}=F_{L+1}+F_{L-1}.$$
长度为 1 的特殊情况也与公式一致：1-环上的那个状态不能取 1，所以 \(C_1=1=F_0+F_2\)。
实际分解中有一个环是
$$000001\to 000010\to 000100\to 001000\to 010000\to 100000\to 000001.$$
这个环的长度是 6，因此合法赋值数为
$$C_6=P_5+P_3=F_7+F_5=13+5=18.$$
这个例子很能说明公式的来源。如果把第一个状态标成 0，剩下 5 个位置就是线性链；如果把第一个状态标成 1，它的左右两个邻点都必须是 0，只剩下中间 3 个位置可以自由安排。两部分相加正好得到 18。
把 64 个状态全部跑一遍以后，得到的环长恰好是
$$1,\ 2,\ 3,\ 6,\ 6,\ 46.$$
因此总方案数为
$$C_1\,C_2\,C_3\,C_6^2\,C_{46}.$$
再代入 \(C_L=F_{L-1}+F_{L+1}\)，就得到
$$1\cdot 3\cdot 4\cdot 18^2\cdot \bigl(F_{45}+F_{47}\bigr).$$
由于 \(F_{45}=1134903170\)，\(F_{47}=2971215073\)，最终答案是
$$15\,964\,587\,728\,784.$$
C++、Python 和 Java 实现都把每个六位状态编码成 0 到 63 之间的整数。后继状态通过两步得到：先把低五位左移一位，再把反馈位 \(a\oplus(b\land c)\) 填到最低位。随后用一个访问标记数组保证每个状态只会被处理一次。
由于这个转移本身是双射，从任意一个未访问状态出发反复求后继，只会沿着一个完整的环前进，不会先走过一段尾巴再进入环。直到首次重复前经历的状态数，就是该环的长度。
对每一个记录下来的环长 \(L\)，实现都会生成直到 \(F_{L+1}\) 的 Fibonacci 数，然后计算 \(F_{L-1}+F_{L+1}\)。所有环对应的因子最后相乘，得到答案。
三种语言版本在数学上完全一致：先分解 64 个状态组成的置换，再把每个环解释成一个独立的“环形二进制串不允许相邻 1”计数问题，最后把各环贡献相乘。
环分解阶段恰好访问 64 个状态中的每一个一次，因此时间复杂度是 \(O(64)\)，空间复杂度也是 \(O(64)\)。对长度为 \(L\) 的环计算 Fibonacci 需要 \(O(L)\) 时间，而所有环长之和同样是 64。
所以总复杂度是 \(O(64)\) 时间和 \(O(64)\) 空间。对于这个固定规模的问题，这就是常数级成本。实际最大环长只有 46，因此数值部分也非常轻量。
Пусть \(\tau : \{0,1\}^6 \to \{0,1\}\) задает булеву таблицу истинности на всех 6-битных состояниях. Условие задачи требует, чтобы для каждого состояния \((a,b,c,d,e,f)\) выполнялось
$$\tau(a,b,c,d,e,f)\land\tau\bigl(b,c,d,e,f,a\oplus(b\land c)\bigr)=0.$$
Если ввести переход
$$T(a,b,c,d,e,f)=\bigl(b,c,d,e,f,a\oplus(b\land c)\bigr),$$
то это означает следующее: состояние и его следующий узел по правилу \(T\) не могут одновременно иметь значение 1. Нужно посчитать, сколько всего таблиц \(\tau\) удовлетворяют этому ограничению на всех 64 состояниях.
Главное наблюдение состоит в том, что граф переходов здесь не является произвольным функциональным графом. Отображение \(T\) задает перестановку 64 состояний, а значит весь граф раскладывается в непересекающиеся ориентированные циклы. После этого вся задача сводится к независимому подсчету допустимых меток на каждом цикле.
Решение не перебирает таблицы истинности напрямую. Вместо этого оно сначала находит циклическое разложение отображения на 64 состояниях, а затем считает, сколько бинарных пометок без соседних единиц допускает цикл данной длины.
Обозначим выход \(T\) через \((u,v,w,p,q,r)\). Тогда по определению
$$u=b,\quad v=c,\quad w=d,\quad p=e,\quad q=f,\quad r=a\oplus(b\land c).$$
Отсюда вход восстанавливается однозначно:
$$a=r\oplus(u\land v),\qquad (b,c,d,e,f)=(u,v,w,p,q).$$
Следовательно, у каждого состояния есть ровно один предшественник и ровно один последователь. Отображение \(T\) биективно, поэтому каждая компонента графа уже сама по себе является чистым циклом. Никаких хвостов, входящих в цикл, здесь нет.
Рассмотрим цикл длины \(L\):
$$s_0\to s_1\to \cdots \to s_{L-1}\to s_0.$$
Положим
$$x_i=\tau(s_i)\in\{0,1\}.$$
Тогда условие задачи эквивалентно соотношениям
$$x_i x_{i+1}=0\qquad\text{для всех }i\pmod L.$$
Иначе говоря, на цикле нужно посчитать бинарные кольцевые последовательности без соседних единиц. С точки зрения теории графов это то же самое, что число независимых множеств в циклическом графе из \(L\) вершин.
Разные циклы не пересекаются по состояниям, поэтому их можно считать независимо. Если цикл длины \(L\) дает \(C_L\) допустимых разметок, а разложение перестановки имеет длины \(L_1,\dots,L_k\), то общий ответ равен
$$\prod_{j=1}^k C_{L_j}.$$
Сначала решим линейную версию задачи. Пусть \(P_n\) обозначает число бинарных строк длины \(n\) без соседних единиц. Разбиение по последнему символу дает рекуррентное соотношение
$$P_n=P_{n-1}+P_{n-2},\qquad P_0=1,\quad P_1=2.$$
Отсюда следует
$$P_n=F_{n+2},$$
где \(F_0=0\), \(F_1=1\), а \(F_{m+2}=F_{m+1}+F_m\) задают числа Фибоначчи.
Теперь вернемся к циклу длины \(L\ge 2\). Разобьем по значению первой вершины.
Если \(x_0=0\), то оставшиеся \(L-1\) позиций образуют обычный путь, и мы получаем \(P_{L-1}\) вариантов.
Если \(x_0=1\), то обе соседние вершины \(x_1\) и \(x_{L-1}\) обязаны быть нулями, а внутри остается путь длины \(L-3\), то есть \(P_{L-3}\) вариантов.
Следовательно,
$$C_L=P_{L-1}+P_{L-3}=F_{L+1}+F_{L-1}.$$
Случай \(L=1\) тоже подходит: в 1-цикле единственная вершина не может быть равна 1, поэтому \(C_1=1=F_0+F_2\).
Один из реальных циклов имеет вид
$$000001\to 000010\to 000100\to 001000\to 010000\to 100000\to 000001.$$
Его длина равна 6, поэтому число допустимых значений \(\tau\) на этих шести состояниях равно
$$C_6=P_5+P_3=F_7+F_5=13+5=18.$$
Это хороший наглядный пример формулы: либо первая вершина получает 0 и остальные пять позиций образуют путь, либо первая вершина получает 1, после чего обе ее соседки фиксируются в 0 и остаются только три свободные позиции посередине.
При обходе всех 64 состояний получаются ровно такие длины циклов:
$$1,\ 2,\ 3,\ 6,\ 6,\ 46.$$
Поэтому итоговое число допустимых таблиц равно
$$C_1\,C_2\,C_3\,C_6^2\,C_{46}.$$
Подставляя формулу \(C_L=F_{L-1}+F_{L+1}\), получаем
$$1\cdot 3\cdot 4\cdot 18^2\cdot \bigl(F_{45}+F_{47}\bigr).$$
Так как \(F_{45}=1134903170\), а \(F_{47}=2971215073\), окончательный ответ равен
$$15\,964\,587\,728\,784.$$
Реализации на C++, Python и Java кодируют каждое 6-битное состояние целым числом от 0 до 63. Следующее состояние строится так: младшие пять бит сдвигаются влево, а в младший разряд добавляется бит обратной связи \(a\oplus(b\land c)\). Массив посещения гарантирует, что каждый узел обрабатывается ровно один раз.
Поскольку переход биективен, запуск из любого еще не посещенного состояния немедленно проходит один полный цикл без каких-либо хвостов. Число сделанных шагов до первого повторения и есть длина найденного цикла.
Для каждой длины \(L\) реализация заранее строит числа Фибоначчи до \(F_{L+1}\) и затем вычисляет \(F_{L-1}+F_{L+1}\). После этого все циклические множители перемножаются в 64-битном аккумуляторе.
Во всех трех языках используется одна и та же схема: сначала разложить перестановку на 64 состояниях на циклы, затем посчитать для каждого цикла число допустимых бинарных разметок без соседних единиц и, наконец, перемножить эти вклады.
Разложение на циклы посещает каждый из 64 состояний ровно один раз, поэтому эта часть работает за \(O(64)\) по времени и использует \(O(64)\) памяти. Подготовка Фибоначчи для цикла длины \(L\) стоит \(O(L)\), причем сумма всех длин циклов снова равна 64.
Итак, общая сложность составляет \(O(64)\) по времени и \(O(64)\) по памяти, то есть фактически константу для фиксированного размера задачи. Максимальная длина цикла равна 46, поэтому численная часть вычислений тоже очень мала.
لتكن \(\tau : \{0,1\}^6 \to \{0,1\}\) جدول حقيقة بوليانيًا معرّفًا على جميع الحالات ذات الستة بتات. يفرض السؤال الشرط التالي لكل حالة \((a,b,c,d,e,f)\):
$$\tau(a,b,c,d,e,f)\land\tau\bigl(b,c,d,e,f,a\oplus(b\land c)\bigr)=0.$$
إذا عرّفنا انتقال الحالة بواسطة
$$T(a,b,c,d,e,f)=\bigl(b,c,d,e,f,a\oplus(b\land c)\bigr),$$
فهذا يعني أن أي حالة وقيمتها التالية تحت \(T\) لا يجوز أن تُسندا كلتاهما إلى 1. المطلوب هو عدّ جميع جداول الحقيقة التي تحقق هذا القيد على الحالات الـ64 كلها.
الفكرة الحاسمة هنا أن مخطط الانتقال ليس رسمًا داليًا عامًا فيه فروع وذيول، بل هو في الحقيقة تبديل على 64 حالة. لذلك ينقسم الفضاء كله إلى دورات منفصلة، ويصبح الحل حاصل ضرب عدد التعيينات المسموح بها على كل دورة على حدة.
التنفيذ لا يحاول استعراض \(2^{64}\) جدولًا ممكنًا. بدلًا من ذلك يبدأ بتحليل البنية الحقيقية لانتقال الحالات الستية، ثم يحسب على كل دورة عدد التوسيمات الثنائية التي تمنع ظهور 1 متجاورتين على طول الدورة.
لنكتب خرج \(T\) على الصورة \((u,v,w,p,q,r)\). حسب التعريف لدينا
$$u=b,\quad v=c,\quad w=d,\quad p=e,\quad q=f,\quad r=a\oplus(b\land c).$$
ومن هذه المعادلات نستعيد الحالة السابقة بشكل وحيد:
$$a=r\oplus(u\land v),\qquad (b,c,d,e,f)=(u,v,w,p,q).$$
إذن لكل حالة تالية سلف وحيد، وبالمثل لكل حالة تابع وحيد، أي إن \(T\) تقابل على مجموعة الحالات الـ64. وهذه النقطة تعني أن كل مركبة متصلة في المخطط هي دورة خالصة، من دون أي أشجار أو مسارات جانبية تنتهي داخل دورة.
خذ دورة طولها \(L\):
$$s_0\to s_1\to \cdots \to s_{L-1}\to s_0.$$
ولنعرّف
$$x_i=\tau(s_i)\in\{0,1\}.$$
عندئذ يصبح شرط المسألة
$$x_i x_{i+1}=0\qquad (i=0,1,\dots,L-1).$$
أي إننا نعدّ السلاسل الثنائية الدائرية التي لا تحتوي على 1 متجاورتين. ومن منظور نظرية الرسوم فهذا يساوي عدد المجموعات المستقلة في رسم دائري له \(L\) رأسًا.
ولأن الدورات منفصلة تمامًا ولا تتشارك حالات، فإن اختيار القيم على دورة لا يؤثر في أي دورة أخرى. إذا كان عدد التعيينات المسموح بها على دورة طولها \(L\) هو \(C_L\)، وكانت أطوال الدورات كلها هي \(L_1,L_2,\dots,L_k\)، فإن الجواب الكلي يساوي
$$\prod_{j=1}^k C_{L_j}.$$
من المفيد أولًا عدّ السلاسل على مسار خطي. لنرمز بـ \(P_n\) إلى عدد السلاسل الثنائية بطول \(n\) التي لا تحتوي على 1 متجاورتين. بالفصل حسب البت الأخير نحصل على العلاقة
$$P_n=P_{n-1}+P_{n-2},\qquad P_0=1,\quad P_1=2.$$
ومن ثم
$$P_n=F_{n+2},$$
حيث \(F_0=0\)، و\(F_1=1\)، وتحقق أعداد فيبوناتشي العلاقة \(F_{m+2}=F_{m+1}+F_m\).
الآن نرجع إلى دورة طولها \(L\ge 2\). نقسم حسب قيمة الموضع الأول.
إذا كان \(x_0=0\)، فإن المواضع المتبقية وعددها \(L-1\) تشكل مسارًا عاديًا، وبالتالي تسهم بـ \(P_{L-1}\) حالة.
أما إذا كان \(x_0=1\)، فلابد أن يكون الجاران \(x_1\) و\(x_{L-1}\) مساويين للصفر، ويبقى مسار داخلي طوله \(L-3\)، فيكون عدد الحالات \(P_{L-3}\).
إذن
$$C_L=P_{L-1}+P_{L-3}=F_{L+1}+F_{L-1}.$$
وحالة \(L=1\) تنسجم مع الصيغة نفسها: العقدة الوحيدة في دورة الطول 1 لا يمكن أن تأخذ القيمة 1، ومن ثم \(C_1=1=F_0+F_2\).
إحدى الدورات الفعلية الناتجة عن \(T\) هي
$$000001\to 000010\to 000100\to 001000\to 010000\to 100000\to 000001.$$
وهذه دورة طولها 6. لذلك فإن عدد التوسيمات المسموح بها على هذه الحالات الست يساوي
$$C_6=P_5+P_3=F_7+F_5=13+5=18.$$
هذا المثال يوضح الاشتقاق بوضوح: إما أن تكون الحالة الأولى صفرًا، فتتبقى خمس خانات على مسار، أو تكون واحدًا، وعندها يُجبر جاراها على الصفر ولا يتبقى إلا ثلاث خانات حرة في الوسط.
عند تتبع الحالات الـ64 كلها نحصل بالضبط على أطوال الدورات التالية:
$$1,\ 2,\ 3,\ 6,\ 6,\ 46.$$
وبالتالي فإن العدد الكلي لجداول الحقيقة المسموح بها هو
$$C_1\,C_2\,C_3\,C_6^2\,C_{46}.$$
وبالتعويض عن \(C_L\) بصيغته نحصل على
$$1\cdot 3\cdot 4\cdot 18^2\cdot \bigl(F_{45}+F_{47}\bigr).$$
ومع \(F_{45}=1134903170\) و\(F_{47}=2971215073\)، تكون النتيجة النهائية
$$15\,964\,587\,728\,784.$$
تمثل تطبيقات C++ وPython وJava كل حالة من الحالات الستية بعدد صحيح بين 0 و63. ثم تحسب الحالة التالية بإزاحة البتات الخمسة الدنيا إلى اليسار وإلحاق بت التغذية الراجعة \(a\oplus(b\land c)\) في النهاية. وتضمن مصفوفة الزيارة ألا تُعالج أي حالة أكثر من مرة.
وبما أن الانتقال تقابلي، فإن البدء من أي حالة غير مزارة واتباع التابع مرارًا يمر مباشرة عبر دورة واحدة كاملة من دون ذيول. وعدد الخطوات حتى أول تكرار هو طول تلك الدورة.
لكل طول \(L\)، تبني الشيفرة أعداد فيبوناتشي حتى \(F_{L+1}\)، ثم تحسب المقدار \(F_{L-1}+F_{L+1}\). بعد ذلك تُضرب جميع هذه العوامل في مجمّع عددي واحد من نوع 64-بت.
الفكرة الرياضية واحدة في اللغات الثلاث: تفكيك تبديل الحالات الـ64 إلى دورات، ثم عدّ التعيينات المسموح بها على كل دورة باعتبارها مسألة "لا يوجد 1 متجاورتان"، وأخيرًا ضرب المساهمات كلها.
مرحلة استخراج الدورات تزور كل واحدة من الحالات الـ64 مرة واحدة فقط، لذا تكلفتها \(O(64)\) زمنًا و\(O(64)\) ذاكرة. أما تجهيز فيبوناتشي لدورة طولها \(L\) فيكلف \(O(L)\)، ومجموع أطوال جميع الدورات يساوي 64 أيضًا.
إذن فالتعقيد الكلي هو \(O(64)\) زمنًا و\(O(64)\) ذاكرة، أي تكلفة ثابتة عمليًا لهذا الحجم الثابت من المسألة. كما أن أطول دورة طولها 46 فقط، لذلك فالحسابات العددية صغيرة جدًا.