For an \(n\)-bit state \(x\), write
$$x=b_0+2b_1+4b_2+\cdots+2^{n-1}b_{n-1},\qquad b_i\in\{0,1\}.$$
The transition rule keeps shifting the bits to the right and inserts a new highest bit given by
$$b_0\land(b_1\oplus b_2).$$
So the next state is
$$f(x)=\left\lfloor\frac{x}{2}\right\rfloor+2^{n-1}\bigl(b_0\land(b_1\oplus b_2)\bigr).$$
The implementations reduce the counting task to the following graph problem on the \(N=2^n\) states: count all subsets of vertices such that no state is chosen together with its image under \(f\). In graph-theoretic language, this is an independent-set count on a special functional digraph, and the final result is taken modulo \(1001001011\).
Let \(G_n\) be the directed graph with one vertex for each state \(x\in\{0,1,\dots,2^n-1\}\) and one directed edge \(x\to f(x)\). Because every vertex has exactly one outgoing edge, every connected component of \(G_n\) has a very rigid shape: one directed cycle, with rooted trees feeding into the cycle.
The mapping \(f\) is completely determined by the lowest three bits of \(x\). Every vertex therefore has outdegree \(1\), although its indegree may vary. This matters because graphs of outdegree \(1\) are functional graphs, and each component decomposes into exactly one cycle plus zero or more in-trees.
That decomposition is the structural reason the problem is tractable. Instead of counting admissible subsets on the full graph at once, we can solve each component separately and multiply the answers.
If a subset \(S\) of states is valid, then no directed edge \(x\to f(x)\) may have both endpoints in \(S\). Since the restriction only concerns adjacent states, we can forget the arrow direction for counting purposes and work with the underlying undirected graph.
So the problem becomes: how many independent sets does each unicyclic component have? Once that is known, the total answer is
$$\prod_{\text{components }C}\operatorname{IS}(C)\pmod{1001001011},$$
where \(\operatorname{IS}(C)\) denotes the number of independent sets in component \(C\).
Take a non-cycle vertex \(u\), and orient its attached tree away from the cycle. Define
$$E(u)=\text{number of valid selections in the subtree of }u\text{ when }u\text{ is excluded},$$
$$I(u)=\text{number of valid selections in the subtree of }u\text{ when }u\text{ is included}.$$
If the children of \(u\) are \(v_1,\dots,v_k\), then standard tree DP gives
$$E(u)=\prod_{j=1}^{k}\bigl(E(v_j)+I(v_j)\bigr),$$
$$I(u)=\prod_{j=1}^{k}E(v_j).$$
The first formula allows each child to be either excluded or included. The second forbids including any child once \(u\) itself is included. A leaf satisfies
$$E(u)=1,\qquad I(u)=1.$$
Now consider a cycle \(c_1,c_2,\dots,c_m\). Each cycle vertex may have extra tree children that are not on the cycle. After solving those trees, we compress their effect into two local weights:
$$W_i^{(0)}=\prod_{v\in T_i}\bigl(E(v)+I(v)\bigr),$$
$$W_i^{(1)}=\prod_{v\in T_i}E(v),$$
where \(T_i\) is the set of non-cycle children attached directly to \(c_i\).
Interpretation:
\(W_i^{(0)}\) counts all valid choices in the incoming trees when \(c_i\) is not selected.
\(W_i^{(1)}\) counts all valid choices in the incoming trees when \(c_i\) is selected, so every attached child must stay out.
After this compression, the whole component is reduced to a weighted cycle.
For a path version of the cycle, let
$$P_i^{(0)}=\text{weighted count up to }c_i\text{ with }c_i\text{ excluded},$$
$$P_i^{(1)}=\text{weighted count up to }c_i\text{ with }c_i\text{ included}.$$
Then for \(i\ge 2\),
$$P_i^{(0)}=\bigl(P_{i-1}^{(0)}+P_{i-1}^{(1)}\bigr)W_i^{(0)},$$
$$P_i^{(1)}=P_{i-1}^{(0)}W_i^{(1)}.$$
Because \(c_1\) and \(c_m\) are adjacent on the cycle, we split into two boundary cases.
Case A: \(c_1\) is excluded. Start with
$$P_1^{(0)}=W_1^{(0)},\qquad P_1^{(1)}=0.$$
This contributes
$$P_m^{(0)}+P_m^{(1)}.$$
Case B: \(c_1\) is included. Start with
$$P_1^{(0)}=0,\qquad P_1^{(1)}=W_1^{(1)}.$$
Now \(c_m\) must be excluded, so this contributes only
$$P_m^{(0)}.$$
If \(m=1\), the cycle is a self-loop. Then the lone cycle vertex cannot be selected at all, and the component contributes simply
$$W_1^{(0)}.$$
For \(n=3\) there are \(8\) states. Writing states in binary, the transition graph splits into two components:
000 -> 000, with the chain 100 -> 010 -> 001 -> 000.
011 -> 101 -> 110 -> 011, with the extra leaf 111 -> 011.
In the first component, 000 is a self-loop, so it cannot be chosen. What remains is the path 100-010-001, whose independent sets are
$$\varnothing,\ \{100\},\ \{010\},\ \{001\},\ \{100,001\},$$
so that component contributes \(5\).
In the second component, the leaf attached to 011 gives weights
$$W_1^{(0)}=2,\qquad W_1^{(1)}=1,$$
while the other two cycle vertices have weights
$$W_2^{(0)}=W_2^{(1)}=W_3^{(0)}=W_3^{(1)}=1.$$
Case A, first cycle vertex excluded:
$$P_1=(2,0),\qquad P_2=(2,2),\qquad P_3=(4,2),$$
so the contribution is \(4+2=6\).
Case B, first cycle vertex included:
$$P_1=(0,1),\qquad P_2=(1,0),\qquad P_3=(1,1),$$
and only the excluded-last state is allowed, so the contribution is \(1\).
Thus the 3-cycle component contributes \(6+1=7\), and the total is
$$5\cdot 7=35,$$
which matches the small checkpoint used by the implementation.
The C++, Python, and Java implementations first build the transition table for all \(2^n\) states and, at the same time, the reverse adjacency lists that list every predecessor of each state. They then find every directed cycle by a standard three-color walk: unvisited, currently on the path, and fully processed. Whenever a walk re-enters a currently active vertex, the cycle segment is recorded.
After the cycles are known, the implementation evaluates every incoming tree exactly once with a post-order dynamic program. Those tree values are folded into the two weights for each cycle vertex, and then a second DP is run around the cycle using the two boundary cases described above. Each component count is multiplied into the global answer modulo \(1001001011\).
Let \(N=2^n\). Building the transition table and reverse graph takes \(O(N)\) time and \(O(N)\) memory. Cycle detection also visits each vertex a constant number of times, so it is \(O(N)\). The tree DP and cycle DP together process each edge and each vertex only once more, so the total running time remains
$$O(N)=O(2^n),$$
with memory usage
$$O(N)=O(2^n).$$
For the actual input \(n=20\), this means linear work over \(1{,}048{,}576\) states, which is exactly why the graph decomposition is effective.
Für einen \(n\)-Bit-Zustand \(x\) schreiben wir
$$x=b_0+2b_1+4b_2+\cdots+2^{n-1}b_{n-1},\qquad b_i\in\{0,1\}.$$
Die Übergangsregel schiebt alle Bits um eine Position nach rechts und setzt das neue höchstwertige Bit auf
$$b_0\land(b_1\oplus b_2).$$
Damit gilt
$$f(x)=\left\lfloor\frac{x}{2}\right\rfloor+2^{n-1}\bigl(b_0\land(b_1\oplus b_2)\bigr).$$
Die Implementierungen formulieren die Aufgabe als Graphproblem auf den \(N=2^n\) Zuständen: Gesucht ist die Anzahl aller Teilmengen von Zuständen, in denen niemals ein Zustand zusammen mit seinem Bild unter \(f\) ausgewählt wird. Graphentheoretisch ist das eine Zählung unabhängiger Mengen in einem speziellen funktionalen Digraphen, jeweils modulo \(1001001011\).
Sei \(G_n\) der gerichtete Graph mit einer Ecke für jeden Zustand \(x\in\{0,1,\dots,2^n-1\}\) und genau einer Kante \(x\to f(x)\). Da jede Ecke genau eine ausgehende Kante besitzt, hat jede Zusammenhangskomponente eine feste Form: einen gerichteten Zyklus, in den gerichtete Bäume einspeisen.
Die Abbildung \(f\) hängt nur von den drei niederwertigsten Bits von \(x\) ab. Deshalb hat jeder Knoten Ausgrad \(1\), auch wenn der Eingrad unterschiedlich sein kann. Genau solche Graphen sind funktionale Graphen, und jede ihrer Komponenten zerfällt in genau einen Zyklus plus eingehende Bäume.
Diese Struktur macht die Aufgabe lösbar. Statt alle zulässigen Teilmengen gleichzeitig zu zählen, bestimmen wir die Anzahl komponentenweise und multiplizieren die Resultate.
Ist \(S\) eine gültige Zustandsmenge, dann darf für keine gerichtete Kante \(x\to f(x)\) gelten, dass beide Endpunkte in \(S\) liegen. Für die Zählung spielt die Pfeilrichtung dabei keine Rolle; entscheidend ist nur die Nachbarschaft.
Somit lautet das Problem: Wie viele unabhängige Mengen besitzt jede unizyklische Komponente? Die Gesamtzahl ist dann
$$\prod_{\text{Komponenten }C}\operatorname{IS}(C)\pmod{1001001011},$$
wobei \(\operatorname{IS}(C)\) die Anzahl unabhängiger Mengen in \(C\) bezeichnet.
Betrachte einen Nicht-Zyklus-Knoten \(u\) und seinen an den Zyklus gerichteten Baum. Wir definieren
$$E(u)=\text{Anzahl gültiger Auswahlen im Teilbaum von }u,\text{ falls }u\text{ nicht gewählt ist},$$
$$I(u)=\text{Anzahl gültiger Auswahlen im Teilbaum von }u,\text{ falls }u\text{ gewählt ist}.$$
Für die Kinder \(v_1,\dots,v_k\) von \(u\) erhält man die Standardrekursion
$$E(u)=\prod_{j=1}^{k}\bigl(E(v_j)+I(v_j)\bigr),$$
$$I(u)=\prod_{j=1}^{k}E(v_j).$$
Im ersten Fall darf jedes Kind unabhängig gewählt oder nicht gewählt werden. Im zweiten Fall muss jedes Kind ausgeschlossen bleiben, weil benachbarte Knoten nicht gleichzeitig in der unabhängigen Menge liegen dürfen. Für ein Blatt gilt
$$E(u)=1,\qquad I(u)=1.$$
Sei nun \(c_1,c_2,\dots,c_m\) ein Zyklus. Jeder Zyklusknoten kann zusätzliche Kinder besitzen, die nicht auf dem Zyklus liegen. Nach dem Lösen dieser Teilbäume fassen wir ihren Beitrag in zwei lokalen Gewichten zusammen:
$$W_i^{(0)}=\prod_{v\in T_i}\bigl(E(v)+I(v)\bigr),$$
$$W_i^{(1)}=\prod_{v\in T_i}E(v),$$
wobei \(T_i\) die Menge der direkt an \(c_i\) hängenden Nicht-Zyklus-Kinder ist.
\(W_i^{(0)}\) zählt alle Möglichkeiten in den anhängenden Bäumen, wenn \(c_i\) ausgeschlossen ist. \(W_i^{(1)}\) zählt alle Möglichkeiten, wenn \(c_i\) aufgenommen wird und deshalb keines seiner Baumkinder gewählt sein darf. Danach bleibt nur noch ein gewichteter Zyklus übrig.
Für die geöffnete Zykluslinie definieren wir
$$P_i^{(0)}=\text{gewichtete Anzahl bis }c_i\text{ mit }c_i\text{ ausgeschlossen},$$
$$P_i^{(1)}=\text{gewichtete Anzahl bis }c_i\text{ mit }c_i\text{ aufgenommen}.$$
Für \(i\ge 2\) gilt dann
$$P_i^{(0)}=\bigl(P_{i-1}^{(0)}+P_{i-1}^{(1)}\bigr)W_i^{(0)},$$
$$P_i^{(1)}=P_{i-1}^{(0)}W_i^{(1)}.$$
Da \(c_1\) und \(c_m\) benachbart sind, werden zwei Anfangsfälle getrennt behandelt.
Fall A: \(c_1\) ist ausgeschlossen. Dann starten wir mit
$$P_1^{(0)}=W_1^{(0)},\qquad P_1^{(1)}=0,$$
und erhalten als Beitrag
$$P_m^{(0)}+P_m^{(1)}.$$
Fall B: \(c_1\) ist aufgenommen. Dann gilt
$$P_1^{(0)}=0,\qquad P_1^{(1)}=W_1^{(1)},$$
und wegen der Nachbarschaft zu \(c_m\) darf am Ende nur
$$P_m^{(0)}$$
gezählt werden. Für \(m=1\) liegt eine Selbstschleife vor; der einzige Zyklusknoten darf dann überhaupt nicht gewählt werden und der Beitrag ist einfach
$$W_1^{(0)}.$$
Für \(n=3\) gibt es \(8\) Zustände. Der Übergangsgraph zerfällt in zwei Komponenten:
000 -> 000, mit der Kette 100 -> 010 -> 001 -> 000.
011 -> 101 -> 110 -> 011, mit dem zusätzlichen Blatt 111 -> 011.
In der ersten Komponente ist 000 eine Selbstschleife und damit nicht wählbar. Übrig bleibt der Pfad 100-010-001 mit den unabhängigen Mengen
$$\varnothing,\ \{100\},\ \{010\},\ \{001\},\ \{100,001\},$$
also Beitrag \(5\).
In der zweiten Komponente liefert das Blatt an 011 die Gewichte
$$W_1^{(0)}=2,\qquad W_1^{(1)}=1,$$
und für die beiden anderen Zyklusknoten gilt jeweils \(1\) in beiden Zuständen.
Fall A, erster Zyklusknoten ausgeschlossen:
$$P_1=(2,0),\qquad P_2=(2,2),\qquad P_3=(4,2),$$
also Beitrag \(6\).
Fall B, erster Zyklusknoten aufgenommen:
$$P_1=(0,1),\qquad P_2=(1,0),\qquad P_3=(1,1),$$
wovon wegen der Randbedingung nur \(1\) zulässig ist. Insgesamt trägt diese Komponente also \(7\) bei, und damit
$$5\cdot 7=35,$$
genau wie im Kontrolltest der Implementierung.
Die C++-, Python- und Java-Implementierungen erzeugen zunächst für alle \(2^n\) Zustände die Übergangstabelle und zugleich die umgekehrten Nachbarschaftslisten aller Vorgänger. Anschließend werden alle gerichteten Zyklen mit einer Drei-Farben-Markierung gefunden: noch unbesucht, aktuell auf dem Suchpfad und vollständig verarbeitet. Sobald ein Lauf wieder auf einen aktiven Knoten trifft, ist der Zyklusteil identifiziert.
Danach wird jeder eingehende Baum genau einmal in Nachbearbeitungsreihenfolge ausgewertet. Aus diesen Baumwerten entstehen die beiden Gewichte jedes Zyklusknotens. Auf dem Zyklus selbst läuft dann die zweite DP mit den zwei Randfällen. Die Beiträge aller Komponenten werden schließlich modulo \(1001001011\) multipliziert.
Mit \(N=2^n\) benötigt der Aufbau der Übergänge und der Rückwärtskanten \(O(N)\) Zeit und \(O(N)\) Speicher. Auch die Zyklensuche besucht jeden Knoten nur konstant oft und ist damit \(O(N)\). Die Baum-DP und die Zyklus-DP verarbeiten danach jede Kante und jeden Knoten nur noch einmal. Insgesamt ergibt sich also
$$O(N)=O(2^n)$$
Zeit und
$$O(N)=O(2^n)$$
Speicher. Für den eigentlichen Fall \(n=20\) bedeutet das lineare Arbeit auf \(1{,}048{,}576\) Zuständen.
Bir \(n\)-bit durumunu
$$x=b_0+2b_1+4b_2+\cdots+2^{n-1}b_{n-1},\qquad b_i\in\{0,1\}$$
şeklinde yazalım. Geçiş kuralı bitleri sağa kaydırır ve en yüksek bite
$$b_0\land(b_1\oplus b_2)$$
değerini yerleştirir. Yani bir sonraki durum
$$f(x)=\left\lfloor\frac{x}{2}\right\rfloor+2^{n-1}\bigl(b_0\land(b_1\oplus b_2)\bigr)$$
olur. C++, Python ve Java çözümleri, problemi \(N=2^n\) adet durum üzerinde şu grafik problemine dönüştürür: bir durum ile onun \(f\) altındaki görüntüsü aynı anda seçilmeyecek şekilde kaç altküme seçilebilir? Grafik teorisi açısından bu, özel bir fonksiyonel digrafta bağımsız küme sayımıdır ve sonuç \(1001001011\) modunda alınır.
\(G_n\), her durum \(x\in\{0,1,\dots,2^n-1\}\) için bir düğüm ve her düğümden \(f(x)\)'e giden tek bir yönlü kenar içeren grafik olsun. Her düğümün çıkış derecesi \(1\) olduğu için her bağlı bileşen tam olarak bir yönlü çevrim ve bu çevrime akan ağaçlardan oluşur.
\(f\) eşlemesi yalnızca \(x\)'in en düşük üç bitine bakar. Bu yüzden her düğümün tek bir ardılı vardır; buna karşılık bir düğüme gelen öncül sayısı değişebilir. Çıkış derecesi \(1\) olan bu tür yapılar fonksiyonel grafiklerdir ve her bileşenleri bir çevrim artı giriş ağaçları biçiminde ayrışır.
Bu ayrışım çözümün temelidir. Tüm grafiği bir anda saymak yerine, her bileşeni ayrı çözüp sonuçları çarparız.
Geçerli bir durum kümesi \(S\) için hiçbir \(x\to f(x)\) kenarının iki ucu da aynı anda \(S\) içinde olamaz. Sayım açısından okun yönü önemli değildir; önemli olan komşuluk ilişkisidir.
Dolayısıyla problem şu hale gelir: her unisiklik bileşenin kaç bağımsız kümesi vardır? Toplam cevap
$$\prod_{\text{bileşen }C}\operatorname{IS}(C)\pmod{1001001011}$$
şeklindedir. Burada \(\operatorname{IS}(C)\), \(C\) bileşenindeki bağımsız küme sayısını gösterir.
Çevrim dışında kalan bir \(u\) düğümünü ele alalım. Çevrime doğru köklenen ağacında şu iki değeri tanımlayalım:
$$E(u)=u\text{ seçili değilken }u\text{ alt ağacındaki geçerli seçim sayısı},$$
$$I(u)=u\text{ seçiliyken }u\text{ alt ağacındaki geçerli seçim sayısı}.$$
\(u\)'nun çocukları \(v_1,\dots,v_k\) ise klasik ağaç DP bağıntıları
$$E(u)=\prod_{j=1}^{k}\bigl(E(v_j)+I(v_j)\bigr),$$
$$I(u)=\prod_{j=1}^{k}E(v_j)$$
olur. İlk formülde her çocuk bağımsız biçimde seçilebilir ya da seçilmeyebilir. İkinci formülde ise \(u\) seçili olduğundan hiçbir çocuk seçilemez. Bir yaprak için
$$E(u)=1,\qquad I(u)=1$$
elde edilir.
Şimdi \(c_1,c_2,\dots,c_m\) çevrimini düşünelim. Her çevrim düğümünün, çevrim üzerinde olmayan bazı çocukları olabilir. Bu alt ağaçlar çözüldükten sonra etkilerini iki ağırlıkta toplarız:
$$W_i^{(0)}=\prod_{v\in T_i}\bigl(E(v)+I(v)\bigr),$$
$$W_i^{(1)}=\prod_{v\in T_i}E(v),$$
burada \(T_i\), doğrudan \(c_i\)'ye bağlı olan çevrim-dışı çocuklar kümesidir.
\(W_i^{(0)}\), \(c_i\) seçilmediğinde bağlı ağaçlarda kaç geçerli seçim olduğunu verir. \(W_i^{(1)}\) ise \(c_i\) seçildiğinde, tüm bu çocukların dışarıda kalması gerektiği durumda kalan seçim sayısıdır. Böylece tüm bileşen, ağırlıklı bir çevrime indirgenmiş olur.
Çevrimi bir yol gibi açıp
$$P_i^{(0)}=c_i\text{ seçilmezken }c_i\text{'ye kadar olan ağırlıklı sayım},$$
$$P_i^{(1)}=c_i\text{ seçiliyken }c_i\text{'ye kadar olan ağırlıklı sayım}$$
tanımlarını yapalım. O zaman \(i\ge 2\) için
$$P_i^{(0)}=\bigl(P_{i-1}^{(0)}+P_{i-1}^{(1)}\bigr)W_i^{(0)},$$
$$P_i^{(1)}=P_{i-1}^{(0)}W_i^{(1)}$$
olur.
Fakat \(c_1\) ile \(c_m\) çevrimde komşu olduğu için iki ayrı başlangıç durumu gerekir.
Durum A: \(c_1\) seçilmez. Başlangıç
$$P_1^{(0)}=W_1^{(0)},\qquad P_1^{(1)}=0$$
olur ve katkı
$$P_m^{(0)}+P_m^{(1)}$$
şeklindedir.
Durum B: \(c_1\) seçilir. Başlangıç
$$P_1^{(0)}=0,\qquad P_1^{(1)}=W_1^{(1)}$$
olur. Bu kez \(c_m\) seçilemez; katkı yalnızca
$$P_m^{(0)}$$
kadardır. Eğer \(m=1\) ise elimizde bir öz-ilmek vardır; bu durumda çevrim düğümü hiç seçilemez ve bileşen katkısı doğrudan
$$W_1^{(0)}$$
olur.
\(n=3\) için \(8\) durum vardır. Geçiş grafiği iki bileşene ayrılır:
000 -> 000, buna bağlı zincir de 100 -> 010 -> 001 -> 000.
011 -> 101 -> 110 -> 011, ayrıca 111 -> 011 yaprağı.
İlk bileşende 000 bir öz-ilmektir; dolayısıyla seçilemez. Geriye kalan 100-010-001 yolu için bağımsız kümeler
$$\varnothing,\ \{100\},\ \{010\},\ \{001\},\ \{100,001\}$$
olduğundan katkı \(5\)'tir.
İkinci bileşende 011'ye bağlı yaprak şu ağırlıkları üretir:
$$W_1^{(0)}=2,\qquad W_1^{(1)}=1.$$
Diğer iki çevrim düğümünde ise her iki ağırlık da \(1\)'dir.
Durum A, ilk düğüm seçilmezse:
$$P_1=(2,0),\qquad P_2=(2,2),\qquad P_3=(4,2),$$
yani katkı \(6\).
Durum B, ilk düğüm seçilirse:
$$P_1=(0,1),\qquad P_2=(1,0),\qquad P_3=(1,1),$$
ve son düğüm seçilemeyeceği için katkı \(1\).
Böylece ikinci bileşen \(7\), toplam ise
$$5\cdot 7=35$$
olur. Bu değer uygulamadaki küçük doğrulama sonucu ile aynıdır.
C++, Python ve Java uygulamaları önce tüm \(2^n\) durumlar için geçiş tablosunu ve her düğümün öncüllerini tutan ters komşuluk yapısını kurar. Sonra üç renkli bir gezinme ile tüm yönlü çevrimleri bulur: hiç görülmemiş, o anda yol üzerinde olan ve tamamen işlenmiş düğümler. Arama aktif bir düğüme geri döndüğünde çevrim bölümü saptanmış olur.
Çevrimler belirlendikten sonra her giriş ağacı sonradan işleme sırasıyla tam bir kez değerlendirilir. Bu değerler çevrim düğümlerinin iki yerel ağırlığına dönüştürülür ve ardından çevrim üzerinde iki sınır durumu ile ikinci DP yürütülür. Son aşamada tüm bileşen katkıları \(1001001011\) modunda çarpılır.
\(N=2^n\) olmak üzere geçiş tablosunu ve ters grafiği kurmak \(O(N)\) zaman ve \(O(N)\) bellek gerektirir. Çevrim bulma da her düğümü sabit sayıda ziyaret ettiği için \(O(N)\)'dir. Ağaç DP'si ve çevrim DP'si her düğüm ve kenarı bir kez daha işler. Dolayısıyla toplam çalışma süresi
$$O(N)=O(2^n)$$
ve toplam bellek kullanımı
$$O(N)=O(2^n)$$
olur. Gerçek girdi olan \(n=20\) için bu, \(1{,}048{,}576\) durum üzerinde doğrusal çalışma anlamına gelir.
Para un estado de \(n\) bits escribimos
$$x=b_0+2b_1+4b_2+\cdots+2^{n-1}b_{n-1},\qquad b_i\in\{0,1\}.$$
La transición desplaza los bits una posición a la derecha e inserta como nuevo bit más significativo
$$b_0\land(b_1\oplus b_2).$$
Por tanto, el siguiente estado es
$$f(x)=\left\lfloor\frac{x}{2}\right\rfloor+2^{n-1}\bigl(b_0\land(b_1\oplus b_2)\bigr).$$
Las implementaciones transforman el problema en el siguiente conteo sobre los \(N=2^n\) estados: cuántos subconjuntos pueden elegirse de modo que ningún estado aparezca junto con su imagen bajo \(f\). En términos de teoría de grafos, eso equivale a contar conjuntos independientes en un digrafo funcional especial, siempre módulo \(1001001011\).
Sea \(G_n\) el grafo dirigido con un vértice por cada estado \(x\in\{0,1,\dots,2^n-1\}\) y una única arista \(x\to f(x)\). Como cada vértice tiene exactamente una arista saliente, cada componente conexa tiene una forma muy rígida: un ciclo dirigido con árboles orientados que desembocan en él.
La aplicación \(f\) depende solo de los tres bits menos significativos de \(x\). Eso garantiza grado de salida \(1\) para cada vértice, aunque el grado de entrada pueda variar. Los grafos con esta propiedad son grafos funcionales, y cada componente se descompone en un único ciclo más varios árboles entrantes.
Esa descomposición es la razón estructural por la que el problema se puede resolver en tiempo lineal en el número de estados.
Si \(S\) es una selección válida de estados, entonces ninguna arista dirigida \(x\to f(x)\) puede tener sus dos extremos dentro de \(S\). Para contar, la dirección de la arista no importa; solo importa que los extremos sean adyacentes.
Por eso el problema pasa a ser: ¿cuántos conjuntos independientes tiene cada componente unicíclica? El resultado global es
$$\prod_{\text{componentes }C}\operatorname{IS}(C)\pmod{1001001011},$$
donde \(\operatorname{IS}(C)\) representa el número de conjuntos independientes del componente \(C\).
Tomemos un vértice \(u\) que no pertenece al ciclo. En el árbol orientado hacia el ciclo definimos
$$E(u)=\text{número de selecciones válidas en el subárbol de }u\text{ cuando }u\text{ queda fuera},$$
$$I(u)=\text{número de selecciones válidas en el subárbol de }u\text{ cuando }u\text{ se incluye}.$$
Si los hijos de \(u\) son \(v_1,\dots,v_k\), entonces
$$E(u)=\prod_{j=1}^{k}\bigl(E(v_j)+I(v_j)\bigr),$$
$$I(u)=\prod_{j=1}^{k}E(v_j).$$
La primera fórmula permite que cada hijo se elija o no de manera independiente. La segunda obliga a excluir a todos los hijos cuando \(u\) está dentro. Para una hoja se cumple
$$E(u)=1,\qquad I(u)=1.$$
Sea \(c_1,c_2,\dots,c_m\) un ciclo. Cada vértice del ciclo puede tener hijos adicionales fuera del ciclo. Una vez resueltos esos árboles, su efecto se resume en dos pesos locales:
$$W_i^{(0)}=\prod_{v\in T_i}\bigl(E(v)+I(v)\bigr),$$
$$W_i^{(1)}=\prod_{v\in T_i}E(v),$$
donde \(T_i\) es el conjunto de hijos no cíclicos conectados directamente a \(c_i\).
\(W_i^{(0)}\) cuenta todas las elecciones válidas en esos árboles cuando \(c_i\) no se elige. \(W_i^{(1)}\) cuenta las elecciones válidas cuando \(c_i\) sí se elige y, por tanto, ninguno de esos hijos puede entrar. Tras esta compresión, todo el componente queda reducido a un ciclo ponderado.
Al abrir el ciclo como si fuera un camino, definimos
$$P_i^{(0)}=\text{conteo ponderado hasta }c_i\text{ con }c_i\text{ fuera},$$
$$P_i^{(1)}=\text{conteo ponderado hasta }c_i\text{ con }c_i\text{ dentro}.$$
Para \(i\ge 2\) se cumple
$$P_i^{(0)}=\bigl(P_{i-1}^{(0)}+P_{i-1}^{(1)}\bigr)W_i^{(0)},$$
$$P_i^{(1)}=P_{i-1}^{(0)}W_i^{(1)}.$$
Como \(c_1\) y \(c_m\) son adyacentes, hay que separar dos casos.
Caso A: \(c_1\) queda fuera. Se inicia con
$$P_1^{(0)}=W_1^{(0)},\qquad P_1^{(1)}=0,$$
y la contribución final es
$$P_m^{(0)}+P_m^{(1)}.$$
Caso B: \(c_1\) se incluye. Se inicia con
$$P_1^{(0)}=0,\qquad P_1^{(1)}=W_1^{(1)},$$
y ahora \(c_m\) debe quedar fuera, así que solo aporta
$$P_m^{(0)}.$$
Si \(m=1\), el ciclo es un lazo sobre sí mismo. En ese caso el único vértice del ciclo no puede elegirse, y la contribución del componente es simplemente
$$W_1^{(0)}.$$
Cuando \(n=3\) hay \(8\) estados. El grafo de transición se separa en dos componentes:
000 -> 000, con la cadena 100 -> 010 -> 001 -> 000.
011 -> 101 -> 110 -> 011, con la hoja adicional 111 -> 011.
En la primera componente, 000 tiene un lazo propio y por eso no puede seleccionarse. Queda el camino 100-010-001, cuyos conjuntos independientes son
$$\varnothing,\ \{100\},\ \{010\},\ \{001\},\ \{100,001\},$$
de modo que esa componente aporta \(5\).
En la segunda componente, la hoja conectada a 011 produce los pesos
$$W_1^{(0)}=2,\qquad W_1^{(1)}=1,$$
mientras que los otros dos vértices del ciclo tienen pesos \(1\) y \(1\).
Caso A, primer vértice excluido:
$$P_1=(2,0),\qquad P_2=(2,2),\qquad P_3=(4,2),$$
así que aporta \(6\).
Caso B, primer vértice incluido:
$$P_1=(0,1),\qquad P_2=(1,0),\qquad P_3=(1,1),$$
pero solo se permite terminar con el último vértice fuera, así que aporta \(1\).
La componente cíclica contribuye \(7\), y por tanto el total vale
$$5\cdot 7=35,$$
igual que en la comprobación pequeña de la implementación.
Las implementaciones en C++, Python y Java construyen primero la tabla de transiciones para los \(2^n\) estados y, a la vez, las listas inversas de predecesores de cada estado. Después localizan todos los ciclos dirigidos con un recorrido de tres colores: no visitado, activo en la ruta actual y ya procesado. Cuando el recorrido vuelve a un vértice activo, el segmento correspondiente forma un ciclo.
Una vez identificados los ciclos, cada árbol entrante se evalúa exactamente una vez con una DP en postorden. Esos valores se absorben en los dos pesos de cada vértice del ciclo, y luego se ejecuta la DP del ciclo con los dos casos de borde descritos antes. Finalmente, todas las componentes se multiplican módulo \(1001001011\).
Si \(N=2^n\), construir la tabla de transiciones y el grafo inverso cuesta \(O(N)\) tiempo y \(O(N)\) memoria. La detección de ciclos también es \(O(N)\) porque cada vértice se visita un número constante de veces. La DP de árboles y la DP de ciclos vuelven a procesar cada vértice y cada arista una sola vez. En conjunto, el coste total es
$$O(N)=O(2^n),$$
con uso de memoria
$$O(N)=O(2^n).$$
Para el caso real \(n=20\), esto significa trabajo lineal sobre \(1{,}048{,}576\) estados.
把一个 \(n\) 位状态 \(x\) 写成
$$x=b_0+2b_1+4b_2+\cdots+2^{n-1}b_{n-1},\qquad b_i\in\{0,1\}.$$
状态转移会把所有比特整体右移一位，并把新的最高位设为
$$b_0\land(b_1\oplus b_2).$$
因此下一状态为
$$f(x)=\left\lfloor\frac{x}{2}\right\rfloor+2^{n-1}\bigl(b_0\land(b_1\oplus b_2)\bigr).$$
实现代码把题目化成一个图论计数问题：在全部 \(N=2^n\) 个状态组成的图上，统计满足“任意状态都不能和它在 \(f\) 下的像同时被选中”的子集个数。用图论语言说，这就是在一个特殊函数图上统计独立集，最终答案对 \(1001001011\) 取模。
记 \(G_n\) 为这样一个有向图：每个状态 \(x\in\{0,1,\dots,2^n-1\}\) 对应一个顶点，并且存在唯一一条有向边 \(x\to f(x)\)。因为每个顶点的出度恰好为 \(1\)，所以每个连通块都具有固定结构：恰好一个有向环，外加若干棵流向该环的入树。
映射 \(f\) 只由 \(x\) 的最低三位决定，因此每个顶点只有一个后继，虽然前驱数量可能不同。出度恒为 \(1\) 的这类图就是函数图，它们的每个连通块都能分解成“一个环 + 若干棵入树”。
这一步非常关键，因为它告诉我们问题不需要在整个 \(2^n\) 状态空间上暴力枚举，而是可以按连通块分别求解，再把结果相乘。
如果一个状态集合 \(S\) 是合法的，那么任何有向边 \(x\to f(x)\) 的两个端点都不能同时属于 \(S\)。对于计数来说，边的方向并不重要，重要的是相邻顶点不能同时被选。
于是问题变成：每个单环连通块有多少个独立集？总答案就是
$$\prod_{\text{连通块 }C}\operatorname{IS}(C)\pmod{1001001011},$$
其中 \(\operatorname{IS}(C)\) 表示连通块 \(C\) 的独立集数量。
取一个不在环上的顶点 \(u\)，把它所在的入树看成朝向环根的树。定义两个量：
$$E(u)=u\text{ 不选时，}u\text{ 子树中的合法选择数},$$
$$I(u)=u\text{ 选中时，}u\text{ 子树中的合法选择数}.$$
若 \(u\) 的孩子为 \(v_1,\dots,v_k\)，则标准树形 DP 给出
$$E(u)=\prod_{j=1}^{k}\bigl(E(v_j)+I(v_j)\bigr),$$
$$I(u)=\prod_{j=1}^{k}E(v_j).$$
第一式表示当 \(u\) 不选时，每个孩子可以独立地选或不选。第二式表示当 \(u\) 被选中时，所有孩子都必须排除。若 \(u\) 是叶子，则有
$$E(u)=1,\qquad I(u)=1.$$
设环为 \(c_1,c_2,\dots,c_m\)。每个环顶点还可能带着一些不在环上的孩子。把这些子树全部求完之后，可以把它们的影响压缩成两个局部权重：
$$W_i^{(0)}=\prod_{v\in T_i}\bigl(E(v)+I(v)\bigr),$$
$$W_i^{(1)}=\prod_{v\in T_i}E(v),$$
这里 \(T_i\) 表示直接连到 \(c_i\) 且不属于环的孩子集合。
\(W_i^{(0)}\) 表示当 \(c_i\) 不选时，这些挂在它下面的树有多少种合法选法；\(W_i^{(1)}\) 表示当 \(c_i\) 被选中时，由于所有相邻孩子都必须不选，剩下有多少种合法选法。压缩完成后，整个连通块就只剩下一个带权环。
把环暂时切开看成一条链，定义
$$P_i^{(0)}=\text{处理到 }c_i\text{ 时，且 }c_i\text{ 不选的带权方案数},$$
$$P_i^{(1)}=\text{处理到 }c_i\text{ 时，且 }c_i\text{ 选中的带权方案数}.$$
那么当 \(i\ge 2\) 时，有递推
$$P_i^{(0)}=\bigl(P_{i-1}^{(0)}+P_{i-1}^{(1)}\bigr)W_i^{(0)},$$
$$P_i^{(1)}=P_{i-1}^{(0)}W_i^{(1)}.$$
但是 \(c_1\) 与 \(c_m\) 在原环上相邻，所以必须分成两个边界情形。
情形 A：\(c_1\) 不选。初始化为
$$P_1^{(0)}=W_1^{(0)},\qquad P_1^{(1)}=0,$$
最后贡献为
$$P_m^{(0)}+P_m^{(1)}.$$
情形 B：\(c_1\) 选中。初始化为
$$P_1^{(0)}=0,\qquad P_1^{(1)}=W_1^{(1)},$$
此时由于 \(c_m\) 与 \(c_1\) 相邻，最后只能取
$$P_m^{(0)}.$$
如果 \(m=1\)，那就是一个自环。自环顶点不能被选中，所以该连通块的贡献直接是
$$W_1^{(0)}.$$
当 \(n=3\) 时共有 \(8\) 个状态。转移图恰好分成两个连通块：
000 -> 000，并带有链 100 -> 010 -> 001 -> 000。
011 -> 101 -> 110 -> 011，并带有额外叶子 111 -> 011。
在第一个连通块里，000 是自环点，因此不能选。剩下的就是路径 100-010-001，它的独立集为
$$\varnothing,\ \{100\},\ \{010\},\ \{001\},\ \{100,001\},$$
所以这一块贡献 \(5\)。
在第二个连通块里，挂在 011 下方的叶子给出权重
$$W_1^{(0)}=2,\qquad W_1^{(1)}=1,$$
另外两个环点的两种权重都等于 \(1\)。
情形 A，首个环点不选：
$$P_1=(2,0),\qquad P_2=(2,2),\qquad P_3=(4,2),$$
因此贡献 \(6\)。
情形 B，首个环点选中：
$$P_1=(0,1),\qquad P_2=(1,0),\qquad P_3=(1,1),$$
但最后一个环点必须不选，所以这一情形只贡献 \(1\)。
第二个连通块总共贡献 \(7\)，于是整体答案是
$$5\cdot 7=35,$$
这与实现中的小规模校验完全一致。
C++、Python 和 Java 实现都会先为全部 \(2^n\) 个状态建立转移表，同时构造每个状态的前驱列表。随后用标准的三色遍历找出所有有向环：未访问、当前在搜索路径上、以及已经彻底处理完毕。当遍历再次遇到当前路径上的顶点时，就识别出一个环。
得到所有环之后，程序对每一棵流向环的树做一次后序动态规划，计算出相应的树贡献。接着把这些贡献压缩为环上顶点的两类权重，再按前面推导的两种边界情形执行环 DP。最后把每个连通块的计数在模 \(1001001011\) 下相乘，得到最终答案。
设 \(N=2^n\)。建立转移表和反向邻接结构需要 \(O(N)\) 时间与 \(O(N)\) 空间。找环过程也只会对每个顶点做常数次处理，因此仍为 \(O(N)\)。树形 DP 与环上 DP 再各自把每个顶点和边处理一次，所以总时间复杂度为
$$O(N)=O(2^n),$$
总空间复杂度为
$$O(N)=O(2^n).$$
对实际输入 \(n=20\) 而言，这意味着对 \(1{,}048{,}576\) 个状态做线性规模的处理。
Пусть \(x\) является \(n\)-битным состоянием, записанным как
$$x=b_0+2b_1+4b_2+\cdots+2^{n-1}b_{n-1},\qquad b_i\in\{0,1\}.$$
Переход сдвигает все биты вправо и вставляет в старший разряд значение
$$b_0\land(b_1\oplus b_2).$$
Следовательно, следующий узел равен
$$f(x)=\left\lfloor\frac{x}{2}\right\rfloor+2^{n-1}\bigl(b_0\land(b_1\oplus b_2)\bigr).$$
Реализации сводят задачу к подсчёту на множестве из \(N=2^n\) состояний: нужно посчитать число подмножеств, в которых состояние никогда не выбирается одновременно со своим образом под действием \(f\). На языке теории графов это подсчёт независимых множеств в специальном функциональном орграфе по модулю \(1001001011\).
Обозначим через \(G_n\) ориентированный граф, у которого каждой вершине \(x\in\{0,1,\dots,2^n-1\}\) соответствует ровно одно ребро \(x\to f(x)\). Поскольку из каждой вершины выходит ровно одно ребро, каждая связная компонента имеет форму одного направленного цикла с входящими в него деревьями.
Отображение \(f\) определяется только тремя младшими битами состояния. Поэтому исходящая степень каждой вершины равна \(1\), хотя входящая степень может различаться. Такие графы являются функциональными, и каждая их компонента распадается на один цикл и набор деревьев, впадающих в этот цикл.
Именно это разложение делает задачу удобной для динамического программирования.
Если множество состояний \(S\) допустимо, то ни одно ориентированное ребро \(x\to f(x)\) не должно иметь оба конца внутри \(S\). Для подсчёта направление несущественно; важен лишь факт соседства.
Поэтому задача сводится к вопросу: сколько независимых множеств у каждой однокольцевой компоненты? Общий ответ равен
$$\prod_{\text{компоненты }C}\operatorname{IS}(C)\pmod{1001001011},$$
где \(\operatorname{IS}(C)\) обозначает число независимых множеств компоненты \(C\).
Рассмотрим вершину \(u\), не лежащую на цикле. Для её поддерева определим
$$E(u)=\text{число допустимых выборов в поддереве }u,\text{ если }u\text{ не выбрана},$$
$$I(u)=\text{число допустимых выборов в поддереве }u,\text{ если }u\text{ выбрана}.$$
Если детьми вершины \(u\) являются \(v_1,\dots,v_k\), то стандартный переход для независимых множеств на дереве имеет вид
$$E(u)=\prod_{j=1}^{k}\bigl(E(v_j)+I(v_j)\bigr),$$
$$I(u)=\prod_{j=1}^{k}E(v_j).$$
Первое выражение разрешает для каждого ребёнка оба варианта. Второе запрещает выбирать детей, если выбрана сама вершина \(u\). Для листа имеем
$$E(u)=1,\qquad I(u)=1.$$
Пусть цикл состоит из вершин \(c_1,c_2,\dots,c_m\). У каждой из них могут быть дочерние вершины вне цикла. После решения соответствующих деревьев их вклад удобно собрать в два веса:
$$W_i^{(0)}=\prod_{v\in T_i}\bigl(E(v)+I(v)\bigr),$$
$$W_i^{(1)}=\prod_{v\in T_i}E(v),$$
где \(T_i\) есть множество нециклических детей, непосредственно прикреплённых к \(c_i\).
\(W_i^{(0)}\) считает все допустимые конфигурации входящих деревьев, когда \(c_i\) не выбрана. \(W_i^{(1)}\) считает допустимые конфигурации, когда \(c_i\) выбрана, а значит, все эти дети обязаны быть исключены. После такого сжатия компоненту можно рассматривать как взвешенный цикл.
Разрезая цикл в цепочку, введём
$$P_i^{(0)}=\text{взвешенное число конфигураций до }c_i,\text{ если }c_i\text{ не выбрана},$$
$$P_i^{(1)}=\text{взвешенное число конфигураций до }c_i,\text{ если }c_i\text{ выбрана}.$$
Тогда при \(i\ge 2\)
$$P_i^{(0)}=\bigl(P_{i-1}^{(0)}+P_{i-1}^{(1)}\bigr)W_i^{(0)},$$
$$P_i^{(1)}=P_{i-1}^{(0)}W_i^{(1)}.$$
Но вершины \(c_1\) и \(c_m\) соседние, поэтому нужны два стартовых случая.
Случай A: \(c_1\) не выбрана. Тогда
$$P_1^{(0)}=W_1^{(0)},\qquad P_1^{(1)}=0,$$
и вклад равен
$$P_m^{(0)}+P_m^{(1)}.$$
Случай B: \(c_1\) выбрана. Тогда
$$P_1^{(0)}=0,\qquad P_1^{(1)}=W_1^{(1)},$$
и из-за соседства с \(c_m\) допускается только
$$P_m^{(0)}.$$
Если \(m=1\), то цикл вырождается в петлю. Такая вершина не может входить в независимое множество, и вклад компоненты равен просто
$$W_1^{(0)}.$$
При \(n=3\) имеется \(8\) состояний. Граф переходов распадается на две компоненты:
000 -> 000, плюс цепочка 100 -> 010 -> 001 -> 000.
011 -> 101 -> 110 -> 011, плюс лист 111 -> 011.
В первой компоненте вершина 000 имеет петлю, значит, её выбирать нельзя. Остаётся путь 100-010-001, у которого независимые множества таковы:
$$\varnothing,\ \{100\},\ \{010\},\ \{001\},\ \{100,001\},$$
то есть вклад равен \(5\).
Во второй компоненте лист у вершины 011 даёт веса
$$W_1^{(0)}=2,\qquad W_1^{(1)}=1,$$
а для двух остальных вершин цикла оба веса равны \(1\).
Случай A, первая вершина цикла исключена:
$$P_1=(2,0),\qquad P_2=(2,2),\qquad P_3=(4,2),$$
значит, вклад \(6\).
Случай B, первая вершина цикла выбрана:
$$P_1=(0,1),\qquad P_2=(1,0),\qquad P_3=(1,1),$$
но в конце разрешено только состояние с исключённой последней вершиной, поэтому вклад \(1\).
Итак, циклическая компонента даёт \(7\), а общий результат
$$5\cdot 7=35,$$
что совпадает с малой проверкой в реализации.
Реализации на C++, Python и Java сначала строят таблицу переходов для всех \(2^n\) состояний и одновременно формируют обратные списки смежности, то есть списки всех предшественников каждого состояния. Затем все циклы находятся стандартным обходом с тремя цветами: не посещена, находится в текущем пути, полностью обработана. Если обход возвращается в вершину второго типа, обнаружен цикл.
После этого каждое входящее дерево вычисляется ровно один раз в постфиксном порядке. Полученные значения сворачиваются в два веса каждой вершины цикла, а затем выполняется DP по самому циклу в двух граничных случаях. Вклады всех компонент перемножаются по модулю \(1001001011\).
Пусть \(N=2^n\). Построение таблицы переходов и обратного графа требует \(O(N)\) времени и \(O(N)\) памяти. Поиск циклов также работает за \(O(N)\), потому что каждая вершина обрабатывается лишь постоянное число раз. После этого дерево и цикл обрабатываются ещё по одному разу, так что суммарная трудоёмкость равна
$$O(N)=O(2^n),$$
а потребление памяти равно
$$O(N)=O(2^n).$$
Для реального случая \(n=20\) это означает линейную обработку \(1{,}048{,}576\) состояний.
لنكتب الحالة ذات \(n\) بتات على الصورة
$$x=b_0+2b_1+4b_2+\cdots+2^{n-1}b_{n-1},\qquad b_i\in\{0,1\}.$$
قاعدة الانتقال تزحزح البتات إلى اليمين وتضع في البت الأعلى القيمة
$$b_0\land(b_1\oplus b_2).$$
ولذلك تكون الحالة التالية
$$f(x)=\left\lfloor\frac{x}{2}\right\rfloor+2^{n-1}\bigl(b_0\land(b_1\oplus b_2)\bigr).$$
تختزل التطبيقات المسألة إلى عدّ مجموعات جزئية من بين \(N=2^n\) حالة بحيث لا تُختار أي حالة مع صورتها تحت التطبيق \(f\) في الوقت نفسه. بلغة نظرية الرسوم، هذا يساوي عدّ المجموعات المستقلة في رسم وظيفي موجه خاص، مع أخذ النتيجة بترديد \(1001001011\).
لنعرّف \(G_n\) بأنه الرسم الموجه الذي يحتوي على رأس لكل حالة \(x\in\{0,1,\dots,2^n-1\}\) وعلى حافة وحيدة من \(x\) إلى \(f(x)\). بما أن كل رأس يملك حافة خروج واحدة فقط، فإن كل مكوّن متصل يملك شكلاً ثابتًا: دورة موجهة واحدة، ومعها أشجار تتدفق نحو هذه الدورة.
التطبيق \(f\) يعتمد فقط على أقل ثلاثة بتات في \(x\). لذا فدرجة الخروج لكل رأس تساوي \(1\)، مع أن عدد الأسلاف قد يختلف من رأس إلى آخر. هذه بالضبط خاصية الرسوم الوظيفية، حيث ينفك كل مكوّن إلى دورة واحدة وعدة أشجار داخلة إليها.
هذا التفكيك هو السبب الحقيقي الذي يسمح بحل المسألة بكفاءة، لأننا نحل كل مكوّن على حدة ثم نضرب النتائج.
إذا كانت \(S\) مجموعة حالات صالحة، فلا يجوز لأي حافة موجهة \(x\to f(x)\) أن يكون طرفاها موجودين معًا داخل \(S\). واتجاه الحافة لا يهم في العد، لأن المهم فقط هو أن الرؤوس المتجاورة لا تُختار معًا.
إذًا تصبح المسألة: كم عدد المجموعات المستقلة في كل مكوّن أحادي الدورة؟ والجواب الكلي هو
$$\prod_C \operatorname{IS}(C)\pmod{1001001011},$$
حيث \(\operatorname{IS}(C)\) هو عدد المجموعات المستقلة في المكوّن \(C\).
خذ رأسًا \(u\) خارج الدورة. نرمز بـ \(E(u)\) إلى عدد الاختيارات الصحيحة داخل شجرة \(u\) عندما لا نختار \(u\)، ونرمز بـ \(I(u)\) إلى العدد نفسه عندما نختار \(u\).
إذا كانت أبناء \(u\) هي \(v_1,\dots,v_k\)، فالعلاقات القياسية تكون
$$E(u)=\prod_{j=1}^{k}\bigl(E(v_j)+I(v_j)\bigr),$$
$$I(u)=\prod_{j=1}^{k}E(v_j).$$
الصيغة الأولى تسمح لكل ابن بأن يكون مختارًا أو غير مختار باستقلال. أما الصيغة الثانية فتلزم استبعاد جميع الأبناء إذا كان \(u\) نفسه مختارًا. وللورقة نحصل على
$$E(u)=1,\qquad I(u)=1.$$
لتكن الدورة \(c_1,c_2,\dots,c_m\). قد يملك كل رأس من رؤوس الدورة أبناءً إضافيين خارج الدورة. بعد حل تلك الأشجار نضغط أثرها في وزنين محليين:
$$W_i^{(0)}=\prod_{v\in T_i}\bigl(E(v)+I(v)\bigr),$$
$$W_i^{(1)}=\prod_{v\in T_i}E(v),$$
حيث \(T_i\) هي مجموعة الأبناء غير الموجودين على الدورة والمتصلين مباشرة بالرأس \(c_i\).
\(W_i^{(0)}\) يعدّ كل الاختيارات الصحيحة في الأشجار المعلّقة عندما لا نختار \(c_i\). أما \(W_i^{(1)}\) فيعدّ الاختيارات الصحيحة عندما نختار \(c_i\)، وعندئذ يجب استبعاد كل هؤلاء الأبناء. بعد هذا الضغط يصبح المكوّن كله دورة موزونة.
إذا فتحنا الدورة على شكل مسار، فليكن \(P_i^{(0)}\) هو العدد الموزون حتى \(c_i\) عندما يكون \(c_i\) مستبعدًا، وليكن \(P_i^{(1)}\) هو العدد الموزون حتى \(c_i\) عندما يكون \(c_i\) مختارًا.
عند \(i\ge 2\) نحصل على
$$P_i^{(0)}=\bigl(P_{i-1}^{(0)}+P_{i-1}^{(1)}\bigr)W_i^{(0)},$$
$$P_i^{(1)}=P_{i-1}^{(0)}W_i^{(1)}.$$
لكن \(c_1\) و\(c_m\) متجاوران على الدورة الأصلية، لذلك يجب فصل حالتين.
الحالة A: الرأس الأول غير مختار. نبدأ بـ
$$P_1^{(0)}=W_1^{(0)},\qquad P_1^{(1)}=0,$$
وتكون المساهمة
$$P_m^{(0)}+P_m^{(1)}.$$
الحالة B: الرأس الأول مختار. نبدأ بـ
$$P_1^{(0)}=0,\qquad P_1^{(1)}=W_1^{(1)},$$
وعندها يجب أن يكون الرأس الأخير غير مختار، لذلك لا نأخذ إلا
$$P_m^{(0)}.$$
إذا كان \(m=1\)، فلدينا حلقة ذاتية. عندئذ لا يمكن اختيار رأس الدورة مطلقًا، وتكون مساهمة هذا المكوّن ببساطة
$$W_1^{(0)}.$$
عندما \(n=3\) يكون لدينا \(8\) حالات. ينقسم رسم الانتقال إلى مكوّنين:
000 -> 000، ومعه السلسلة 100 -> 010 -> 001 -> 000.
011 -> 101 -> 110 -> 011، ومعه الورقة 111 -> 011.
في المكوّن الأول، الرأس 000 يملك حلقة ذاتية، لذلك لا يمكن اختياره. يبقى المسار 100-010-001، ومجموعاته المستقلة هي
$$\varnothing,\ \{100\},\ \{010\},\ \{001\},\ \{100,001\},$$
ومن ثم تكون مساهمته \(5\).
في المكوّن الثاني، الورقة المعلّقة عند 011 تعطي الوزنين
$$W_1^{(0)}=2,\qquad W_1^{(1)}=1,$$
بينما الوزنان عند رأسي الدورة الآخرين يساويان \(1\) و\(1\).
في الحالة A، مع استبعاد الرأس الأول:
$$P_1=(2,0),\qquad P_2=(2,2),\qquad P_3=(4,2),$$
فتكون المساهمة \(6\).
وفي الحالة B، مع اختيار الرأس الأول:
$$P_1=(0,1),\qquad P_2=(1,0),\qquad P_3=(1,1),$$
لكن النهاية المسموح بها هي فقط استبعاد الرأس الأخير، فتكون المساهمة \(1\).
إذًا المكوّن الدوري يساهم بـ \(7\)، ويكون الناتج الكلي
$$5\cdot 7=35,$$
وهو نفس مقدار الفحص الصغير الموجود في التنفيذ.
تبدأ تطبيقات C++ وPython وJava ببناء جدول الانتقال لجميع الحالات \(2^n\)، وبالتوازي تبني قوائم الأسلاف لكل حالة. بعد ذلك تستخرج جميع الدورات الموجهة باستعمال مرور ثلاثي الألوان: رأس غير مزور، رأس موجود على المسار الحالي، ورأس تمت معالجته بالكامل. وعندما يعود المرور إلى رأس ما زال نشطًا على المسار، يكون جزء الدورة قد تحدد.
بعد معرفة الدورات، تُقيَّم كل شجرة داخلة مرة واحدة فقط بترتيب لاحق. ثم تُدمج هذه القيم في وزنين لكل رأس على الدورة، وبعدها تُنفّذ DP خاصة بالدورة مع حالتي الحد المذكورتين. في النهاية تُضرب مساهمات جميع المكوّنات بترديد \(1001001011\).
إذا كان \(N=2^n\)، فإن بناء جدول الانتقال والرسم العكسي يحتاج إلى \(O(N)\) زمنًا و\(O(N)\) ذاكرة. كما أن اكتشاف الدورات نفسه يزور كل رأس عددًا ثابتًا من المرات، فيبقى \(O(N)\). ثم إن DP على الأشجار والدورة تعالج كل رأس وكل حافة مرة إضافية فقط. لذلك يكون التعقيد الكلي
$$O(N)=O(2^n),$$
أما استهلاك الذاكرة فهو
$$O(N)=O(2^n).$$
وبالنسبة إلى المدخل الفعلي \(n=20\)، فهذا يعني معالجة خطية لـ \(1{,}048{,}576\) حالة.