Problem 867 asks for the number of admissible tilings of a dodecagon of order \(n\), and the implementations evaluate the case \(n=10\) modulo
$$M=10^9+7.$$
The key point is that the geometry is not attacked tile by tile. Instead, the region is converted into a layered conflict graph, and a valid tiling becomes an independent set on that graph. Once that translation is made, the task becomes a transfer-matrix problem on rows whose lengths change by \(1\) at each step.
For any finite sequence of row lengths \((\ell_1,\ell_2,\dots,\ell_t)\), let
$$C(\ell_1,\ell_2,\dots,\ell_t)$$
denote the number of independent sets in the layered graph whose \(i\)-th row has \(\ell_i\) positions. The implementations solve the dodecagon problem by evaluating a small family of such row-profile counts and then combining them recursively.
A row of length \(L\) is represented by a bitmask \(m\in\{0,1,\dots,2^L-1\}\). A bit \(1\) means that the corresponding position is selected in the independent set. Two adjacent positions in the same row cannot both be selected, so a legal mask must satisfy
$$m \text{ is legal} \iff (m \mathbin{\&} (m \ll 1))=0.$$
Equivalently, a legal mask is an independent set of the path graph on \(L\) vertices. The number of such masks is Fibonacci-like, which is why the method remains practical even when all masks up to width \(2n-1\) are precomputed.
Suppose the current row has length \(L_c\) and the next row has length \(L_n\), where the geometry guarantees \(L_n=L_c\pm1\). Fix a legal mask \(b\) on the next row. It forbids certain positions on the current row because any touching pair would violate independence.
If the next row is longer, \(L_n=L_c+1\), then a selected position in \(b\) blocks the position directly under it and the one immediately to its left. If the next row is shorter, \(L_n=L_c-1\), it blocks the position directly above it and the one immediately to its right. Writing \(\operatorname{Forb}(b)\) for that forbidden set, a previous-row mask \(a\) is compatible exactly when
$$a \subseteq \overline{\operatorname{Forb}(b)}.$$
Therefore, if \(\operatorname{dp}_{\mathrm{cur}}[a]\) counts all partial configurations ending with mask \(a\), then the next layer satisfies
$$\operatorname{dp}_{\mathrm{next}}[b]=\sum_{a\subseteq \overline{\operatorname{Forb}(b)}} \operatorname{dp}_{\mathrm{cur}}[a].$$
Computing the sum above separately for every \(b\) would repeat the same submask enumeration many times. The implementations avoid that by forming the subset zeta transform
$$Z(S)=\sum_{A\subseteq S}\operatorname{dp}_{\mathrm{cur}}[A].$$
Once \(Z\) has been computed for all subsets \(S\subseteq\{0,\dots,L_c-1\}\), every transition becomes a single table lookup:
$$\operatorname{dp}_{\mathrm{next}}[b]=Z\!\left(\overline{\operatorname{Forb}(b)}\right).$$
The standard bit-by-bit sweep computes \(Z\) in \(O(L_c2^{L_c})\) time, which is the dominant cost of each layer transition.
The full dodecagon is assembled from two recurring shapes, and both are counted by the same row-profile engine.
The first is a symmetric belt whose row lengths grow from \(n\) up to \(2n-1\) and then shrink back to \(n\):
$$B_n=C(n,n+1,\dots,2n-1,2n-2,\dots,n).$$
The second is a corner staircase of height \(h-1\):
$$K_{n,h}=C(n-2,n-3,\dots,n-h).$$
So the geometric complexity of the dodecagon is reduced to repeatedly evaluating these belt and corner profile counts.
Let \(Q(u,v)\) be the memoized count for the reduced central configuration that remains after stripping equal corner layers. The implementations use the recurrence
$$Q(u,0)=B_u,$$
$$Q(u,v)=\mathbf{1}_{(u,v)=(1,1)}+\sum_{w=0}^{u-1} Q(v,w)\,K_{u,u-w}^{\,6} \qquad (v>0).$$
The exponent \(6\) comes from the six congruent corner sectors of the dodecagon. After the interface parameter \(w\) is fixed, those six sectors contribute independently, so their counts multiply. The target quantity is then recovered by
$$A_n=2Q(n,n)-\mathbf{1}_{n=1}.$$
This formula is exactly the one implemented in all three languages.
For \(n=1\), the symmetric belt consists of a single row of length \(1\), so \(B_1=C(1)=2\): the mask may be empty or occupied. The corner profile is empty, hence \(K_{1,1}=1\). Therefore
$$Q(1,1)=1+Q(1,0)\,K_{1,1}^{\,6}=1+2=3,$$
and the final count is
$$A_1=2\cdot 3-1=5.$$
For \(n=2\), the belt profile is \((2,3,2)\), and the implementation evaluates
$$B_2=C(2,3,2)=19.$$
Both relevant corner staircases contribute \(1\), so
$$Q(2,1)=Q(1,0)+Q(1,1)=2+3=5,$$
$$Q(2,2)=Q(2,0)+Q(2,1)=19+5=24,$$
and finally
$$A_2=2\cdot 24=48.$$
These two values are the small checkpoints used by the implementations, so they provide a good sanity check for the whole derivation.
The C++, Python, and Java implementations all follow the same pipeline. First they precompute every legal row mask for each width from \(0\) to \(2n-1\). Next they run the row-profile dynamic program described above, caching results by the row-length sequence so that repeated belt or corner profiles are evaluated only once. On each transition they build the subset-sum table for the current row, use it to fill the next row in one pass over the legal masks, and then sum the counts on the last row.
Above that transfer-matrix layer, the implementation memoizes the one-parameter belt counts, the two-parameter corner counts, and the two-parameter recursive assembly values. Modular exponentiation is used only when the six identical corner contributions must be raised to the sixth power. Because the same subproblems occur many times, memoization is essential to keeping the recursive stage small.
Let \(W=2n-1\) be the maximum row width. Precomputing all legal masks costs \(O(2^W)\) time and storage. For a single row-profile sequence \((\ell_1,\dots,\ell_t)\), the transfer stage costs
$$O\!\left(\sum_{i=1}^{t-1} \ell_i 2^{\ell_i}\right),$$
because each layer transition is dominated by one subset-zeta transform on a width-\(\ell_i\) row. The recursive assembly has \(O(n^2)\) memo states, and each state sums over at most \(u\) interface values, so the extra gluing work is \(O(n^3)\) after cached profile counts are available. In practice the profile DP dominates, while the memory footprint is \(O(2^W)\) for the active DP arrays plus the memo tables.
Problem 867 fragt nach der Anzahl zulässiger Parkettierungen eines Dodekagons der Ordnung \(n\); die Implementierungen berechnen den Fall \(n=10\) modulo
$$M=10^9+7.$$
Die Geometrie wird nicht direkt Stein für Stein durchsucht. Stattdessen wird die Figur in einen geschichteten Konfliktgraphen übersetzt, und jede gültige Parkettierung entspricht dort einer unabhängigen Menge. Danach bleibt ein Transfer-Matrix-Problem über Zeilen, deren Längen sich jeweils nur um \(1\) unterscheiden.
Für eine endliche Folge von Zeilenlängen \((\ell_1,\ell_2,\dots,\ell_t)\) sei
$$C(\ell_1,\ell_2,\dots,\ell_t)$$
die Anzahl unabhängiger Mengen im geschichteten Graphen, dessen \(i\)-te Zeile genau \(\ell_i\) Positionen besitzt. Das Dodekagon wird vollständig durch einige wenige solcher Zeilenprofile beschrieben, die anschließend rekursiv zusammengesetzt werden.
Eine Zeile der Länge \(L\) wird durch eine Bitmaske \(m\in\{0,1,\dots,2^L-1\}\) dargestellt. Ein Bit \(1\) bedeutet, dass die betreffende Position in der unabhängigen Menge gewählt wird. Zwei benachbarte Positionen derselben Zeile dürfen nicht gleichzeitig gewählt werden, also gilt
$$m \text{ ist zulässig} \iff (m \mathbin{\&} (m \ll 1))=0.$$
Damit sind die zulässigen Masken genau die unabhängigen Mengen des Pfadgraphen auf \(L\) Knoten. Ihre Anzahl wächst Fibonacci-artig, weshalb die Vorberechnung aller Masken bis Breite \(2n-1\) praktikabel bleibt.
Sei die aktuelle Zeile von Länge \(L_c\) und die nächste von Länge \(L_n\), wobei wegen der Geometrie stets \(L_n=L_c\pm1\) gilt. Fixiere eine zulässige Maske \(b\) auf der nächsten Zeile. Sie verbietet bestimmte Positionen auf der aktuellen Zeile, denn jede berührende Auswahl würde die Unabhängigkeit verletzen.
Falls die nächste Zeile länger ist, also \(L_n=L_c+1\), blockiert eine gewählte Position in \(b\) die direkt darunter liegende Position und die unmittelbar links davon. Falls die nächste Zeile kürzer ist, also \(L_n=L_c-1\), blockiert sie die direkt darüber liegende Position und die unmittelbar rechts davon. Mit \(\operatorname{Forb}(b)\) als verbotener Menge ist eine frühere Maske \(a\) genau dann kompatibel, wenn
$$a \subseteq \overline{\operatorname{Forb}(b)}.$$
Daher erfüllt die Übergangs-DP
$$\operatorname{dp}_{\mathrm{next}}[b]=\sum_{a\subseteq \overline{\operatorname{Forb}(b)}} \operatorname{dp}_{\mathrm{cur}}[a].$$
Würde man diese Summe für jedes \(b\) getrennt über alle Teilmengen auswerten, entstünde viel Wiederholung. Deshalb bilden die Implementierungen zuerst die Teilmengen-Zeta-Transformation
$$Z(S)=\sum_{A\subseteq S}\operatorname{dp}_{\mathrm{cur}}[A].$$
Ist \(Z\) für alle Teilmengen \(S\subseteq\{0,\dots,L_c-1\}\) bekannt, dann wird jeder Übergang zu einer einzigen Tabelle-Abfrage:
$$\operatorname{dp}_{\mathrm{next}}[b]=Z\!\left(\overline{\operatorname{Forb}(b)}\right).$$
Die übliche bitweise Zeta-Sweep-Berechnung kostet \(O(L_c2^{L_c})\) Zeit und dominiert damit den Aufwand pro Schicht.
Für das gesamte Dodekagon werden nur zwei wiederkehrende Formtypen benötigt, und beide lassen sich mit derselben Profil-DP zählen.
Der erste Typ ist ein symmetrischer Gürtel, dessen Zeilenlängen von \(n\) auf \(2n-1\) anwachsen und danach wieder auf \(n\) schrumpfen:
$$B_n=C(n,n+1,\dots,2n-1,2n-2,\dots,n).$$
Der zweite Typ ist eine Ecktreppe der Höhe \(h-1\):
$$K_{n,h}=C(n-2,n-3,\dots,n-h).$$
Die eigentliche geometrische Schwierigkeit wird also auf wiederholte Auswertungen dieser Gürtel- und Eckprofile zurückgeführt.
Sei \(Q(u,v)\) die memoisiert berechnete Anzahl für die reduzierte zentrale Konfiguration, die nach dem Entfernen gleicher Eckenlagen übrig bleibt. Die Implementierungen verwenden
$$Q(u,0)=B_u,$$
$$Q(u,v)=\mathbf{1}_{(u,v)=(1,1)}+\sum_{w=0}^{u-1} Q(v,w)\,K_{u,u-w}^{\,6} \qquad (v>0).$$
Die Potenz \(6\) entsteht durch die sechs kongruenten Ecksektoren des Dodekagons. Ist der Schnittparameter \(w\) festgelegt, tragen diese sechs Sektoren unabhängig voneinander bei, also multiplizieren sich ihre Anzahlen. Die gesuchte Gesamtzahl erhält man durch
$$A_n=2Q(n,n)-\mathbf{1}_{n=1}.$$
Genau diese Formel wird in allen drei Sprachen umgesetzt.
Für \(n=1\) besteht der symmetrische Gürtel nur aus einer einzigen Zeile der Länge \(1\), also ist \(B_1=C(1)=2\): die Maske ist entweder leer oder belegt. Das Eckprofil ist leer, deshalb gilt \(K_{1,1}=1\). Somit
$$Q(1,1)=1+Q(1,0)\,K_{1,1}^{\,6}=1+2=3,$$
und die Endzahl ist
$$A_1=2\cdot 3-1=5.$$
Für \(n=2\) lautet das Gürtelprofil \((2,3,2)\), und die Implementierungen berechnen
$$B_2=C(2,3,2)=19.$$
Beide relevanten Ecktreppen liefern den Wert \(1\), also
$$Q(2,1)=Q(1,0)+Q(1,1)=2+3=5,$$
$$Q(2,2)=Q(2,0)+Q(2,1)=19+5=24,$$
und damit schließlich
$$A_2=2\cdot 24=48.$$
Diese beiden Zahlen sind die kleinen Prüfwerte der Implementierungen und bestätigen daher die Herleitung sehr gut.
Die C++-, Python- und Java-Implementierungen folgen exakt derselben Pipeline. Zuerst werden für jede Breite von \(0\) bis \(2n-1\) alle zulässigen Zeilenmasken vorbereitet. Danach läuft die oben beschriebene Profil-DP, wobei Resultate nach Zeilenlängenfolge zwischengespeichert werden, damit identische Gürtel- oder Eckprofile nur einmal ausgewertet werden. Bei jedem Übergang wird zunächst die Teilmengen-Summtabelle der aktuellen Zeile aufgebaut, dann die nächste Zeile in einem Durchlauf über ihre zulässigen Masken gefüllt und am Ende über die letzte Zeile aufsummiert.
Oberhalb dieser Transfer-Matrix-Ebene merkt sich die Implementierung die Gürtelwerte, die Eckwerte und die zweiparametrigen Rekursionswerte. Modulare Potenzierung wird nur benötigt, wenn die sechs identischen Eckenbeiträge zur sechsten Potenz erhoben werden. Weil dieselben Teilprobleme immer wieder auftreten, ist Memoisierung der entscheidende Beschleuniger der rekursiven Phase.
Sei \(W=2n-1\) die maximale Zeilenbreite. Das Vorberechnen aller zulässigen Masken kostet \(O(2^W)\) Zeit und Speicher. Für ein einzelnes Profil \((\ell_1,\dots,\ell_t)\) kostet die Transfer-Stufe
$$O\!\left(\sum_{i=1}^{t-1} \ell_i 2^{\ell_i}\right),$$
weil jeder Schichtübergang im Wesentlichen eine Teilmengen-Zeta-Transformation auf einer Breite \(\ell_i\) ausführt. Die rekursive Zusammensetzung besitzt \(O(n^2)\) Memo-Zustände; jeder Zustand summiert über höchstens \(u\) Schnittwerte, sodass darüber hinaus \(O(n^3)\) Klebearbeit anfällt, sobald die Profilwerte im Cache liegen. Praktisch dominiert die Profil-DP, während der Speicherbedarf aus \(O(2^W)\) für aktive DP-Arrays plus Memo-Tabellen besteht.
Problem 867, mertebesi \(n\) olan bir onikigenin geçerli döşemelerinin sayısını sorar; implementasyonlar \(n=10\) durumu için sonucu
$$M=10^9+7$$
modunda hesaplar. Geometri doğrudan karo karo sayılmaz. Bunun yerine bölge katmanlı bir çatışma grafına çevrilir ve her geçerli döşeme bu graf üzerinde bir bağımsız kümeye karşılık gelir. Böylece problem, uzunlukları her adımda yalnızca \(1\) değişen satırlar üzerinde bir aktarım matrisi problemine dönüşür.
Sonlu bir satır uzunlukları dizisi \((\ell_1,\ell_2,\dots,\ell_t)\) için
$$C(\ell_1,\ell_2,\dots,\ell_t)$$
ifadesi, \(i\). satırı \(\ell_i\) konum içeren katmanlı graf üzerindeki bağımsız kümelerin sayısını göstersin. Implementasyonlar, onikigen problemini birkaç temel satır profilini hesaplayıp bunları rekürsif olarak birleştirerek çözer.
Uzunluğu \(L\) olan bir satır, \(m\in\{0,1,\dots,2^L-1\}\) biçiminde bir bit maskesiyle temsil edilir. Bir bitin \(1\) olması, ilgili konumun bağımsız kümeye alındığını gösterir. Aynı satırda yan yana iki konum birlikte seçilemez; dolayısıyla geçerli maske koşulu
$$m \text{ geçerlidir} \iff (m \mathbin{\&} (m \ll 1))=0$$
şeklindedir. Başka bir deyişle bu maskeler, \(L\) düğümlü bir yol grafının bağımsız kümeleridir. Sayıları Fibonacci benzeri büyüdüğü için \(2n-1\) genişliğine kadar tüm maskeleri önceden üretmek hâlâ pratiktir.
Geçerli geometride bir satırın uzunluğu bir sonraki satıra geçerken yalnızca \(1\) artar ya da azalır. Yani mevcut satır uzunluğu \(L_c\), sonraki satır uzunluğu \(L_n\) ve \(L_n=L_c\pm1\) olur. Sonraki satırdaki geçerli bir \(b\) maskesini sabitleyelim. Bu maske, temas yasağı nedeniyle mevcut satırda bazı konumları yasaklar.
Eğer sonraki satır daha uzunsa, yani \(L_n=L_c+1\), \(b\) içindeki seçili bir konum mevcut satırda tam altındaki konumu ve onun hemen solundakini yasaklar. Eğer sonraki satır daha kısaysa, yani \(L_n=L_c-1\), bu kez tam üstündeki konumu ve hemen sağındakini yasaklar. Bu yasaklı kümeyi \(\operatorname{Forb}(b)\) ile gösterirsek, önceki satırın \(a\) maskesi ancak
$$a \subseteq \overline{\operatorname{Forb}(b)}$$
ise uyumludur. Böylece geçiş bağıntısı
$$\operatorname{dp}_{\mathrm{next}}[b]=\sum_{a\subseteq \overline{\operatorname{Forb}(b)}} \operatorname{dp}_{\mathrm{cur}}[a]$$
olur.
Bu toplamı her \(b\) için ayrı ayrı hesaplamak aynı alt-maskeleri tekrar tekrar dolaşmak demektir. Implementasyonlar bunu önlemek için önce alt-küme zeta dönüşümünü kurar:
$$Z(S)=\sum_{A\subseteq S}\operatorname{dp}_{\mathrm{cur}}[A].$$
\(Z\) tüm \(S\subseteq\{0,\dots,L_c-1\}\) alt-kümeleri için hazır olduğunda, her geçiş tek bir tablo erişimine iner:
$$\operatorname{dp}_{\mathrm{next}}[b]=Z\!\left(\overline{\operatorname{Forb}(b)}\right).$$
Bitler üzerinde yapılan standart zeta süpürmesi bu tabloyu \(O(L_c2^{L_c})\) zamanda üretir; dolayısıyla her katmanın baskın maliyeti budur.
Tüm onikigen yalnızca iki tekrar eden şekil ailesi kullanılarak kuruluyor ve her ikisi de aynı satır-profili DP motoruyla sayılıyor.
Birinci aile, satır uzunlukları \(n\)'den \(2n-1\)'e çıkıp sonra tekrar \(n\)'e dönen simetrik bir kuşaktır:
$$B_n=C(n,n+1,\dots,2n-1,2n-2,\dots,n).$$
İkinci aile ise yüksekliği \(h-1\) olan bir köşe merdivenidir:
$$K_{n,h}=C(n-2,n-3,\dots,n-h).$$
Böylece geometrik karmaşıklık, tekrar tekrar bu kuşak ve köşe profillerini değerlendirme işine indirgenmiş olur.
\(Q(u,v)\), eşit köşe katmanları soyulduktan sonra geriye kalan azaltılmış merkez yapının memoize edilmiş sayısı olsun. Implementasyonların kullandığı bağıntı
$$Q(u,0)=B_u,$$
$$Q(u,v)=\mathbf{1}_{(u,v)=(1,1)}+\sum_{w=0}^{u-1} Q(v,w)\,K_{u,u-w}^{\,6} \qquad (v>0)$$
şeklindedir. Buradaki \(6\). kuvvet, onikigenin eşlenik altı köşe sektöründen gelir. Arayüz parametresi \(w\) sabitlenince bu altı sektör birbirinden bağımsız katkı verir ve sayıları çarpılır. Son hedef değer de
$$A_n=2Q(n,n)-\mathbf{1}_{n=1}$$
formülüyle elde edilir. Üç dildeki implementasyonların hepsi tam olarak bunu uygular.
\(n=1\) için simetrik kuşak yalnızca uzunluğu \(1\) olan tek bir satırdan oluşur; dolayısıyla \(B_1=C(1)=2\). Çünkü maske ya boştur ya da tek konumu seçer. Köşe profili boştur, bu yüzden \(K_{1,1}=1\). O hâlde
$$Q(1,1)=1+Q(1,0)\,K_{1,1}^{\,6}=1+2=3,$$
ve son sayı
$$A_1=2\cdot 3-1=5$$
olur.
\(n=2\) için kuşak profili \((2,3,2)\)'dir ve implementasyonlar
$$B_2=C(2,3,2)=19$$
değerini verir. Gerekli iki köşe merdiveni de \(1\) katkı yapar. Böylece
$$Q(2,1)=Q(1,0)+Q(1,1)=2+3=5,$$
$$Q(2,2)=Q(2,0)+Q(2,1)=19+5=24,$$
ve son olarak
$$A_2=2\cdot 24=48$$
elde edilir. Bu iki küçük değer implementasyonlarda da kontrol noktası olarak kullanılır.
C++, Python ve Java implementasyonları aynı işlem hattını izler. Önce \(0\) ile \(2n-1\) arasındaki her genişlik için tüm geçerli satır maskeleri önceden hazırlanır. Ardından yukarıdaki satır-profili dinamik programı çalıştırılır ve aynı kuşak veya köşe profili tekrarlandığında yeniden hesap yapılmaması için sonuçlar satır uzunlukları dizisine göre önbelleğe alınır. Her geçişte mevcut satırın alt-küme toplam tablosu kurulur, sonra sonraki satır kendi geçerli maskeleri üzerinden tek geçişte doldurulur ve en sonda son satırdaki tüm sayılar toplanır.
Bu aktarım-matrisi katmanının üstünde, implementasyon kuşak sayımlarını, köşe sayımlarını ve iki parametreli rekürsif birleştirme değerlerini memoize eder. Modüler üs alma yalnızca altı özdeş köşe katkısının altıncı kuvveti gerektiğinde kullanılır. Aynı alt problemler çok sık tekrarlandığından, rekürsif katmanın verimli kalmasının ana nedeni bu memoizasyondur.
Maksimum satır genişliği \(W=2n-1\) olsun. Tüm geçerli maskeleri önceden üretmek \(O(2^W)\) zaman ve bellek ister. Tek bir profil \((\ell_1,\dots,\ell_t)\) için aktarım aşamasının maliyeti
$$O\!\left(\sum_{i=1}^{t-1} \ell_i 2^{\ell_i}\right)$$
şeklindedir; çünkü her katman geçişi özünde genişliği \(\ell_i\) olan bir satır üzerinde alt-küme zeta dönüşümü yapar. Rekürsif birleştirme kısmında \(O(n^2)\) adet memo durumu vardır ve her durum en fazla \(u\) arayüz değeri üzerinden toplama yapar; dolayısıyla profil değerleri hazır olduktan sonra ek yapıştırma maliyeti \(O(n^3)\) olur. Pratikte baskın kısım profil DP'sidir; bellek kullanımı ise etkin DP dizileri için \(O(2^W)\) ve buna ek olarak memo tablolarıdır.
El problema 867 pide contar los recubrimientos válidos de un dodecágono de orden \(n\); las implementaciones evalúan el caso \(n=10\) módulo
$$M=10^9+7.$$
La geometría no se ataca loseta por loseta. En cambio, la región se traduce a un grafo de conflictos por capas, y cada recubrimiento válido pasa a ser un conjunto independiente en ese grafo. Después de esa traducción, el problema se convierte en una cuenta por matriz de transferencia sobre filas cuyas longitudes cambian en \(1\) en cada paso.
Para cualquier secuencia finita de longitudes de fila \((\ell_1,\ell_2,\dots,\ell_t)\), definamos
$$C(\ell_1,\ell_2,\dots,\ell_t)$$
como el número de conjuntos independientes en el grafo por capas cuya fila \(i\) tiene exactamente \(\ell_i\) posiciones. Las implementaciones resuelven el dodecágono evaluando unas pocas familias de perfiles de fila y combinándolas luego de forma recursiva.
Una fila de longitud \(L\) se representa mediante una máscara de bits \(m\in\{0,1,\dots,2^L-1\}\). Un bit \(1\) indica que la posición correspondiente ha sido elegida en el conjunto independiente. Dos posiciones adyacentes de la misma fila no pueden elegirse a la vez, así que una máscara legal debe cumplir
$$m \text{ es legal} \iff (m \mathbin{\&} (m \ll 1))=0.$$
En otras palabras, las máscaras legales son exactamente los conjuntos independientes del camino de \(L\) vértices. Su número crece de forma tipo Fibonacci, por lo que sigue siendo razonable precomputarlas para todas las anchuras hasta \(2n-1\).
Supongamos que la fila actual tiene longitud \(L_c\) y la siguiente tiene longitud \(L_n\), con \(L_n=L_c\pm1\). Fijemos una máscara legal \(b\) en la fila siguiente. Esa máscara prohíbe ciertas posiciones de la fila actual, porque cualquier pareja que se toque rompería la independencia.
Si la fila siguiente es más larga, es decir, \(L_n=L_c+1\), una posición ocupada en \(b\) bloquea la posición situada justo debajo y la inmediata a su izquierda. Si la fila siguiente es más corta, o sea, \(L_n=L_c-1\), bloquea la posición situada justo encima y la inmediata a su derecha. Si llamamos \(\operatorname{Forb}(b)\) al conjunto prohibido, entonces una máscara previa \(a\) es compatible exactamente cuando
$$a \subseteq \overline{\operatorname{Forb}(b)}.$$
Por tanto, la transición cumple
$$\operatorname{dp}_{\mathrm{next}}[b]=\sum_{a\subseteq \overline{\operatorname{Forb}(b)}} \operatorname{dp}_{\mathrm{cur}}[a].$$
Calcular la suma anterior para cada \(b\) por separado repetiría muchas veces la misma enumeración de submáscaras. Para evitarlo, las implementaciones construyen primero la transformación zeta sobre subconjuntos
$$Z(S)=\sum_{A\subseteq S}\operatorname{dp}_{\mathrm{cur}}[A].$$
Una vez que \(Z\) está disponible para todos los \(S\subseteq\{0,\dots,L_c-1\}\), cada transición se reduce a una sola consulta:
$$\operatorname{dp}_{\mathrm{next}}[b]=Z\!\left(\overline{\operatorname{Forb}(b)}\right).$$
El barrido estándar bit a bit calcula \(Z\) en tiempo \(O(L_c2^{L_c})\), y ese es el coste dominante de cada cambio de capa.
El dodecágono completo se construye a partir de dos tipos de formas recurrentes, y ambos se cuentan con el mismo motor de perfiles por filas.
El primero es una banda simétrica cuyas longitudes suben desde \(n\) hasta \(2n-1\) y luego vuelven a bajar hasta \(n\):
$$B_n=C(n,n+1,\dots,2n-1,2n-2,\dots,n).$$
El segundo es una escalera de esquina de altura \(h-1\):
$$K_{n,h}=C(n-2,n-3,\dots,n-h).$$
Así, la dificultad geométrica queda reducida a evaluar muchas veces estas bandas y esquinas canónicas.
Sea \(Q(u,v)\) el número memoizado de la configuración central reducida que queda después de retirar capas iguales de las esquinas. Las implementaciones usan la recurrencia
$$Q(u,0)=B_u,$$
$$Q(u,v)=\mathbf{1}_{(u,v)=(1,1)}+\sum_{w=0}^{u-1} Q(v,w)\,K_{u,u-w}^{\,6} \qquad (v>0).$$
La potencia \(6\) aparece porque el dodecágono tiene seis sectores de esquina congruentes. Una vez fijado el parámetro de interfaz \(w\), esos seis sectores aportan de manera independiente, así que sus cuentas se multiplican. La cantidad final se recupera mediante
$$A_n=2Q(n,n)-\mathbf{1}_{n=1}.$$
Esa es exactamente la fórmula implementada en C++, Python y Java.
Para \(n=1\), la banda simétrica es solo una fila de longitud \(1\), por lo que \(B_1=C(1)=2\): la máscara puede estar vacía o contener la única posición. El perfil de esquina está vacío, así que \(K_{1,1}=1\). Por consiguiente,
$$Q(1,1)=1+Q(1,0)\,K_{1,1}^{\,6}=1+2=3,$$
y el recuento final es
$$A_1=2\cdot 3-1=5.$$
Para \(n=2\), el perfil de la banda es \((2,3,2)\), y la implementación obtiene
$$B_2=C(2,3,2)=19.$$
Las dos escaleras de esquina relevantes valen \(1\), luego
$$Q(2,1)=Q(1,0)+Q(1,1)=2+3=5,$$
$$Q(2,2)=Q(2,0)+Q(2,1)=19+5=24,$$
y finalmente
$$A_2=2\cdot 24=48.$$
Estos dos valores aparecen como comprobaciones pequeñas en las implementaciones y validan la derivación.
Las implementaciones en C++, Python y Java siguen exactamente la misma estrategia. Primero precalculan todas las máscaras legales para cada anchura entre \(0\) y \(2n-1\). Después ejecutan la programación dinámica por perfiles de fila y guardan en caché los resultados según la secuencia de longitudes, para que una banda o una esquina ya calculada no se vuelvan a evaluar. En cada transición construyen la tabla de sumas por subconjuntos de la fila actual, rellenan la siguiente fila con una sola pasada sobre sus máscaras legales y al final suman las cuentas de la última fila.
Por encima de esa capa de matriz de transferencia, la implementación memoiza los recuentos de bandas, los de esquinas y los valores de la recurrencia de dos parámetros. La potenciación modular solo se usa cuando hay que elevar a la sexta potencia la contribución de las seis esquinas idénticas. Como los mismos subproblemas reaparecen muchas veces, la memoización es lo que mantiene pequeña la fase recursiva.
Sea \(W=2n-1\) la anchura máxima de fila. Precalcular todas las máscaras legales cuesta \(O(2^W)\) tiempo y memoria. Para un perfil concreto \((\ell_1,\dots,\ell_t)\), la fase de transferencia cuesta
$$O\!\left(\sum_{i=1}^{t-1} \ell_i 2^{\ell_i}\right),$$
porque cada transición entre capas está dominada por una transformación zeta sobre subconjuntos en una fila de anchura \(\ell_i\). El ensamblaje recursivo tiene \(O(n^2)\) estados memoizados, y cada estado suma sobre como mucho \(u\) valores de interfaz; por tanto, el trabajo adicional de pegado es \(O(n^3)\) una vez disponibles los perfiles en caché. En la práctica domina la DP de perfiles, y el uso de memoria es \(O(2^W)\) para los vectores activos más las tablas de memoización.
第 867 题要求计算一个阶数为 \(n\) 的十二边形的合法铺法数量；这三份实现求的是 \(n=10\) 时的结果，并且对
$$M=10^9+7$$
取模。它们并不直接枚举所有铺法，而是先把几何问题改写成一个分层冲突图上的独立集计数问题。完成这一步之后，原题就变成了一个按行推进的转移问题，其中相邻两行的长度每次只相差 \(1\)。
对任意有限的行长度序列 \((\ell_1,\ell_2,\dots,\ell_t)\)，记
$$C(\ell_1,\ell_2,\dots,\ell_t)$$
为对应分层图中的独立集个数，其中第 \(i\) 行恰好有 \(\ell_i\) 个位置。三份实现的核心思路，就是先计算少数几类标准行轮廓的计数，再把它们用一个递推关系拼成完整的十二边形。
长度为 \(L\) 的一行可以用一个位掩码 \(m\in\{0,1,\dots,2^L-1\}\) 表示。某一位为 \(1\) 表示该位置被选入独立集。由于同一行内相邻位置不能同时被选中，合法掩码必须满足
$$m \text{ 合法} \iff (m \mathbin{\&} (m \ll 1))=0.$$
也就是说，合法掩码正好对应于长度为 \(L\) 的路径图上的独立集。这样的掩码个数按 Fibonacci 型增长，因此即使把所有宽度直到 \(2n-1\) 的合法掩码都预处理出来，规模仍然可控。
设当前行长度为 \(L_c\)，下一行长度为 \(L_n\)。在本题的几何结构中，总有 \(L_n=L_c\pm1\)。固定下一行上的一个合法掩码 \(b\)。由于独立集不允许相互接触，\(b\) 会在当前行中禁止若干位置。
当下一行更长，即 \(L_n=L_c+1\) 时，\(b\) 中一个被选中的位置会禁止当前行里它正下方的位置以及左侧紧邻的位置。当下一行更短，即 \(L_n=L_c-1\) 时，它会禁止当前行里它正上方的位置以及右侧紧邻的位置。把这些被禁止的位置记作 \(\operatorname{Forb}(b)\)，那么上一行的掩码 \(a\) 与 \(b\) 兼容，当且仅当
$$a \subseteq \overline{\operatorname{Forb}(b)}.$$
于是转移方程就是
$$\operatorname{dp}_{\mathrm{next}}[b]=\sum_{a\subseteq \overline{\operatorname{Forb}(b)}} \operatorname{dp}_{\mathrm{cur}}[a].$$
如果对每个 \(b\) 都单独枚举所有可行子掩码，上式会重复做大量相同工作。实现采用的优化是先计算子集 zeta 变换
$$Z(S)=\sum_{A\subseteq S}\operatorname{dp}_{\mathrm{cur}}[A].$$
只要所有 \(S\subseteq\{0,\dots,L_c-1\}\) 的 \(Z(S)\) 都已经备好，那么每个下一行状态就只需要一次查表：
$$\operatorname{dp}_{\mathrm{next}}[b]=Z\!\left(\overline{\operatorname{Forb}(b)}\right).$$
标准的按位扫描可以在 \(O(L_c2^{L_c})\) 时间内完成整个 zeta 变换，因此每一层的主耗时都落在这里。
完整的十二边形并不需要对任意轮廓都重新建模，只需要两类反复出现的标准形状，而且它们都能用同一套行轮廓 DP 来计数。
第一类是对称的中带区域，行长度从 \(n\) 增长到 \(2n-1\)，再下降回 \(n\)：
$$B_n=C(n,n+1,\dots,2n-1,2n-2,\dots,n).$$
第二类是高度为 \(h-1\) 的角落阶梯：
$$K_{n,h}=C(n-2,n-3,\dots,n-h).$$
因此，原始几何问题被拆成了反复计算“对称中带”和“角落阶梯”这两类标准组件的任务。
记 \(Q(u,v)\) 为去掉若干层对称角块之后，剩余中心结构的记忆化计数。实现中使用的递推关系是
$$Q(u,0)=B_u,$$
$$Q(u,v)=\mathbf{1}_{(u,v)=(1,1)}+\sum_{w=0}^{u-1} Q(v,w)\,K_{u,u-w}^{\,6} \qquad (v>0).$$
这里的六次方来自十二边形的六个全等角区。一旦界面参数 \(w\) 被固定，这六个角区彼此独立，因此它们的计数可以直接相乘。最后的目标值由
$$A_n=2Q(n,n)-\mathbf{1}_{n=1}$$
给出。这正是三份实现共同采用的最终公式。
当 \(n=1\) 时，对称中带只有一行，长度为 \(1\)，因此 \(B_1=C(1)=2\)：该行要么不选，要么选中唯一的位置。角落轮廓为空，所以 \(K_{1,1}=1\)。于是
$$Q(1,1)=1+Q(1,0)\,K_{1,1}^{\,6}=1+2=3,$$
从而最终答案是
$$A_1=2\cdot 3-1=5.$$
当 \(n=2\) 时，中带轮廓为 \((2,3,2)\)，实现计算得到
$$B_2=C(2,3,2)=19.$$
两个需要用到的角落阶梯都只贡献 \(1\)，因此
$$Q(2,1)=Q(1,0)+Q(1,1)=2+3=5,$$
$$Q(2,2)=Q(2,0)+Q(2,1)=19+5=24,$$
最后得到
$$A_2=2\cdot 24=48.$$
这两个小规模结果正好就是实现中使用的检查点，因此非常适合作为整套推导的验算。
C++、Python 和 Java 三个版本遵循完全相同的流程。首先，它们为从 \(0\) 到 \(2n-1\) 的每一种行宽预计算全部合法掩码。然后运行上面描述的行轮廓动态规划，并按“行长度序列”缓存结果，这样同一个中带轮廓或角落轮廓只会被求值一次。每次进行一层转移时，先为当前行建立子集和表，再用一次遍历填充下一行的所有合法掩码，最后把末行上的计数全部累加起来。
在这层转移矩阵之上，实现还会分别记忆中带计数、角落计数以及双参数递推值。只有在六个相同角区的贡献需要合并时才会用到模幂运算。由于同样的子问题会反复出现，记忆化正是递推层保持高效的关键。
设最大行宽为 \(W=2n-1\)。预处理全部合法掩码需要 \(O(2^W)\) 时间和空间。对于单个轮廓 \((\ell_1,\dots,\ell_t)\)，转移阶段的复杂度是
$$O\!\left(\sum_{i=1}^{t-1} \ell_i 2^{\ell_i}\right),$$
因为每一层转移本质上都由一次宽度为 \(\ell_i\) 的子集 zeta 变换主导。递推拼装部分共有 \(O(n^2)\) 个记忆化状态，每个状态最多对 \(u\) 个界面参数求和，因此在轮廓结果已缓存之后，额外的拼装工作量为 \(O(n^3)\)。实际运行中，主导成本仍然是行轮廓 DP；内存主要消耗在 \(O(2^W)\) 大小的活动 DP 数组以及各类缓存表上。
В задаче 867 требуется посчитать число допустимых замощений двенадцатиугольника порядка \(n\); реализации вычисляют случай \(n=10\) по модулю
$$M=10^9+7.$$
Геометрия не перебирается плитка за плиткой. Вместо этого область переводится в послойный граф конфликтов, и каждое корректное замощение становится независимым множеством этого графа. После такой замены задача превращается в задачу переноса по строкам, длины которых меняются на \(1\) при каждом шаге.
Для любой конечной последовательности длин строк \((\ell_1,\ell_2,\dots,\ell_t)\) обозначим через
$$C(\ell_1,\ell_2,\dots,\ell_t)$$
число независимых множеств в послойном графе, у которого \(i\)-я строка имеет ровно \(\ell_i\) позиций. Все решение сводится к вычислению нескольких стандартных семейств таких профилей и их последующей рекурсивной сборке.
Строка длины \(L\) задается битовой маской \(m\in\{0,1,\dots,2^L-1\}\). Бит \(1\) означает, что соответствующая позиция выбрана в независимом множестве. Две соседние позиции в одной строке нельзя выбирать одновременно, поэтому допустимая маска должна удовлетворять условию
$$m \text{ допустима} \iff (m \mathbin{\&} (m \ll 1))=0.$$
То есть допустимые маски совпадают с независимыми множествами пути из \(L\) вершин. Их количество растет по фибоначчиевому типу, поэтому предварительно построить все маски до ширины \(2n-1\) вполне реально.
Пусть текущая строка имеет длину \(L_c\), а следующая строка имеет длину \(L_n\), причем по геометрии всегда \(L_n=L_c\pm1\). Зафиксируем допустимую маску \(b\) на следующей строке. Она запрещает некоторые позиции на текущей строке, потому что любая соприкасающаяся пара разрушила бы независимость.
Если следующая строка длиннее, то есть \(L_n=L_c+1\), выбранная позиция из \(b\) блокирует позицию прямо под собой и соседнюю слева. Если следующая строка короче, то есть \(L_n=L_c-1\), она блокирует позицию прямо над собой и соседнюю справа. Обозначив множество запрещенных позиций через \(\operatorname{Forb}(b)\), получаем: предыдущая маска \(a\) совместима с \(b\) тогда и только тогда, когда
$$a \subseteq \overline{\operatorname{Forb}(b)}.$$
Следовательно, переход имеет вид
$$\operatorname{dp}_{\mathrm{next}}[b]=\sum_{a\subseteq \overline{\operatorname{Forb}(b)}} \operatorname{dp}_{\mathrm{cur}}[a].$$
Если вычислять эту сумму отдельно для каждого \(b\), придется многократно перечислять одни и те же подмаски. Поэтому реализации сначала строят zeta-преобразование по подмножествам
$$Z(S)=\sum_{A\subseteq S}\operatorname{dp}_{\mathrm{cur}}[A].$$
Как только значения \(Z\) известны для всех \(S\subseteq\{0,\dots,L_c-1\}\), каждый переход становится одной табличной операцией:
$$\operatorname{dp}_{\mathrm{next}}[b]=Z\!\left(\overline{\operatorname{Forb}(b)}\right).$$
Стандартный побитовый проход вычисляет это преобразование за \(O(L_c2^{L_c})\), и именно он задает основную стоимость перехода между слоями.
Полный двенадцатиугольник строится из двух повторяющихся типов фигур, и обе считаются одним и тем же механизмом по профилям строк.
Первый тип — симметричный пояс, где длины строк растут от \(n\) до \(2n-1\), а затем возвращаются к \(n\):
$$B_n=C(n,n+1,\dots,2n-1,2n-2,\dots,n).$$
Второй тип — угловая лестница высоты \(h-1\):
$$K_{n,h}=C(n-2,n-3,\dots,n-h).$$
Значит, вся геометрическая сложность сводится к многократному вычислению этих симметричных поясов и угловых лестниц.
Пусть \(Q(u,v)\) — мемоизированное число для уменьшенной центральной конфигурации, которая остается после снятия одинаковых угловых слоев. Реализации используют рекурсию
$$Q(u,0)=B_u,$$
$$Q(u,v)=\mathbf{1}_{(u,v)=(1,1)}+\sum_{w=0}^{u-1} Q(v,w)\,K_{u,u-w}^{\,6} \qquad (v>0).$$
Степень \(6\) появляется из-за шести равных угловых секторов двенадцатиугольника. После выбора параметра стыка \(w\) эти шесть секторов дают независимый вклад, поэтому их количества перемножаются. Итоговая величина получается по формуле
$$A_n=2Q(n,n)-\mathbf{1}_{n=1}.$$
Именно это выражение реализовано во всех трех версиях программы.
При \(n=1\) симметричный пояс состоит из одной строки длины \(1\), поэтому \(B_1=C(1)=2\): маска либо пустая, либо выбирает единственную позицию. Угловой профиль пуст, значит \(K_{1,1}=1\). Тогда
$$Q(1,1)=1+Q(1,0)\,K_{1,1}^{\,6}=1+2=3,$$
и итог равен
$$A_1=2\cdot 3-1=5.$$
При \(n=2\) профиль пояса имеет вид \((2,3,2)\), и реализации получают
$$B_2=C(2,3,2)=19.$$
Обе нужные угловые лестницы дают значение \(1\), поэтому
$$Q(2,1)=Q(1,0)+Q(1,1)=2+3=5,$$
$$Q(2,2)=Q(2,0)+Q(2,1)=19+5=24,$$
а затем
$$A_2=2\cdot 24=48.$$
Эти два малых значения совпадают с контрольными точками в реализациях и хорошо подтверждают всю схему.
Реализации на C++, Python и Java используют один и тот же конвейер. Сначала они заранее строят все допустимые маски для каждой ширины от \(0\) до \(2n-1\). Затем запускают динамику по профилю строк и кэшируют результаты по самой последовательности длин, чтобы одинаковые пояса и углы считались только один раз. На каждом переходе сначала формируется таблица сумм по подмножествам для текущей строки, затем за один проход по допустимым маскам заполняется следующая строка, а в конце суммируются значения на последней строке.
Над этим трансферным уровнем реализация отдельно мемоизирует значения для поясов, для углов и для двухпараметрической рекурсии сборки. Модульное возведение в степень требуется только тогда, когда вклад шести одинаковых углов нужно возвести в шестую степень. Поскольку одни и те же подзадачи возникают снова и снова, именно мемоизация делает рекурсивную часть быстрой.
Пусть \(W=2n-1\) — максимальная ширина строки. Предварительное построение всех допустимых масок требует \(O(2^W)\) времени и памяти. Для одного профиля \((\ell_1,\dots,\ell_t)\) стоимость трансферной стадии равна
$$O\!\left(\sum_{i=1}^{t-1} \ell_i 2^{\ell_i}\right),$$
поскольку каждый переход между слоями определяется одной zeta-сверткой по подмножествам на ширине \(\ell_i\). Рекурсивная сборка имеет \(O(n^2)\) мемо-состояний, и каждое состояние суммирует не более чем по \(u\) значениям интерфейса, так что дополнительная работа после кэширования профилей составляет \(O(n^3)\). На практике доминирует именно динамика по профилям, а память расходуется как \(O(2^W)\) на активные массивы DP плюс таблицы кэша.
تطلب المسألة 867 حساب عدد التبليطات الصحيحة لاثني عشري منتظم من الرتبة \(n\)، بينما تقوم التطبيقات بحساب الحالة \(n=10\) بترديد
$$M=10^9+7.$$
الفكرة ليست تعداد التبليطات مباشرة قطعةً قطعة. بدلاً من ذلك تُحوَّل الهندسة إلى رسم بياني طبقي للتعارضات، وتصبح كل تبليطة صحيحة مجموعةً مستقلة في ذلك الرسم. بعد هذه الخطوة يتحول السؤال إلى مسألة انتقال صفّي، حيث يختلف طول كل صف عن الصف التالي بمقدار \(1\) فقط.
لكل متتالية منتهية من أطوال الصفوف \((\ell_1,\ell_2,\dots,\ell_t)\)، لنرمز بـ
$$C(\ell_1,\ell_2,\dots,\ell_t)$$
إلى عدد المجموعات المستقلة في الرسم البياني الطبقي الذي يحتوي صفه رقم \(i\) على \(\ell_i\) موضعًا بالضبط. تعتمد الحلول على حساب عدد صغير من هذه الملفات الصفية القياسية ثم دمجها بعلاقة عودية لإعادة بناء الشكل الكامل.
يُمثَّل الصف ذو الطول \(L\) بقناع بتات \(m\in\{0,1,\dots,2^L-1\}\). البت \(1\) يعني أن الموضع الموافق قد اختير ضمن المجموعة المستقلة. ولا يجوز اختيار موضعين متجاورين في الصف نفسه، ولذلك يكون القناع صالحًا إذا وفقط إذا تحقق الشرط
$$(m \mathbin{\&} (m \ll 1))=0.$$
وبصياغة أخرى، الأقنعة الصالحة هي بالضبط المجموعات المستقلة لمسار طوله \(L\). وعدد هذه الأقنعة ينمو على نمط فيبوناتشي تقريبًا، ولهذا يبقى من الممكن توليد جميع الأقنعة حتى العرض \(2n-1\) مسبقًا.
لنفرض أن طول الصف الحالي هو \(L_c\) وأن طول الصف التالي هو \(L_n\)، ومع بنية المسألة يكون دائمًا \(L_n=L_c\pm1\). إذا ثبتنا قناعًا صالحًا \(b\) على الصف التالي، فإنه يمنع بعض مواضع الصف الحالي لأن أي تماس مباشر سيكسر شرط الاستقلال.
إذا كان الصف التالي أطول، أي \(L_n=L_c+1\)، فإن الموضع المختار في \(b\) يمنع الموضع الواقع تحته مباشرة والموضع المجاور يسارًا. وإذا كان الصف التالي أقصر، أي \(L_n=L_c-1\)، فإنه يمنع الموضع الواقع فوقه مباشرة والموضع المجاور يمينًا. وإذا رمزنا إلى مجموعة المواضع الممنوعة بـ \(\operatorname{Forb}(b)\)، فإن قناع الصف السابق \(a\) يكون متوافقًا مع \(b\) إذا وفقط إذا
$$a \subseteq \overline{\operatorname{Forb}(b)}.$$
وعندئذ تصبح معادلة الانتقال
$$\operatorname{dp}_{\mathrm{next}}[b]=\sum_{a\subseteq \overline{\operatorname{Forb}(b)}} \operatorname{dp}_{\mathrm{cur}}[a].$$
لو حُسب هذا المجموع لكل \(b\) على حدة فسنعيد تعداد الأقنعة الجزئية نفسها مرات كثيرة. لذلك تبني التطبيقات أولاً تحويل زيتا على المجموعات الجزئية:
$$Z(S)=\sum_{A\subseteq S}\operatorname{dp}_{\mathrm{cur}}[A].$$
بعد تجهيز \(Z\) لكل \(S\subseteq\{0,\dots,L_c-1\}\)، يصبح كل انتقال مجرد قراءة واحدة من الجدول:
$$\operatorname{dp}_{\mathrm{next}}[b]=Z\!\left(\overline{\operatorname{Forb}(b)}\right).$$
ويُحسب هذا التحويل بمسح معياري على البتات في زمن \(O(L_c2^{L_c})\)، وهو الكلفة الغالبة في انتقال كل طبقة.
لا يحتاج الاثنا عشري الكامل إلى ملفات صفية اعتباطية، بل إلى عائلتين متكررتين فقط، وكلتاهما تُحسبان بمحرك العد الصفّي نفسه.
الأولى هي حزام متماثل ترتفع فيه أطوال الصفوف من \(n\) إلى \(2n-1\) ثم تعود إلى \(n\):
$$B_n=C(n,n+1,\dots,2n-1,2n-2,\dots,n).$$
والثانية هي سُلَّم زاوية ارتفاعه \(h-1\):
$$K_{n,h}=C(n-2,n-3,\dots,n-h).$$
وهكذا تُختزل الصعوبة الهندسية كلها إلى إعادة حساب هذه الأحزمة والسلالم الزاوية المعيارية.
لنرمز بـ \(Q(u,v)\) إلى العدد المخزن لحالة المركز المختزلة بعد نزع طبقات متساوية من الزوايا. تستخدم التطبيقات العلاقة
$$Q(u,0)=B_u,$$
$$Q(u,v)=\mathbf{1}_{(u,v)=(1,1)}+\sum_{w=0}^{u-1} Q(v,w)\,K_{u,u-w}^{\,6} \qquad (v>0).$$
وتأتي القوة السادسة من وجود ستة قطاعات زاوية متطابقة في الاثني عشري. ما إن يتحدد معامل الواجهة \(w\) حتى تصبح مساهمات هذه القطاعات الستة مستقلة، ولذلك تُضرب أعدادها بعضها في بعض. ثم تُستخرج القيمة النهائية من
$$A_n=2Q(n,n)-\mathbf{1}_{n=1}.$$
وهذه بالضبط هي الصيغة التي تنفذها تطبيقات C++ وPython وJava.
عندما \(n=1\)، يتكون الحزام المتماثل من صف واحد فقط طوله \(1\)، ولذلك \(B_1=C(1)=2\): إما أن يكون القناع فارغًا وإما أن يختار الموضع الوحيد. أما ملف الزاوية فهو فارغ، ومن ثم \(K_{1,1}=1\). لذا نحصل على
$$Q(1,1)=1+Q(1,0)\,K_{1,1}^{\,6}=1+2=3,$$
ومن ثم تكون القيمة النهائية
$$A_1=2\cdot 3-1=5.$$
وعندما \(n=2\)، يكون ملف الحزام هو \((2,3,2)\)، وتحسب التطبيقات
$$B_2=C(2,3,2)=19.$$
أما سلما الزاوية المطلوبان فكلاهما يساوي \(1\)، ومن ثم
$$Q(2,1)=Q(1,0)+Q(1,1)=2+3=5,$$
$$Q(2,2)=Q(2,0)+Q(2,1)=19+5=24,$$
وأخيرًا
$$A_2=2\cdot 24=48.$$
هاتان القيمتان الصغيرتان هما أيضًا نقطتا تحقق مستخدمتان داخل التطبيقات، ولذلك فهما مثال ممتاز على صحة الاشتقاق.
تتبع تطبيقات C++ وPython وJava المسار نفسه تمامًا. أولاً تُولِّد جميع الأقنعة الصالحة لكل عرض من \(0\) إلى \(2n-1\). بعد ذلك تُشغِّل البرمجة الديناميكية على ملفات الصفوف، وتخزن النتائج بحسب متتالية الأطوال حتى لا يُعاد حساب الحزام نفسه أو الزاوية نفسها أكثر من مرة. وفي كل انتقال تُبنى أولاً جدول مجموعات الأجزاء للصف الحالي، ثم يُملأ الصف التالي بمرور واحد على أقنعته الصالحة، وفي النهاية تُجمع القيم الموجودة على الصف الأخير.
وفوق طبقة الانتقال هذه، تحتفظ الشيفرة بقيم الأحزمة، وقيم الزوايا، وقيم العلاقة العودية ذات المعاملين. ولا يُستخدم الأس السريع بترديد \(M\) إلا عندما يجب رفع مساهمة الزوايا الست المتطابقة إلى القوة السادسة. وبما أن المسائل الفرعية نفسها تظهر مرارًا، فإن التخزين هو العامل الحاسم في إبقاء الطبقة العودية صغيرة وسريعة.
ليكن \(W=2n-1\) هو أعظم عرض لصف. إن توليد جميع الأقنعة الصالحة مسبقًا يكلف \(O(2^W)\) زمنًا وذاكرة. وبالنسبة إلى ملف صفّي واحد \((\ell_1,\dots,\ell_t)\)، فإن كلفة طبقة الانتقال تساوي
$$O\!\left(\sum_{i=1}^{t-1} \ell_i 2^{\ell_i}\right),$$
لأن كل انتقال بين طبقتين تهيمن عليه عملية zeta على جميع الأجزاء بعرض \(\ell_i\). أما مرحلة التجميع العودي ففيها \(O(n^2)\) حالات مخزنة، وكل حالة تجمع على الأكثر عبر \(u\) قيم للواجهة؛ ولذلك يصبح العمل الإضافي بعد توفر الملفات المخزنة \(O(n^3)\). عمليًا تبقى كلفة البرمجة الديناميكية على ملفات الصفوف هي الغالبة، بينما يساوي استهلاك الذاكرة \(O(2^W)\) للمصفوفات النشطة إضافةً إلى جداول التخزين.