The problem asks for the number of proper 3-colorings of a triangular grid: every vertex receives one of three colors, and any two adjacent vertices must have different colors. In the actual instance there are \(n=8\) rows, row \(r\) contains \(2r+1\) vertices, and the whole graph therefore has \(1+3+\cdots+15=8^2=64\) vertices.
A brute-force search over \(3^{64}\) assignments is completely unrealistic. The successful idea is to sweep through the triangle row by row and keep only the interface information that can still influence the next row.
The triangular shape is the reason a compact dynamic program exists. Once the rows are written in the right way, the dependence between consecutive rows becomes digitwise and can be aggregated efficiently.
Number the rows from top to bottom by \(r=0,1,\dots,n-1\). A coloring of row \(r\) can be written as
$$v=(x_0,x_1,\dots,x_{2r}).$$
Inside one row, consecutive vertices are adjacent, so every legal row coloring must satisfy
$$x_i\ne x_{i+1}\qquad(0\le i\lt 2r).$$
Now compare two consecutive rows. If row \(r-1\) is \((a_0,a_1,\dots,a_{2r-2})\) and row \(r\) is \((b_0,b_1,\dots,b_{2r})\), then the only inter-row edges join \(a_{2j}\) to \(b_{2j+1}\) for \(j=0,1,\dots,r-1\). So the previous row influences the next row only through its even positions, and the new row is constrained only at its odd positions.
Let \(S_r\) be the set of all legal colorings of row \(r\). Because the first entry has 3 choices and each later entry has exactly 2 choices different from its left neighbor,
$$|S_r|=3\cdot 2^{2r}=3\cdot 4^r.$$
For a state \(v=(x_0,\dots,x_{2r})\in S_r\), split the row into its even-position and odd-position signatures:
$$E(v)=(x_0,x_2,\dots,x_{2r}),\qquad O(v)=(x_1,x_3,\dots,x_{2r-1}).$$
The even signature has length \(r+1\), while the odd signature has length \(r\). This split is not cosmetic: \(O(v)\) is the part that must agree with the previous row's restrictions, and \(E(v)\) is the part that remains exposed to the next row.
Let \(F_r(v)\) denote the number of proper colorings of the first \(r+1\) rows whose \(r\)-th row is exactly \(v\in S_r\). The base case is row \(0\): there are three one-vertex colorings, and each contributes 1.
If \(u\in S_{r-1}\) and \(v\in S_r\), then the two rows are compatible exactly when every even-position color of \(u\) differs from the touching odd-position color of \(v\):
$$E(u)_j\ne O(v)_j\qquad(j=0,1,\dots,r-1).$$
Therefore
$$F_r(v)=\sum_{\substack{u\in S_{r-1}\\ E(u)_j\ne O(v)_j\ \forall j}} F_{r-1}(u).$$
After the last row, the required count is simply
$$T_n=\sum_{v\in S_{n-1}} F_{n-1}(v).$$
The recurrence still sums over every full coloring of the previous row, but the compatibility test depends only on \(E(u)\). That means we can aggregate all previous rows with the same exposed even signature. For each \(e\in\{0,1,2\}^r\), define
$$A_{r-1}(e)=\sum_{\substack{u\in S_{r-1}\\ E(u)=e}} F_{r-1}(u).$$
Then the transition becomes
$$F_r(v)=\sum_{\substack{e\in\{0,1,2\}^r\\ e_j\ne O(v)_j\ \forall j}} A_{r-1}(e).$$
This is the central simplification. For a fixed odd signature \(O(v)\), each digit of \(e\) may be any of the two colors different from the required odd digit, so exactly \(2^r\) even signatures are compatible out of the full \(3^r\) signature space. The implementations exploit precisely this digitwise independence.
Consider the current row coloring
$$v=(0,1,2,0,1).$$
It is legal because neighboring entries are all different. Its odd signature is
$$O(v)=(1,0).$$
Any previous row of width 3 contributes only through its even signature \(e=(e_0,e_1)\), and compatibility requires
$$e_0\ne 1,\qquad e_1\ne 0.$$
So the only compatible even signatures are
$$e\in\{(0,1),(0,2),(2,1),(2,2)\}.$$
For this one row state we therefore have
$$F_2(v)=A_1(0,1)+A_1(0,2)+A_1(2,1)+A_1(2,2).$$
This small example shows why the transition naturally produces a \(2^r\) branching factor: each odd-position color forbids exactly one choice for the matching exposed digit from the previous row. As a whole-triangle sanity check, the 2-row triangle has \(3\cdot 2\cdot 2\cdot 2=24\) proper colorings.
The C++, Python, and Java implementations first generate every legal coloring of each row with a depth-first search that enforces \(x_i\ne x_{i+1}\). Each row state is then stored through its odd and even signatures. The C++ and Python implementations encode these signatures as base-3 integers, while the Java implementation derives compact string signatures from the same row states.
At the transition from row \(r-1\) to row \(r\), the implementations combine all previous counts that share the same exposed even signature. That converts many full row states into a much smaller table indexed by the \(3^r\) possible even signatures of length \(r\). Each current row then needs only the sum over those previous signatures that are digitwise different from its odd signature.
Many current row states have the same odd signature. The C++ and Python implementations memoize the compatible-interface sum for each required odd signature and obtain it by recursively enumerating the \(2^r\) admissible previous signatures. The Java implementation expresses the same recurrence more directly by scanning the aggregated previous signatures and testing digitwise compatibility. After the final row, all remaining counts are added. The C++ implementation also contains a brute-force cross-check for very small triangles, which independently verifies the recurrence.
Row \(r\) has \(3\cdot 4^r\) legal states, so the largest row in the actual problem, \(r=7\), has \(3\cdot 4^7=49{,}152\) states. This is far smaller than \(3^{64}\), but still large enough that a naive row-to-row all-pairs transition would be wasteful.
After interface compression, the transition from row \(r-1\) to row \(r\) lives in a signature space of size \(3^r\). In the optimized integer-coded versions, building the aggregated table costs \(O(4^r)\), and evaluating all distinct compatibility sums costs \(O(3^r2^r)=O(6^r)\). Memory during the sweep is dominated by the current and previous row tables together with an aggregation array of size \(3^r\). Since the problem stops at \(r=7\), the method runs comfortably and computes the exact count without approximation.
Gesucht ist die Anzahl zulässiger 3-Färbungen des dreieckigen Gitters aus der Aufgabe: Jeder Knoten erhält eine von drei Farben, und benachbarte Knoten müssen verschiedene Farben besitzen. Im eigentlichen Fall gibt es \(n=8\) Zeilen; Zeile \(r\) enthält \(2r+1\) Knoten, also hat das gesamte Gitter \(1+3+\cdots+15=8^2=64\) Knoten.
Eine brute-force Suche über \(3^{64}\) Belegungen ist ausgeschlossen. Die Lösung verarbeitet das Dreieck stattdessen zeilenweise und speichert nur die Randinformation, die spätere Zeilen überhaupt noch beeinflussen kann.
Die Dreiecksstruktur macht eine kompakte dynamische Programmierung möglich. Sobald man die Zeilen passend beschreibt, wird die Abhängigkeit zwischen zwei aufeinanderfolgenden Zeilen zu einer ziffernweisen Verträglichkeitsbedingung.
Nummeriere die Zeilen von oben nach unten mit \(r=0,1,\dots,n-1\). Eine Färbung der Zeile \(r\) schreiben wir als
$$v=(x_0,x_1,\dots,x_{2r}).$$
Innerhalb einer Zeile sind aufeinanderfolgende Knoten benachbart, also muss jede zulässige Zeilenfärbung die Bedingung
$$x_i\ne x_{i+1}\qquad(0\le i\lt 2r)$$
erfüllen. Vergleiche nun zwei benachbarte Zeilen. Ist Zeile \(r-1\) gleich \((a_0,a_1,\dots,a_{2r-2})\) und Zeile \(r\) gleich \((b_0,b_1,\dots,b_{2r})\), dann verbinden die einzigen Kanten zwischen den Zeilen \(a_{2j}\) mit \(b_{2j+1}\) für \(j=0,1,\dots,r-1\). Die vorige Zeile wirkt also nur über ihre geraden Positionen auf die nächste Zeile, und die neue Zeile wird nur an ihren ungeraden Positionen eingeschränkt.
Sei \(S_r\) die Menge aller zulässigen Färbungen der Zeile \(r\). Da der erste Eintrag 3 Möglichkeiten besitzt und jeder weitere Eintrag genau 2 Möglichkeiten hat, die von seinem linken Nachbarn verschieden sind, gilt
$$|S_r|=3\cdot 2^{2r}=3\cdot 4^r.$$
Für einen Zustand \(v=(x_0,\dots,x_{2r})\in S_r\) trennen wir gerade und ungerade Positionen:
$$E(v)=(x_0,x_2,\dots,x_{2r}),\qquad O(v)=(x_1,x_3,\dots,x_{2r-1}).$$
Die gerade Signatur hat Länge \(r+1\), die ungerade Signatur Länge \(r\). Genau diese Zerlegung ist entscheidend: \(O(v)\) ist der Teil der aktuellen Zeile, der zur vorherigen Zeile kompatibel sein muss, während \(E(v)\) der Teil ist, der in die nächste Zeile hineinragt.
Sei \(F_r(v)\) die Anzahl zulässiger Färbungen der ersten \(r+1\) Zeilen, bei denen die \(r\)-te Zeile genau \(v\in S_r\) ist. Der Anfang ist Zeile \(0\): Dort gibt es drei Ein-Knoten-Färbungen, und jede trägt 1 bei.
Für \(u\in S_{r-1}\) und \(v\in S_r\) sind beide Zeilen genau dann kompatibel, wenn jede gerade Position der vorherigen Zeile von der berührenden ungeraden Position der aktuellen Zeile verschieden ist:
$$E(u)_j\ne O(v)_j\qquad(j=0,1,\dots,r-1).$$
Daher gilt
$$F_r(v)=\sum_{\substack{u\in S_{r-1}\\ E(u)_j\ne O(v)_j\ \forall j}} F_{r-1}(u).$$
Nach der letzten Zeile ist die gesuchte Anzahl einfach
$$T_n=\sum_{v\in S_{n-1}} F_{n-1}(v).$$
Die Rekurrenz summiert noch über alle vollständigen Färbungen der vorherigen Zeile, aber der Kompatibilitätstest hängt nur von \(E(u)\) ab. Deshalb können alle vorherigen Zustände mit derselben geraden Signatur zusammengefasst werden. Für \(e\in\{0,1,2\}^r\) definieren wir
$$A_{r-1}(e)=\sum_{\substack{u\in S_{r-1}\\ E(u)=e}} F_{r-1}(u).$$
Dann wird der Übergang zu
$$F_r(v)=\sum_{\substack{e\in\{0,1,2\}^r\\ e_j\ne O(v)_j\ \forall j}} A_{r-1}(e).$$
Das ist die eigentliche Vereinfachung. Für eine feste ungerade Signatur \(O(v)\) darf jede Ziffer von \(e\) eine der beiden Farben annehmen, die von der geforderten ungeraden Ziffer verschieden sind. Unter den insgesamt \(3^r\) Signaturen bleiben also genau \(2^r\) kompatible Signaturen übrig. Genau diese Ziffern-Unabhängigkeit nutzt der Code aus.
Betrachte die aktuelle Zeilenfärbung
$$v=(0,1,2,0,1).$$
Sie ist zulässig, weil benachbarte Einträge immer verschieden sind. Ihre ungerade Signatur lautet
$$O(v)=(1,0).$$
Jede vorherige Zeile der Breite 3 wirkt nur über ihre gerade Signatur \(e=(e_0,e_1)\), und Kompatibilität bedeutet
$$e_0\ne 1,\qquad e_1\ne 0.$$
Also kommen nur die Signaturen
$$e\in\{(0,1),(0,2),(2,1),(2,2)\}$$
in Frage. Für diesen einzelnen Zustand gilt damit
$$F_2(v)=A_1(0,1)+A_1(0,2)+A_1(2,1)+A_1(2,2).$$
Das Beispiel zeigt unmittelbar, warum der Übergang einen Faktor \(2^r\) hat: Jede ungerade Ziffer verbietet genau eine Farbe für die passende exponierte Ziffer der vorherigen Zeile. Als globaler Plausibilitätscheck besitzt das Dreieck mit 2 Zeilen insgesamt \(3\cdot 2\cdot 2\cdot 2=24\) zulässige Färbungen.
Die Implementierungen in C++, Python und Java erzeugen zunächst jede zulässige Färbung jeder Zeile mit einer Tiefensuche, die die Bedingung \(x_i\ne x_{i+1}\) direkt erzwingt. Jeder Zeilenzustand wird anschließend durch seine gerade und ungerade Signatur beschrieben. C++ und Python kodieren diese Signaturen als Zahlen zur Basis 3; Java gewinnt aus denselben Zuständen kompakte Zeichenketten-Signaturen.
Beim Übergang von Zeile \(r-1\) zu Zeile \(r\) fassen die Implementierungen alle bisherigen Zählwerte mit derselben geraden Signatur zusammen. Dadurch werden viele vollständige Zeilenzustände zu einer deutlich kleineren Tabelle reduziert, die nur durch die \(3^r\) möglichen geraden Signaturen der Länge \(r\) indiziert ist. Jede aktuelle Zeile benötigt dann nur noch die Summe über diejenigen früheren Signaturen, die ziffernweise von ihrer ungeraden Signatur verschieden sind.
Viele aktuelle Zeilenzustände besitzen dieselbe ungerade Signatur. Die C++- und Python-Versionen speichern deshalb die kompatible Interfacesumme für jede benötigte ungerade Signatur zwischen und erzeugen sie durch rekursive Enumeration der \(2^r\) zulässigen vorherigen Signaturen. Die Java-Version formuliert dieselbe Rekurrenz direkter, indem sie die aggregierten vorherigen Signaturen durchläuft und ziffernweise auf Verträglichkeit prüft. Nach der letzten Zeile werden alle verbleibenden Zählwerte addiert. Die C++-Implementierung enthält zusätzlich eine brute-force Kontrolle für sehr kleine Dreiecke und überprüft damit die Rekurrenz unabhängig.
Zeile \(r\) besitzt \(3\cdot 4^r\) zulässige Zustände. Im realen Fall ist die größte Zeile \(r=7\), also \(3\cdot 4^7=49{,}152\) Zustände. Das ist viel kleiner als \(3^{64}\), aber immer noch groß genug, dass ein naiver All-zu-All-Übergang zwischen zwei Zeilen unnötig teuer wäre.
Nach der Interface-Kompression lebt der Übergang von Zeile \(r-1\) zu Zeile \(r\) nur noch in einem Signaturraum der Größe \(3^r\). In den optimierten Ganzzahl-Implementierungen kostet das Aufbauen der aggregierten Tabelle \(O(4^r)\), und das Auswerten aller verschiedenen Kompatibilitätssummen kostet \(O(3^r2^r)=O(6^r)\). Der Speicherbedarf während des Durchlaufs wird von den Tabellen der aktuellen und vorherigen Zeile sowie einem Aggregationsarray der Größe \(3^r\) bestimmt. Da das Problem bei \(r=7\) endet, läuft die Methode bequem und liefert den exakten Wert ohne Approximation.
Bu problemde üçgensel bir ızgaranın düzgün 3-renklemelerinin sayısı istenir: her düğüm üç renkten biriyle boyanır ve ortak kenarla bağlı iki düğüm aynı renge sahip olamaz. Gerçek örnekte \(n=8\) satır vardır; \(r\). satır \(2r+1\) düğüm içerir ve toplam düğüm sayısı da \(1+3+\cdots+15=8^2=64\) olur.
\(3^{64}\) olası atamayı doğrudan denemek imkansızdır. İşe yarayan fikir, üçgeni satır satır ilerlemek ve gelecek satırları gerçekten etkileyebilecek sınır bilgisini tutmaktır.
Üçgen geometrisi burada çok sıkı bir dinamik programlama yapısı veriyor. Satırlar doğru biçimde yazıldığında, ardışık iki satır arasındaki bağ yalnızca basamak basamak eşitsizlik şartına indirgeniyor.
Satırları yukarıdan aşağıya \(r=0,1,\dots,n-1\) diye numaralayalım. \(r\). satırın bir renklemesi
$$v=(x_0,x_1,\dots,x_{2r})$$
şeklinde yazılsın. Aynı satır içinde ardışık düğümler komşu olduğundan, her geçerli satır renklemesi
$$x_i\ne x_{i+1}\qquad(0\le i\lt 2r)$$
koşulunu sağlamalıdır. Şimdi art arda iki satıra bakalım. \(r-1\). satır \((a_0,a_1,\dots,a_{2r-2})\), \(r\). satır ise \((b_0,b_1,\dots,b_{2r})\) olsun. Satırlar arasındaki tek kenarlar, \(a_{2j}\) ile \(b_{2j+1}\) düğümlerini \(j=0,1,\dots,r-1\) için bağlar. Demek ki bir önceki satır yalnızca çift indisli konumları üzerinden sonraki satırı etkiler; yeni satırda da sadece tek indisli konumlar önceki satır tarafından kısıtlanır.
\(S_r\), \(r\). satırın tüm geçerli renkleme kümesi olsun. İlk düğüm için 3 seçim vardır; sonraki her düğüm için de sol komşusundan farklı tam 2 renk kalır. Bu yüzden
$$|S_r|=3\cdot 2^{2r}=3\cdot 4^r.$$
\(v=(x_0,\dots,x_{2r})\in S_r\) için satırı çift ve tek konum imzalarına ayıralım:
$$E(v)=(x_0,x_2,\dots,x_{2r}),\qquad O(v)=(x_1,x_3,\dots,x_{2r-1}).$$
Çift konum imzasının uzunluğu \(r+1\), tek konum imzasının uzunluğu \(r\)'dir. Bu ayrım tamamen problemden gelir: \(O(v)\), önceki satırın dayattığı koşullarla uyuşması gereken parçadır; \(E(v)\) ise bir sonraki satıra taşınacak açık arayüzdür.
\(F_r(v)\), ilk \(r+1\) satırın geçerli renkleme sayısı olsun; burada \(r\). satır tam olarak \(v\in S_r\) durumundadır. Başlangıç durumu \(0\). satırdır: tek düğümlü üç farklı renkleme vardır ve her biri 1 katkı yapar.
\(u\in S_{r-1}\) ve \(v\in S_r\) için iki satırın uyumlu olması tam olarak şu koşula denktir:
$$E(u)_j\ne O(v)_j\qquad(j=0,1,\dots,r-1).$$
Dolayısıyla
$$F_r(v)=\sum_{\substack{u\in S_{r-1}\\ E(u)_j\ne O(v)_j\ \forall j}} F_{r-1}(u).$$
Son satıra gelindiğinde istenen sonuç
$$T_n=\sum_{v\in S_{n-1}} F_{n-1}(v)$$
olur.
Bu bağıntı hâlâ önceki satırın bütün tam durumları üzerinden toplama yapıyor, fakat uyumluluk testi yalnızca \(E(u)\)'ya bağlı. Bu yüzden aynı çift-konum imzasına sahip tüm önceki durumlar bir araya getirilebilir. \(e\in\{0,1,2\}^r\) için
$$A_{r-1}(e)=\sum_{\substack{u\in S_{r-1}\\ E(u)=e}} F_{r-1}(u)$$
tanımını yapalım. O zaman geçiş
$$F_r(v)=\sum_{\substack{e\in\{0,1,2\}^r\\ e_j\ne O(v)_j\ \forall j}} A_{r-1}(e)$$
şeklini alır. Asıl hız kazancı burada gelir. Sabit bir \(O(v)\) için, \(e\)'nin her basamağı istenen tek basamaktan farklı olan iki renkten birini seçebilir; yani toplam \(3^r\) imza arasından tam \(2^r\) tanesi uyumludur. Uygulamalar tam olarak bu basamak bağımsızlığını kullanır.
Şu anki satır renklemesini ele alalım:
$$v=(0,1,2,0,1).$$
Komşu terimler farklı olduğu için bu satır geçerlidir. Tek-konum imzası
$$O(v)=(1,0)$$
olur. Genişliği 3 olan önceki satır, yalnızca \(e=(e_0,e_1)\) çift-imzası üzerinden etkide bulunur ve uyumluluk
$$e_0\ne 1,\qquad e_1\ne 0$$
şartını ister. Bu nedenle uyumlu imzalar sadece
$$e\in\{(0,1),(0,2),(2,1),(2,2)\}$$
olabilir. Bu tek satır durumu için
$$F_2(v)=A_1(0,1)+A_1(0,2)+A_1(2,1)+A_1(2,2)$$
elde edilir. Bu küçük örnek, neden doğal olarak \(2^r\) dallanması çıktığını açıkça gösterir: tek-konum renginin her biri, eşleşen önceki basamak için tam bir rengi yasaklar. Tüm üçgen için basit bir kontrol olarak, 2 satırlı üçgende toplam düzgün renkleme sayısı \(3\cdot 2\cdot 2\cdot 2=24\)'tür.
C++, Python ve Java uygulamaları önce her satırın tüm geçerli renkleme durumlarını, \(x_i\ne x_{i+1}\) koşulunu doğrudan uygulayan bir derinlik öncelikli arama ile üretir. Her satır durumu daha sonra çift ve tek konum imzalarıyla temsil edilir. C++ ve Python sürümleri bu imzaları taban 3 sayılar olarak tutar; Java sürümü ise aynı durumlar üzerinden kısa dizgesel imzalar üretir.
\(r-1\). satırdan \(r\). satıra geçerken uygulamalar, önceki tüm sayıları aynı açık çift-imzaya göre toplar. Böylece çok sayıdaki tam satır durumu, uzunluğu \(r\) olan \(3^r\) olası çift-imza ile indekslenen daha küçük bir tabloya indirgenir. Bundan sonra her mevcut satırın ihtiyaç duyduğu şey, tek-imzasından basamak basamak farklı olan önceki imzaların toplamıdır.
Birçok mevcut satır aynı tek-imzayı paylaşır. C++ ve Python uygulamaları bu yüzden her gerekli tek-imza için uyumlu arayüz toplamını önbelleğe alır ve bunu \(2^r\) adet izinli önceki imzayı özyinelemeli biçimde gezerek hesaplar. Java uygulaması aynı bağıntıyı daha doğrudan yazar; toplulaştırılmış önceki imzaları dolaşıp basamak basamak uyumluluğu test eder. Son satırdan sonra elde kalan tüm sayılar toplanır. C++ sürümünde ayrıca çok küçük üçgenler için kaba kuvvetli bir çapraz kontrol bulunur; bu da DP bağıntısını bağımsız olarak doğrular.
\(r\). satırın \(3\cdot 4^r\) adet geçerli durumu vardır. Gerçek problemde en büyük satır \(r=7\) olduğundan bu sayı \(3\cdot 4^7=49{,}152\)'dir. Bu, \(3^{64}\)'e kıyasla çok küçüktür; yine de satırlar arasında bütün çiftleri deneyen naif bir geçiş için gereksiz derecede büyüktür.
Arayüz sıkıştırmasından sonra \(r-1\). satırdan \(r\). satıra geçiş yalnızca boyutu \(3^r\) olan bir imza uzayında yaşar. Tamsayı tabanlı optimize sürümlerde toplulaştırılmış tabloyu kurmak \(O(4^r)\), farklı tüm uyumluluk toplamlarını hesaplamak ise \(O(3^r2^r)=O(6^r)\) maliyetlidir. Geçiş sırasında bellek kullanımı, mevcut ve önceki satır tabloları ile boyutu \(3^r\) olan bir toplulaştırma dizisi tarafından belirlenir. Problem yalnızca \(r=7\)'ye kadar gittiği için yöntem rahat çalışır ve sonucu yaklaşık değil tam olarak üretir.
Se pide contar las 3-coloraciones propias de la malla triangular del enunciado: cada vértice recibe uno de tres colores y dos vértices unidos por una arista deben tener colores distintos. En la instancia real hay \(n=8\) filas; la fila \(r\) contiene \(2r+1\) vértices, así que el grafo completo tiene \(1+3+\cdots+15=8^2=64\) vértices.
Un barrido directo sobre \(3^{64}\) asignaciones es imposible. La idea correcta es recorrer el triángulo fila por fila y conservar solo la información de frontera que todavía puede afectar a la fila siguiente.
La geometría triangular es precisamente lo que permite una programación dinámica compacta. Si las filas se describen de la forma adecuada, la dependencia entre dos filas consecutivas se reduce a una condición de desigualdad dígito a dígito.
Numeremos las filas de arriba abajo como \(r=0,1,\dots,n-1\). Una coloración de la fila \(r\) se escribe como
$$v=(x_0,x_1,\dots,x_{2r}).$$
Dentro de una fila, vértices consecutivos son adyacentes, así que toda coloración válida debe cumplir
$$x_i\ne x_{i+1}\qquad(0\le i\lt 2r).$$
Ahora comparemos dos filas consecutivas. Si la fila \(r-1\) es \((a_0,a_1,\dots,a_{2r-2})\) y la fila \(r\) es \((b_0,b_1,\dots,b_{2r})\), entonces las únicas aristas entre ambas filas unen \(a_{2j}\) con \(b_{2j+1}\) para \(j=0,1,\dots,r-1\). Eso significa que la fila anterior influye en la siguiente solo a través de sus posiciones pares, y la nueva fila queda restringida solo en sus posiciones impares.
Sea \(S_r\) el conjunto de todas las coloraciones válidas de la fila \(r\). Como el primer vértice tiene 3 opciones y cada vértice posterior tiene exactamente 2 opciones distintas de su vecino izquierdo,
$$|S_r|=3\cdot 2^{2r}=3\cdot 4^r.$$
Para un estado \(v=(x_0,\dots,x_{2r})\in S_r\), separamos la fila en firmas de posiciones pares e impares:
$$E(v)=(x_0,x_2,\dots,x_{2r}),\qquad O(v)=(x_1,x_3,\dots,x_{2r-1}).$$
La firma par tiene longitud \(r+1\), mientras que la firma impar tiene longitud \(r\). Esta separación refleja exactamente el problema: \(O(v)\) es la parte que debe ser compatible con la fila anterior, y \(E(v)\) es la parte que queda expuesta hacia la fila siguiente.
Sea \(F_r(v)\) el número de coloraciones válidas de las primeras \(r+1\) filas cuya fila \(r\) es exactamente \(v\in S_r\). El caso base es la fila \(0\): hay tres coloraciones de un solo vértice y cada una aporta 1.
Si \(u\in S_{r-1}\) y \(v\in S_r\), ambas filas son compatibles exactamente cuando cada color de posición par en \(u\) difiere del color impar que toca en \(v\):
$$E(u)_j\ne O(v)_j\qquad(j=0,1,\dots,r-1).$$
Por tanto,
$$F_r(v)=\sum_{\substack{u\in S_{r-1}\\ E(u)_j\ne O(v)_j\ \forall j}} F_{r-1}(u).$$
Después de la última fila, la cantidad pedida es
$$T_n=\sum_{v\in S_{n-1}} F_{n-1}(v).$$
La recurrencia todavía suma sobre todas las coloraciones completas de la fila anterior, pero la compatibilidad solo depende de \(E(u)\). Por eso se pueden agrupar todas las filas anteriores que compartan la misma firma par. Para cada \(e\in\{0,1,2\}^r\), definimos
$$A_{r-1}(e)=\sum_{\substack{u\in S_{r-1}\\ E(u)=e}} F_{r-1}(u).$$
Entonces la transición pasa a ser
$$F_r(v)=\sum_{\substack{e\in\{0,1,2\}^r\\ e_j\ne O(v)_j\ \forall j}} A_{r-1}(e).$$
Aquí está la simplificación clave. Para una firma impar fija \(O(v)\), cada dígito de \(e\) puede elegirse entre los dos colores distintos del dígito impar correspondiente, así que entre las \(3^r\) firmas posibles sobreviven exactamente \(2^r\) firmas compatibles. La implementación explota justo esa independencia por coordenadas.
Consideremos la coloración de fila
$$v=(0,1,2,0,1).$$
Es válida porque las entradas vecinas siempre son distintas. Su firma impar es
$$O(v)=(1,0).$$
Cualquier fila anterior de anchura 3 aporta solo mediante su firma par \(e=(e_0,e_1)\), y la compatibilidad exige
$$e_0\ne 1,\qquad e_1\ne 0.$$
Por lo tanto, las únicas firmas pares compatibles son
$$e\in\{(0,1),(0,2),(2,1),(2,2)\}.$$
Para este único estado de fila se obtiene
$$F_2(v)=A_1(0,1)+A_1(0,2)+A_1(2,1)+A_1(2,2).$$
Este ejemplo muestra exactamente por qué aparece un factor \(2^r\): cada color en posición impar prohíbe un único color para el dígito expuesto correspondiente de la fila anterior. Como comprobación global, el triángulo de 2 filas tiene \(3\cdot 2\cdot 2\cdot 2=24\) coloraciones propias.
Las implementaciones en C++, Python y Java generan primero todas las coloraciones válidas de cada fila mediante una búsqueda en profundidad que impone \(x_i\ne x_{i+1}\). Después, cada estado de fila se representa por sus firmas par e impar. Las versiones de C++ y Python codifican esas firmas como enteros en base 3; la versión de Java deriva firmas compactas en forma de cadenas a partir de los mismos estados.
En la transición de la fila \(r-1\) a la fila \(r\), las implementaciones reúnen todos los conteos anteriores que comparten la misma firma par expuesta. Eso convierte muchos estados completos de fila en una tabla mucho más pequeña, indexada solo por las \(3^r\) firmas pares posibles de longitud \(r\). Cada fila actual necesita entonces únicamente la suma de aquellas firmas anteriores que difieren dígito a dígito de su firma impar.
Muchos estados actuales comparten la misma firma impar. Las implementaciones en C++ y Python memorizan por ello la suma compatible para cada firma impar requerida y la obtienen enumerando recursivamente las \(2^r\) firmas anteriores admisibles. La implementación en Java expresa la misma recurrencia de forma más directa, recorriendo las firmas anteriores ya agregadas y comprobando la compatibilidad dígito a dígito. Tras la última fila, se suman todos los conteos restantes. La implementación en C++ también incluye una verificación por fuerza bruta para triángulos muy pequeños, que sirve como comprobación independiente de la recurrencia.
La fila \(r\) tiene \(3\cdot 4^r\) estados legales. En el caso real, la fila más grande es \(r=7\), así que aparecen \(3\cdot 4^7=49{,}152\) estados. Eso es muchísimo menor que \(3^{64}\), pero sigue siendo suficientemente grande como para que un tránsito ingenuo de todos contra todos entre filas resulte innecesariamente caro.
Después de comprimir la interfaz, la transición entre la fila \(r-1\) y la fila \(r\) vive solo en un espacio de firmas de tamaño \(3^r\). En las versiones optimizadas con enteros, construir la tabla agregada cuesta \(O(4^r)\), y evaluar todas las sumas de compatibilidad distintas cuesta \(O(3^r2^r)=O(6^r)\). La memoria durante el barrido está dominada por las tablas de la fila actual y la anterior, más un arreglo agregado de tamaño \(3^r\). Como el problema termina en \(r=7\), el método es sobradamente práctico y calcula el valor exacto.
这道题要求统计题目中那个三角形网格的合法三染色数：每个顶点从三种颜色里选一种，任何由边相连的两个顶点都不能同色。实际要求的是 \(n=8\) 行的情形，第 \(r\) 行有 \(2r+1\) 个顶点，因此整个图一共有 \(1+3+\cdots+15=8^2=64\) 个顶点。
如果直接在 \(3^{64}\) 个颜色赋值上暴力搜索，规模完全不可接受。真正可行的方法是按行推进，并且只保留那些仍然可能影响下一行的边界信息。
题目的关键不只是“用动态规划”，而是三角形的连边方式恰好允许一种非常紧凑的按行状态压缩。只要把一行拆成合适的两部分，相邻两行之间的约束就会变成逐位的不等关系。
把行从上到下编号为 \(r=0,1,\dots,n-1\)。第 \(r\) 行的一种着色记为
$$v=(x_0,x_1,\dots,x_{2r}).$$
同一行里相邻顶点之间有边，所以合法行状态必须满足
$$x_i\ne x_{i+1}\qquad(0\le i\lt 2r).$$
再看相邻两行。若第 \(r-1\) 行是 \((a_0,a_1,\dots,a_{2r-2})\)，第 \(r\) 行是 \((b_0,b_1,\dots,b_{2r})\)，那么两行之间唯一的连边是 \(a_{2j}\) 与 \(b_{2j+1}\)，其中 \(j=0,1,\dots,r-1\)。这条观察非常重要：前一行真正会影响下一行的，只有它的偶数位置；而当前行真正受到上一行约束的，只有它的奇数位置。
记 \(S_r\) 为第 \(r\) 行所有合法着色的集合。因为第一个顶点有 3 种选择，而之后每个顶点都只能从与左邻点不同的 2 种颜色里选，所以
$$|S_r|=3\cdot 2^{2r}=3\cdot 4^r.$$
对于任意 \(v=(x_0,\dots,x_{2r})\in S_r\)，把它拆成偶数位置与奇数位置两部分：
$$E(v)=(x_0,x_2,\dots,x_{2r}),\qquad O(v)=(x_1,x_3,\dots,x_{2r-1}).$$
其中偶数位置签名长度是 \(r+1\)，奇数位置签名长度是 \(r\)。这种拆分不是形式上的，而是正好对应题目的几何结构：\(O(v)\) 是当前行里必须与上一行相容的部分，\(E(v)\) 则是当前行留给下一行的“暴露边界”。
设 \(F_r(v)\) 表示前 \(r+1\) 行已经合法染色，并且第 \(r\) 行恰好等于 \(v\in S_r\) 的方案数。初始行 \(r=0\) 很简单：只有一个顶点，共 3 种颜色，每种都贡献 1。
如果 \(u\in S_{r-1}\)、\(v\in S_r\)，那么两行兼容当且仅当前一行偶数位置的颜色，与当前行接触到的奇数位置颜色逐位不同：
$$E(u)_j\ne O(v)_j\qquad(j=0,1,\dots,r-1).$$
因此递推式是
$$F_r(v)=\sum_{\substack{u\in S_{r-1}\\ E(u)_j\ne O(v)_j\ \forall j}} F_{r-1}(u).$$
最后一行处理完以后，答案就是
$$T_n=\sum_{v\in S_{n-1}} F_{n-1}(v).$$
上面的递推仍然对前一行的所有完整状态求和，但兼容性判断其实只依赖于 \(E(u)\)，不依赖于前一行的奇数位置。于是可以把所有拥有同一偶数位置签名的前一行状态先合并。对每个 \(e\in\{0,1,2\}^r\)，定义
$$A_{r-1}(e)=\sum_{\substack{u\in S_{r-1}\\ E(u)=e}} F_{r-1}(u).$$
那么转移就化为
$$F_r(v)=\sum_{\substack{e\in\{0,1,2\}^r\\ e_j\ne O(v)_j\ \forall j}} A_{r-1}(e).$$
这一步就是整道题的核心压缩。对固定的奇数位置签名 \(O(v)\) 来说，\(e\) 的每一位都只能从“与该奇数位不同”的 2 种颜色里选，因此在全部 \(3^r\) 个候选签名中，恰好只有 \(2^r\) 个是兼容的。实现程序利用的就是这种按位独立性。
考虑当前这一行的着色
$$v=(0,1,2,0,1).$$
它显然是合法的，因为相邻位置颜色都不同。它的奇数位置签名为
$$O(v)=(1,0).$$
宽度为 3 的前一行只通过它的偶数位置签名 \(e=(e_0,e_1)\) 参与转移，而兼容条件是
$$e_0\ne 1,\qquad e_1\ne 0.$$
因此可行的偶数位置签名只有
$$e\in\{(0,1),(0,2),(2,1),(2,2)\}.$$
于是这个当前状态的转移值就是
$$F_2(v)=A_1(0,1)+A_1(0,2)+A_1(2,1)+A_1(2,2).$$
这个例子准确展示了为什么每一步会自然地产生 \(2^r\) 个兼容接口：当前行的每一个奇数位都只排除上一行对应接口位的一个颜色。顺便做一个整图检验，只有 2 行的三角形总共有 \(3\cdot 2\cdot 2\cdot 2=24\) 种合法三染色。
C++、Python 和 Java 三个实现都会先用深度优先生成法枚举每一行所有满足 \(x_i\ne x_{i+1}\) 的合法着色。之后，每个行状态都被表示成奇数位置签名和偶数位置签名。C++ 与 Python 用三进制整数编码这些签名；Java 则基于相同的行状态构造紧凑的字符串签名。
从第 \(r-1\) 行转到第 \(r\) 行时，实现会先把所有上一行方案数按“暴露出来的偶数位置签名”聚合。这样，大量完整行状态就被压缩成一个只含 \(3^r\) 个可能签名的较小表。对于当前任意一行，只需要查出那些与它的奇数位置签名逐位不同的上一行接口签名之和。
很多当前行状态共享同一个奇数位置签名。C++ 和 Python 的实现会因此把“某个奇数签名所需的兼容总和”记忆化，并通过递归枚举那 \(2^r\) 个允许的上一行签名来计算它。Java 的实现写法更直接：它遍历已经聚合好的上一行签名并逐位检查兼容性。最后一行处理完以后，把剩下的计数全部相加即可。C++ 实现还带有一个很小规模的暴力校验，用来独立验证递推本身没有问题。
第 \(r\) 行有 \(3\cdot 4^r\) 个合法状态。在实际题目里，最大的是 \(r=7\) 这一行，也就是 \(3\cdot 4^7=49{,}152\) 个状态。这个规模远小于 \(3^{64}\)，但如果仍然对相邻两行做朴素的全对全转移，开销依然不必要地大。
压缩接口以后，从第 \(r-1\) 行到第 \(r\) 行的转移只发生在大小为 \(3^r\) 的签名空间里。对使用整数签名的优化版本来说，建立聚合表需要 \(O(4^r)\)，而计算所有不同兼容和需要 \(O(3^r2^r)=O(6^r)\)。运行中的内存主要由当前行和上一行的状态表，以及一个大小为 \(3^r\) 的聚合数组构成。由于本题只做到 \(r=7\)，所以这一方法不仅可行，而且是精确计算，不涉及任何近似。
Нужно посчитать число правильных 3-раскрасок треугольной решетки из условия: каждая вершина получает один из трех цветов, а любые две соседние вершины обязаны иметь разные цвета. В реальной постановке \(n=8\) строк; строка с номером \(r\) содержит \(2r+1\) вершин, поэтому весь граф имеет \(1+3+\cdots+15=8^2=64\) вершины.
Полный перебор \(3^{64}\) раскрасок невозможен. Рабочее решение идет по строкам и сохраняет только ту граничную информацию, которая еще может повлиять на следующую строку.
Суть здесь не просто в динамике, а в том, что структура треугольной решетки позволяет очень компактно сжать состояние. Если разложить строку на правильные компоненты, зависимость между соседними строками станет покоординатным условием неравенства.
Пронумеруем строки сверху вниз: \(r=0,1,\dots,n-1\). Раскраску строки \(r\) запишем как
$$v=(x_0,x_1,\dots,x_{2r}).$$
Внутри одной строки соседние вершины соединены ребрами, поэтому любая допустимая раскраска строки должна удовлетворять условию
$$x_i\ne x_{i+1}\qquad(0\le i\lt 2r).$$
Теперь рассмотрим две соседние строки. Пусть строка \(r-1\) равна \((a_0,a_1,\dots,a_{2r-2})\), а строка \(r\) равна \((b_0,b_1,\dots,b_{2r})\). Тогда единственные ребра между этими строками соединяют \(a_{2j}\) с \(b_{2j+1}\) для \(j=0,1,\dots,r-1\). Значит, предыдущая строка влияет на следующую только через свои четные позиции, а новая строка ограничивается предыдущей только в нечетных позициях.
Обозначим через \(S_r\) множество всех допустимых раскрасок строки \(r\). Первый элемент имеет 3 варианта, а каждый следующий элемент имеет ровно 2 варианта, отличных от цвета слева, поэтому
$$|S_r|=3\cdot 2^{2r}=3\cdot 4^r.$$
Для состояния \(v=(x_0,\dots,x_{2r})\in S_r\) выделим четную и нечетную сигнатуры:
$$E(v)=(x_0,x_2,\dots,x_{2r}),\qquad O(v)=(x_1,x_3,\dots,x_{2r-1}).$$
Четная сигнатура имеет длину \(r+1\), нечетная сигнатура - длину \(r\). Это разбиение полностью соответствует геометрии задачи: \(O(v)\) - часть текущей строки, которая должна быть совместима с предыдущей, а \(E(v)\) - часть, которая остается открытой для следующего шага.
Пусть \(F_r(v)\) обозначает число правильных раскрасок первых \(r+1\) строк, у которых строка \(r\) в точности равна \(v\in S_r\). База проста: для строки \(0\) есть три одноэлементные раскраски, каждая дает вклад 1.
Если \(u\in S_{r-1}\) и \(v\in S_r\), то строки совместимы тогда и только тогда, когда каждый цвет в четной позиции строки \(u\) отличается от соприкасающегося нечетного цвета в строке \(v\):
$$E(u)_j\ne O(v)_j\qquad(j=0,1,\dots,r-1).$$
Следовательно,
$$F_r(v)=\sum_{\substack{u\in S_{r-1}\\ E(u)_j\ne O(v)_j\ \forall j}} F_{r-1}(u).$$
После обработки последней строки ответ равен
$$T_n=\sum_{v\in S_{n-1}} F_{n-1}(v).$$
Формула выше все еще суммирует по всем полным состояниям предыдущей строки, но проверка совместимости зависит только от \(E(u)\). Поэтому все предыдущие состояния с одной и той же четной сигнатурой можно объединить. Для каждого \(e\in\{0,1,2\}^r\) зададим
$$A_{r-1}(e)=\sum_{\substack{u\in S_{r-1}\\ E(u)=e}} F_{r-1}(u).$$
Тогда переход принимает вид
$$F_r(v)=\sum_{\substack{e\in\{0,1,2\}^r\\ e_j\ne O(v)_j\ \forall j}} A_{r-1}(e).$$
Именно здесь происходит главная экономия. Для фиксированной нечетной сигнатуры \(O(v)\) каждая цифра в \(e\) может быть выбрана двумя способами, отличными от соответствующей нечетной цифры. Поэтому среди всех \(3^r\) сигнатур совместимыми оказываются ровно \(2^r\). На этой покоординатной независимости и построен алгоритм.
Рассмотрим текущую раскраску строки
$$v=(0,1,2,0,1).$$
Она допустима, потому что любые соседние элементы различны. Ее нечетная сигнатура равна
$$O(v)=(1,0).$$
Предыдущая строка ширины 3 влияет только через свою четную сигнатуру \(e=(e_0,e_1)\), а совместимость требует
$$e_0\ne 1,\qquad e_1\ne 0.$$
Значит, возможны только сигнатуры
$$e\in\{(0,1),(0,2),(2,1),(2,2)\}.$$
Для этого конкретного состояния строки получаем
$$F_2(v)=A_1(0,1)+A_1(0,2)+A_1(2,1)+A_1(2,2).$$
Пример наглядно показывает происхождение множителя \(2^r\): каждая нечетная позиция запрещает ровно один цвет в соответствующей открытой позиции предыдущей строки. В качестве общей проверки можно заметить, что треугольник из 2 строк имеет \(3\cdot 2\cdot 2\cdot 2=24\) правильные раскраски.
Реализации на C++, Python и Java сначала перечисляют все допустимые раскраски каждой строки с помощью поиска в глубину, который сразу навязывает условие \(x_i\ne x_{i+1}\). Затем каждое состояние строки представляется через четную и нечетную сигнатуры. В C++ и Python эти сигнатуры кодируются целыми числами в троичной системе, а Java строит по тем же состояниям компактные строковые сигнатуры.
При переходе от строки \(r-1\) к строке \(r\) реализации сначала объединяют все прежние количества по одинаковой открытой четной сигнатуре. Тем самым множество полных состояний строки заменяется гораздо меньшей таблицей, индексированной лишь \(3^r\) возможными четными сигнатурами длины \(r\). После этого каждой текущей строке нужна только сумма по тем прежним сигнатурам, которые покоординатно отличаются от ее нечетной сигнатуры.
Многие текущие состояния строки имеют одну и ту же нечетную сигнатуру. Поэтому версии на C++ и Python запоминают сумму по совместимому интерфейсу для каждой нужной нечетной сигнатуры и вычисляют ее рекурсивным перебором \(2^r\) допустимых предыдущих сигнатур. Версия на Java записывает ту же рекурсию более прямо, проходя по уже агрегированным предыдущим сигнатурам и проверяя совместимость поразрядно. После последней строки все оставшиеся количества суммируются. В реализации на C++ также есть переборная проверка для совсем маленьких треугольников, которая независимо подтверждает корректность рекуррентной схемы.
Строка \(r\) имеет \(3\cdot 4^r\) допустимых состояний. В реальной задаче максимальна строка \(r=7\), то есть \(3\cdot 4^7=49{,}152\) состояний. Это несопоставимо меньше, чем \(3^{64}\), но для наивного перехода “каждое к каждому” между соседними строками все равно избыточно.
После сжатия интерфейса переход от строки \(r-1\) к строке \(r\) живет в пространстве сигнатур размера \(3^r\). В оптимизированных версиях с целочисленными кодами построение агрегированной таблицы стоит \(O(4^r)\), а вычисление всех различных сумм совместимости стоит \(O(3^r2^r)=O(6^r)\). Память во время прохода определяется таблицами текущей и предыдущей строк, а также агрегирующим массивом размера \(3^r\). Поскольку здесь нужно дойти лишь до \(r=7\), метод работает быстро и дает точный ответ.
المطلوب هو عدّ جميع التلوينات الصحيحة بثلاثة ألوان للشبكة المثلثية في المسألة: كل رأس يأخذ واحدًا من ثلاثة ألوان، وأي رأسين متجاورين يجب أن يختلف لونهما. في الحالة الفعلية لدينا \(n=8\) صفوف، والصف رقم \(r\) يحتوي على \(2r+1\) رأسًا، ولذلك يضم الشكل كاملًا \(1+3+\cdots+15=8^2=64\) رأسًا.
التعداد المباشر لكل الإسنادات الممكنة وعددها \(3^{64}\) غير عملي تمامًا. الفكرة الصحيحة هي المرور على المثلث صفًا بعد صف، والاحتفاظ فقط بمعلومة الحدّ الفاصل التي يمكن أن تؤثر في الصف التالي.
جوهر الحل هو أن شكل الشبكة المثلثية يسمح بضغط الحالة بطريقة دقيقة جدًا. إذا كُتبت الصفوف بالشكل المناسب، فإن علاقة التوافق بين صفين متتاليين تتحول إلى شرط اختلاف رقمي خانة بخانة.
لنرقم الصفوف من الأعلى إلى الأسفل بالصيغة \(r=0,1,\dots,n-1\). تلوين الصف رقم \(r\) نكتبه على الصورة
$$v=(x_0,x_1,\dots,x_{2r}).$$
داخل الصف الواحد، كل رأسين متتاليين متجاوران، ولذلك يجب أن يحقق أي تلوين قانوني الشرط
$$x_i\ne x_{i+1}\qquad(0\le i\lt 2r).$$
والآن لننظر إلى صفين متجاورين. إذا كان الصف \(r-1\) هو \((a_0,a_1,\dots,a_{2r-2})\) والصف \(r\) هو \((b_0,b_1,\dots,b_{2r})\)، فإن الحواف الوحيدة بين الصفين تصل \(a_{2j}\) مع \(b_{2j+1}\) من أجل \(j=0,1,\dots,r-1\). معنى ذلك أن الصف السابق لا يؤثر في الصف التالي إلا عبر مواضعه الزوجية، وأن الصف الجديد لا يتقيد من الصف السابق إلا عند مواضعه الفردية.
لتكن \(S_r\) مجموعة كل التلوينات القانونية للصف \(r\). بما أن الرأس الأول يملك 3 اختيارات، وكل رأس لاحق يملك اختيارين فقط مختلفين عن جاره الأيسر، فإن
$$|S_r|=3\cdot 2^{2r}=3\cdot 4^r.$$
ولأي حالة \(v=(x_0,\dots,x_{2r})\in S_r\)، نقسم الصف إلى توقيع المواضع الزوجية وتوقيع المواضع الفردية:
$$E(v)=(x_0,x_2,\dots,x_{2r}),\qquad O(v)=(x_1,x_3,\dots,x_{2r-1}).$$
طول التوقيع الزوجي هو \(r+1\)، وطول التوقيع الفردي هو \(r\). هذا ليس مجرد ترميز شكلي؛ فـ \(O(v)\) هو الجزء من الصف الحالي الذي يجب أن يتوافق مع الصف السابق، أما \(E(v)\) فهو الجزء الذي يبقى مكشوفًا ليؤثر في الصف التالي.
لنرمز بـ \(F_r(v)\) إلى عدد التلوينات الصحيحة لأول \(r+1\) صفوف عندما يكون الصف \(r\) مساويًا تمامًا للحالة \(v\in S_r\). حالة البداية هي الصف \(0\): توجد ثلاث تلوينات أحادية الرأس، وكل واحدة تسهم بمقدار 1.
إذا كان \(u\in S_{r-1}\) و\(v\in S_r\)، فإن الصفين متوافقان إذا وفقط إذا كان كل لون في الموضع الزوجي من \(u\) مختلفًا عن اللون الفردي الملامس له في \(v\):
$$E(u)_j\ne O(v)_j\qquad(j=0,1,\dots,r-1).$$
إذًا نحصل على
$$F_r(v)=\sum_{\substack{u\in S_{r-1}\\ E(u)_j\ne O(v)_j\ \forall j}} F_{r-1}(u).$$
وبعد إنهاء الصف الأخير يكون العدد المطلوب هو
$$T_n=\sum_{v\in S_{n-1}} F_{n-1}(v).$$
العلاقة السابقة ما زالت تجمع على جميع الحالات الكاملة للصف السابق، لكن اختبار التوافق يعتمد فقط على \(E(u)\). لذلك يمكن جمع كل الحالات السابقة التي تشترك في التوقيع الزوجي نفسه. لكل \(e\in\{0,1,2\}^r\) نعرّف
$$A_{r-1}(e)=\sum_{\substack{u\in S_{r-1}\\ E(u)=e}} F_{r-1}(u).$$
وعندئذ يصبح الانتقال
$$F_r(v)=\sum_{\substack{e\in\{0,1,2\}^r\\ e_j\ne O(v)_j\ \forall j}} A_{r-1}(e).$$
وهنا تظهر القفزة الأساسية في الكفاءة. فإذا ثبتنا التوقيع الفردي \(O(v)\)، فإن كل خانة من \(e\) تستطيع اختيار أي واحد من اللونين المختلفين عن الخانة الفردية الموافقة. أي أن عدد التواقيع الزوجية المتوافقة هو بالضبط \(2^r\) من أصل \(3^r\) توقيعًا ممكنًا. التنفيذ البرمجي يستغل هذه الاستقلالية خانة بخانة بصورة مباشرة.
لنأخذ تلوين الصف الحالي
$$v=(0,1,2,0,1).$$
هذا الصف قانوني لأن كل عنصرين متجاورين مختلفان. وتوقيعه الفردي هو
$$O(v)=(1,0).$$
أي صف سابق بعرض 3 يساهم فقط عبر توقيعه الزوجي \(e=(e_0,e_1)\)، وشرط التوافق هو
$$e_0\ne 1,\qquad e_1\ne 0.$$
ومن ثم فإن التواقيع الزوجية المتوافقة الوحيدة هي
$$e\in\{(0,1),(0,2),(2,1),(2,2)\}.$$
ولهذا نحصل في هذه الحالة الواحدة على
$$F_2(v)=A_1(0,1)+A_1(0,2)+A_1(2,1)+A_1(2,2).$$
هذا المثال يوضح بدقة لماذا يظهر عامل \(2^r\): كل لون في موضع فردي يمنع لونًا واحدًا فقط في خانة الواجهة الموافقة من الصف السابق. وكفحص صغير على مستوى الشكل كله، فإن المثلث ذي الصفين يملك \(3\cdot 2\cdot 2\cdot 2=24\) تلوينًا صحيحًا.
تبدأ تطبيقات C++ وPython وJava بتوليد كل تلوين قانوني لكل صف عبر بحث عمقي يفرض الشرط \(x_i\ne x_{i+1}\) مباشرة. وبعد ذلك يُمثَّل كل صف بتوقيعه الزوجي وتوقيعه الفردي. نسختا C++ وPython تستخدمان أعدادًا صحيحة بالأساس 3 لترميز هذه التواقيع، بينما تستخدم نسخة Java تواقيع نصية مدمجة مشتقة من الحالات نفسها.
عند الانتقال من الصف \(r-1\) إلى الصف \(r\)، تجمع التطبيقات كل الأعداد السابقة التي تشترك في التوقيع الزوجي المكشوف نفسه. بذلك تتحول مجموعة كبيرة من الحالات الكاملة إلى جدول أصغر بكثير مفهرس فقط بواسطة \(3^r\) توقيعًا زوجيًا ممكنًا بطول \(r\). وبعد هذا الضغط، يحتاج كل صف حالي فقط إلى مجموع التواقيع السابقة التي تختلف خانة بخانة عن توقيعه الفردي.
كثير من حالات الصف الحالي تشترك في التوقيع الفردي نفسه. لذلك تقوم نسختا C++ وPython بحفظ مجموع الواجهة المتوافقة لكل توقيع فردي مطلوب، وتحسبانه عبر تعداد تراجعي للتواقيع السابقة المسموح بها وعددها \(2^r\). أما نسخة Java فتكتب العلاقة نفسها بصورة مباشرة أكثر، إذ تمر على التواقيع السابقة المجمعة وتفحص التوافق رقميًا. بعد الصف الأخير تُجمع جميع القيم المتبقية. كما تتضمن نسخة C++ فحصًا بالقوة الغاشمة للأشكال الصغيرة جدًا، وهذا يمنح تحققًا مستقلًا من صحة العلاقة الديناميكية.
الصف رقم \(r\) يملك \(3\cdot 4^r\) حالة قانونية. وفي المسألة الفعلية يكون أكبر صف هو \(r=7\)، أي \(3\cdot 4^7=49{,}152\) حالة. هذا أصغر بكثير من \(3^{64}\)، لكنه ما يزال كبيرًا بما يكفي لجعل الانتقال الساذج بين كل حالتين في صفين متجاورين غير مناسب.
بعد ضغط الواجهة، يعيش الانتقال من الصف \(r-1\) إلى الصف \(r\) داخل فضاء تواقيع حجمه \(3^r\) فقط. في النسخ المحسنة التي تستعمل ترميزًا عدديًا، يكلف بناء الجدول المجمع \(O(4^r)\)، بينما يكلف حساب جميع مجاميع التوافق المختلفة \(O(3^r2^r)=O(6^r)\). الذاكرة أثناء التنفيذ يهيمن عليها جدول الصف الحالي وجدول الصف السابق إضافة إلى مصفوفة تجميع حجمها \(3^r\). وبما أن المسألة تتوقف عند \(r=7\)، فإن الطريقة سريعة عمليًا وتعطي الجواب الدقيق بلا أي تقريب.