We must compute \(L(6,10)\bmod 10^{10}\), where \(L(m,n)\) counts Eulerian-cycle structures on the rectangular graph defined in the problem. A naive search is hopeless: each lattice vertex admits many local pairings, and those local choices must remain globally compatible until the very end.
Process the lattice vertices in a fixed sweep order, column by column and inside each column from bottom to top. After some prefix of vertices has been processed, every already-handled local port has degree \(2\), so the processed subgraph is a disjoint union of paths and cycles.
The only information that can still affect the future is how the unfinished paths touch the current cut. Label the boundary stubs by \(0,1,\dots,B_v-1\). Each unfinished component hits the cut in exactly two stubs, so the entire past is encoded by a perfect matching
$$\sigma_v:\{0,\dots,B_v-1\}\to\{0,\dots,B_v-1\},\qquad \sigma_v(\sigma_v(i))=i,\ \sigma_v(i)\ne i.$$
The code stores this matching as a partner array state[i] = \sigma_v(i). No richer graph structure is required: once the partner of every open stub is known, the future can be processed exactly.
A lattice point may be adjacent to one, two, or four unit cells. Each adjacent cell contributes two local half-edges, so a corner vertex has \(2\) active ports, an edge vertex has \(4\), and an interior vertex has \(8\). The port names in the implementation are
$$E_L,E_U,N_R,N_L,W_U,W_L,S_L,S_R.$$
Because an Eulerian cycle must use every local incidence exactly once, the active ports at one vertex must be partitioned into disjoint pairs. The number of perfect pairings on \(2k\) labeled ports is
$$ (2k-1)!!=\frac{(2k)!}{2^k k!}. $$
Therefore the only local branching factors are
$$2\text{ ports } \to 1,\qquad 4\text{ ports } \to 3,\qquad 8\text{ ports } \to 105.$$
The program precomputes these pairing lists once in PairingCache.
Suppose a local pairing joins labels \(a\) and \(b\). There are exactly three cases.
Old-old. Both labels already belong to the incoming frontier. If \(\sigma(a)=b\), then this operation closes one component completely. Otherwise, if \(\sigma(a)=p_a\) and \(\sigma(b)=p_b\), removing \(a\) and \(b\) from the frontier forces \(p_a\) and \(p_b\) to become a new matched pair.
Old-new. If \(a\) is old and \(c\) is a newly created outgoing label, then the former partner \(\sigma(a)\) is transferred to \(c\).
New-new. Two outgoing labels are simply paired with each other.
This is exactly the logic implemented by apply_pair. After all local pairs are applied, the surviving outgoing labels are renumbered to form the next state \(\sigma_{v+1}\).
The target is one global Eulerian cycle, not several disconnected cycles. If a component closes before the final vertex, it no longer touches the frontier, so no later decision can merge it with the rest of the graph. Such a transition is therefore invalid.
Hence the dynamic program enforces:
$$\text{for non-final vertices: } \texttt{closed}=0.$$
At the very last vertex the opposite condition holds: we must finish with exactly one closure and no remaining frontier labels, i.e.
$$\text{final acceptance: } \texttt{closed}=1 \text{ and } B_{\mathrm{final}}=0.$$
Let \(D_v(\sigma)\) be the number of valid partial constructions after processing the first \(v\) sweep positions and ending in frontier state \(\sigma\). For the next vertex, define \(T_v(\sigma,\sigma')\) as the number of local pairings that transform \(\sigma\) into \(\sigma'\) without creating an illegal premature cycle. Then
$$D_{v+1}(\sigma')=\sum_{\sigma} D_v(\sigma)\,T_v(\sigma,\sigma') \pmod{10^{10}}.$$
This is a standard transfer-matrix / frontier-DP recurrence, but the state is not merely a bitmask: it is a matching on the cut, because connectivity matters.
The implementation rotates the rectangle so that \(n \le m\). This does not change \(L(m,n)\), but it minimizes the frontier width and therefore the number of states.
The arrays row_wires and prefix count how many old labels lie to the right of the current row, how many belong to the bottom slice, and how many belong to the left slice. From these counts the code can build, in \(O(1)\) per vertex, the exact map
$$\text{old labels} \longrightarrow \text{new labels after removing consumed ports and inserting outgoing ports}.$$
That is why the expensive part of the algorithm is the number of frontier states, not geometric bookkeeping.
The program validates several small instances before computing the target:
$$L(1,1)=1,\qquad L(1,2)=2,\qquad L(2,2)=37,\qquad L(3,3)=104290.$$
The first case is easy to visualize: a single cell forces one Eulerian cycle. The second case already shows why the DP is necessary: even a \(1\times2\) strip has multiple globally valid ways to wire the local pairings into a single cycle.
The code precomputes all perfect pairings of size \(2\), \(4\), and \(8\), then sweeps through the \((m+1)(n+1)\) lattice vertices. For each vertex it builds a VertexContext, iterates over all current states, applies every valid local pairing through process_state, and accumulates counts modulo \(10^{10}\) in the next hash map. Large DP layers may optionally be split across threads, but the mathematics is entirely the frontier-matching recurrence above.
If \(S_w\) denotes the number of reachable frontier matchings for width \(w=\min(m,n)\), then the total running time is roughly
$$O\big((m+1)(n+1)\cdot S_w \cdot 105\big),$$
because each vertex tests at most \(105\) local pairings per state. Memory usage is \(O(S_w)\). The exponential difficulty is entirely concentrated in \(S_w\), which is why rotating the rectangle to keep the smaller dimension as the width is crucial.
Gesucht ist \(L(6,10)\bmod 10^{10}\), wobei \(L(m,n)\) die Anzahl eulerscher Zyklusstrukturen auf dem im Problem definierten Rechteckgraphen bezeichnet. Ein direkter Bruteforce-Ansatz scheitert sofort: Jeder Gitterknoten erlaubt mehrere lokale Verpaarungen, und diese lokalen Entscheidungen müssen global bis zum Schluss konsistent bleiben.
Wir verarbeiten die Gitterknoten in fester Reihenfolge, spaltenweise und innerhalb einer Spalte von unten nach oben. Nachdem ein Präfix der Knoten abgearbeitet wurde, hat jeder bereits behandelte Port lokal Grad \(2\). Der verarbeitete Teilgraph ist also eine disjunkte Vereinigung von Pfaden und Zyklen.
Für die Zukunft relevant ist nur noch, wie die unfertigen Pfade den aktuellen Schnitt treffen. Bezeichne die offenen Randstubs mit \(0,1,\dots,B_v-1\). Jede unfertige Zusammenhangskomponente trifft den Schnitt in genau zwei Stubs, daher ist die gesamte Vergangenheit durch eine perfekte Paarung beschrieben:
$$\sigma_v:\{0,\dots,B_v-1\}\to\{0,\dots,B_v-1\},\qquad \sigma_v(\sigma_v(i))=i,\ \sigma_v(i)\ne i.$$
Im Code wird diese Paarung als Partner-Array state[i] = \sigma_v(i) gespeichert. Mehr Struktur braucht man nicht: Kennt man zu jedem offenen Stub den Partner, kann die Zukunft exakt weiterverarbeitet werden.
Ein Gitterpunkt kann an einer, zwei oder vier Einheitszellen liegen. Jede angrenzende Zelle liefert zwei lokale Halbkanten; daher hat ein Eckpunkt \(2\) aktive Ports, ein Randpunkt \(4\) und ein innerer Punkt \(8\). Die Portnamen im Code lauten
$$E_L,E_U,N_R,N_L,W_U,W_L,S_L,S_R.$$
Da ein Euler-Zyklus jede lokale Inzidenz genau einmal benutzen muss, werden die aktiven Ports am aktuellen Knoten paarweise verbunden. Die Anzahl perfekter Paarungen auf \(2k\) markierten Ports ist
$$ (2k-1)!!=\frac{(2k)!}{2^k k!}. $$
Damit entstehen genau die lokalen Verzweigungszahlen
$$2\text{ Ports } \to 1,\qquad 4\text{ Ports } \to 3,\qquad 8\text{ Ports } \to 105.$$
Diese Listen werden im Programm einmalig in PairingCache vorab erzeugt.
Verbinde lokal die Labels \(a\) und \(b\). Dann gibt es genau drei Fälle.
Alt-alt. Beide Labels gehören bereits zum eingehenden Frontier. Gilt \(\sigma(a)=b\), dann wird eine Komponente vollständig geschlossen. Andernfalls, mit \(\sigma(a)=p_a\) und \(\sigma(b)=p_b\), müssen nach dem Entfernen von \(a\) und \(b\) die ehemaligen Partner \(p_a\) und \(p_b\) neu gepaart werden.
Alt-neu. Ist \(a\) alt und \(c\) ein neu entstehendes ausgehendes Label, dann wird der frühere Partner \(\sigma(a)\) auf \(c\) übertragen.
Neu-neu. Zwei ausgehende Labels werden direkt miteinander gepaart.
Genau diese Logik steckt in apply_pair. Nach allen lokalen Paarungen werden die überlebenden ausgehenden Labels umnummeriert und bilden den nächsten Zustand \(\sigma_{v+1}\).
Gesucht ist genau ein globaler Euler-Zyklus, nicht mehrere getrennte Zyklen. Wenn sich vor dem letzten Knoten bereits eine Komponente schließt, berührt sie den Frontier nicht mehr und kann später nicht mehr mit dem Rest verbunden werden. Ein solcher Übergang ist also ungültig.
Daher fordert das DP:
$$\text{für nichtletzte Knoten: } \texttt{closed}=0.$$
Am allerletzten Knoten gilt das Gegenstück: Es muss genau ein Schließen stattfinden und es dürfen keine offenen Frontier-Labels übrig bleiben, also
$$\text{endgültige Akzeptanz: } \texttt{closed}=1 \text{ und } B_{\mathrm{final}}=0.$$
Sei \(D_v(\sigma)\) die Anzahl gültiger partieller Konstruktionen nach den ersten \(v\) Sweep-Positionen mit Frontier-Zustand \(\sigma\). Für den nächsten Knoten bezeichne \(T_v(\sigma,\sigma')\) die Anzahl lokaler Paarungen, die \(\sigma\) in \(\sigma'\) überführen, ohne einen unzulässigen vorzeitigen Zyklus zu erzeugen. Dann gilt
$$D_{v+1}(\sigma')=\sum_{\sigma} D_v(\sigma)\,T_v(\sigma,\sigma') \pmod{10^{10}}.$$
Das ist eine klassische Transfermatrix-/Frontier-DP-Gleichung, aber der Zustand ist nicht bloß eine Bitmaske, sondern eine Paarung auf dem Schnitt, weil Konnektivität wesentlich ist.
Die Implementierung rotiert das Rechteck so, dass \(n \le m\) gilt. Das ändert \(L(m,n)\) nicht, reduziert aber die Frontier-Breite und damit die Zustandszahl erheblich.
Die Arrays row_wires und prefix zählen, wie viele alte Labels rechts der aktuellen Zeile liegen, wie viele zur unteren Scheibe gehören und wie viele zur linken Scheibe gehören. Aus diesen Zahlen kann der Code in \(O(1)\) pro Knoten die exakte Abbildung konstruieren
$$\text{alte Labels} \longrightarrow \text{neue Labels nach Entfernen verbrauchter Ports und Einfügen ausgehender Ports}.$$
Deshalb dominiert nicht die Geometrie, sondern die Anzahl der Frontier-Zustände die Laufzeit.
Vor der Zielberechnung prüft das Programm mehrere kleine Fälle:
$$L(1,1)=1,\qquad L(1,2)=2,\qquad L(2,2)=37,\qquad L(3,3)=104290.$$
Der Fall \(L(1,1)=1\) ist direkt anschaulich: Eine einzelne Zelle erzwingt genau einen Euler-Zyklus. Bereits beim \(1\times2\)-Streifen sieht man aber, warum das DP nötig ist: Mehrere lokale Entscheidungen bleiben global gültig und führen zu verschiedenen Gesamtzyklen.
Der Code erzeugt zunächst alle perfekten Paarungen der Größen \(2\), \(4\) und \(8\). Danach sweeped er über die \((m+1)(n+1)\) Gitterknoten. Für jeden Knoten wird ein VertexContext aufgebaut; anschließend werden alle aktuellen Zustände durchlaufen, jede zulässige lokale Paarung in process_state angewendet und die Anzahl modulo \(10^{10}\) in der nächsten Hash-Map akkumuliert. Große DP-Schichten können optional über Threads verteilt werden, aber die mathematische Grundlage bleibt exakt die obige Matching-Rekurrenz.
Bezeichnet \(S_w\) die Anzahl erreichbarer Frontier-Paarungen bei Breite \(w=\min(m,n)\), so ist die Laufzeit näherungsweise
$$O\big((m+1)(n+1)\cdot S_w \cdot 105\big),$$
denn pro Knoten werden höchstens \(105\) lokale Paarungen pro Zustand geprüft. Der Speicherbedarf beträgt \(O(S_w)\). Die exponentielle Schwierigkeit sitzt vollständig in \(S_w\), daher ist die Rotation auf die kleinere Breite entscheidend.
İstenen değer \(L(6,10)\bmod 10^{10}\). Burada \(L(m,n)\), problemde tanımlanan dikdörtgen graf üzerindeki Euler çevrimi yapılarını sayar. Doğrudan arama pratik değildir; çünkü her kafes düğümünde birden fazla yerel eşleştirme vardır ve bu seçimlerin tümü son ana kadar küresel olarak uyumlu kalmalıdır.
Düğümleri sabit bir sırada, sütun sütun ve her sütunda aşağıdan yukarıya işleriz. İlk \(v\) konum işlendiğinde, işlenmiş bölgede her yerel portun derecesi artık \(2\) olur; dolayısıyla işlenmiş altgraf, ayrık yol ve çevrimlerin birleşimidir.
Geleceği etkileyebilecek tek bilgi, henüz tamamlanmamış yolların mevcut kesiti nerelerden deldiğidir. Sınır uçlarını \(0,1,\dots,B_v-1\) ile etiketleyelim. Tamamlanmamış her bileşen kesiti tam iki açık uçla keser; o halde geçmişin tamamı şu kusursuz eşleşme ile kodlanır:
$$\sigma_v:\{0,\dots,B_v-1\}\to\{0,\dots,B_v-1\},\qquad \sigma_v(\sigma_v(i))=i,\ \sigma_v(i)\ne i.$$
Kod bunu state[i] = \sigma_v(i) biçiminde bir partner dizisi olarak tutar. Daha zengin bir veri yapısına ihtiyaç yoktur: her açık ucun kiminle eşleştiğini bilmek, geleceği tam olarak işlemeye yeter.
Bir kafes noktası bir, iki ya da dört birim kareye komşu olabilir. Her komşu kare bu düğüme iki yerel yarım-kenar getirir; bu yüzden köşe düğümünde \(2\), kenar düğümünde \(4\), iç düğümde \(8\) aktif port vardır. Uygulamadaki port adları şunlardır:
$$E_L,E_U,N_R,N_L,W_U,W_L,S_L,S_R.$$
Bir Euler çevriminde her yerel temas tam bir kez kullanılacağı için, aktif portlar ikili çiftlere ayrılmalıdır. \(2k\) etiketli port üzerindeki kusursuz eşleşme sayısı
$$ (2k-1)!!=\frac{(2k)!}{2^k k!}. $$
Dolayısıyla yerel dallanma sayıları tam olarak
$$2\text{ port } \to 1,\qquad 4\text{ port } \to 3,\qquad 8\text{ port } \to 105$$
olur. Program bu listeleri bir kez PairingCache içinde önceden üretir.
Yerelde \(a\) ve \(b\) etiketlerini birleştirdiğimizi düşünelim. Tam üç durum vardır.
Eski-eski. Her iki etiket de gelen frontier üzerindedir. Eğer \(\sigma(a)=b\) ise bu işlem bir bileşeni tamamen kapatır. Aksi halde \(\sigma(a)=p_a\) ve \(\sigma(b)=p_b\) ise, \(a\) ve \(b\) kaldırıldıktan sonra eski partnerler \(p_a\) ve \(p_b\) yeni eş olur.
Eski-yeni. \(a\) eski, \(c\) yeni oluşturulan bir çıkış etiketi ise, \(a\)'nın eski partneri \(\sigma(a)\) artık \(c\)'ye aktarılır.
Yeni-yeni. İki yeni çıkış etiketi doğrudan birbirine eşlenir.
apply_pair fonksiyonu tam olarak bu mantığı uygular. Tüm yerel çiftler uygulandıktan sonra hayatta kalan çıkış etiketleri yeniden numaralandırılır ve bir sonraki durum \(\sigma_{v+1}\) oluşur.
Aradığımız nesne tek bir küresel Euler çevrimidir; birbirinden kopuk birden fazla çevrim değil. Eğer son düğüme gelmeden bir bileşen kapanırsa, artık frontier’a dokunmaz ve sonraki seçimlerle geri kalan kısımla birleştirilemez. Böyle bir geçiş geçersizdir.
Bu yüzden DP şu şartı koyar:
$$\text{son olmayan düğümlerde: } \texttt{closed}=0.$$
Son düğümde ise tam tersi gerekir: tam bir kapanış olmalı ve hiç açık frontier etiketi kalmamalıdır:
$$\text{nihai kabul: } \texttt{closed}=1 \text{ ve } B_{\mathrm{final}}=0.$$
\(D_v(\sigma)\), taramadaki ilk \(v\) konum işlendiğinde frontier durumu \(\sigma\) ile biten geçerli kısmi kurulumların sayısı olsun. Sonraki düğüm için \(T_v(\sigma,\sigma')\), \(\sigma\)'yı \(\sigma'\)'ya götüren ve yasak bir erken çevrim üretmeyen yerel eşleşme sayısı olsun. O zaman
$$D_{v+1}(\sigma')=\sum_{\sigma} D_v(\sigma)\,T_v(\sigma,\sigma') \pmod{10^{10}}.$$
Bu klasik bir transfer-matrix / frontier-DP bağıntısıdır; fakat durum sadece bir bitmask değildir. Kesit üzerindeki bağlantı yapısı da önemli olduğu için durum bir eşleşmedir.
Uygulama önce dikdörtgeni döndürüp \(n \le m\) olmasını sağlar. Bu, \(L(m,n)\)'yi değiştirmez ama frontier genişliğini küçültür; asıl kazanç buradan gelir.
row_wires ve prefix dizileri, mevcut satırın sağında kaç eski etiket bulunduğunu, alt dilime kaç etiket düştüğünü ve sol dilimde kaç etiket olduğunu sayar. Kod bu sayılardan hareketle her düğüm için \(O(1)\) sürede şu dönüşümü kurar:
$$\text{eski etiketler} \longrightarrow \text{tüketilen portlar atıldıktan ve yeni çıkış portları eklendikten sonraki yeni etiketler}.$$
Bu nedenle pahalı olan kısım geometri değil, erişilebilir frontier durumlarının sayısıdır.
Hedef hesaptan önce program şu küçük örnekleri doğrular:
$$L(1,1)=1,\qquad L(1,2)=2,\qquad L(2,2)=37,\qquad L(3,3)=104290.$$
\(L(1,1)=1\) kolayca görülebilir: tek bir hücre yalnızca bir Euler çevrimine izin verir. Ama \(1\times2\) şerit bile, yerel eşleştirmelerin küresel olarak farklı biçimde birleşebildiğini ve bu yüzden DP gerektiğini gösterir.
Kod önce \(2\), \(4\) ve \(8\) port için tüm kusursuz eşleşmeleri önceden üretir. Ardından \((m+1)(n+1)\) kafes düğümü üzerinde tarama yapar. Her düğümde bir VertexContext kurulur; sonra tüm mevcut durumlar gezilir, her geçerli yerel eşleşme process_state ile uygulanır ve sayılar modulo \(10^{10}\) olarak bir sonraki hash-map’te toplanır. Büyük DP katmanları isterse thread’lere bölünebilir, fakat matematiksel çekirdek tamamen yukarıdaki frontier-eşleşme bağıntısıdır.
\(w=\min(m,n)\) genişliği için erişilebilir frontier eşleşmesi sayısı \(S_w\) olsun. Toplam süre yaklaşık
$$O\big((m+1)(n+1)\cdot S_w \cdot 105\big)$$
olur; çünkü her düğümde her durum için en fazla \(105\) yerel eşleşme denenir. Bellek kullanımı \(O(S_w)\)'dir. Üstel zorluk tamamen \(S_w\)'da toplandığı için küçük kenarı genişlik seçmek kritiktir.
Debemos calcular \(L(6,10)\bmod 10^{10}\), donde \(L(m,n)\) cuenta las estructuras de ciclos eulerianos del grafo rectangular definido en el enunciado. La enumeración directa es inviable: cada vértice permite varias conexiones locales y esas decisiones deben seguir siendo compatibles globalmente hasta el final.
Procesamos los vértices en un orden fijo, columna por columna y dentro de cada columna de abajo arriba. Después de procesar los primeros \(v\) vértices, cada puerto ya tratado tiene grado local \(2\), así que la parte procesada es una unión disjunta de caminos y ciclos.
Lo único que puede influir en el futuro es cómo los caminos inacabados cortan la frontera actual. Etiquetamos los extremos abiertos como \(0,1,\dots,B_v-1\). Cada componente inacabado toca la frontera en exactamente dos extremos, así que todo el pasado queda resumido por un emparejamiento perfecto
$$\sigma_v:\{0,\dots,B_v-1\}\to\{0,\dots,B_v-1\},\qquad \sigma_v(\sigma_v(i))=i,\ \sigma_v(i)\ne i.$$
En el código ese emparejamiento se almacena como un vector de compañeros state[i] = \sigma_v(i). No hace falta guardar más información: saber con quién está conectado cada extremo abierto determina completamente la continuación.
Un punto de la retícula puede tocar una, dos o cuatro celdas unidad. Cada celda adyacente aporta dos semiaristas locales; por eso un vértice de esquina tiene \(2\) puertos activos, uno de borde tiene \(4\) y uno interior tiene \(8\). Los nombres de los puertos en la implementación son
$$E_L,E_U,N_R,N_L,W_U,W_L,S_L,S_R.$$
Como un ciclo euleriano debe usar exactamente una vez cada incidencia local, los puertos activos del vértice se deben particionar en pares. El número de emparejamientos perfectos sobre \(2k\) puertos etiquetados es
$$ (2k-1)!!=\frac{(2k)!}{2^k k!}. $$
Así obtenemos exactamente
$$2\text{ puertos } \to 1,\qquad 4\text{ puertos } \to 3,\qquad 8\text{ puertos } \to 105.$$
El programa precalcula estas listas una sola vez en PairingCache.
Supongamos que localmente unimos las etiquetas \(a\) y \(b\). Hay exactamente tres casos.
Viejo-viejo. Ambos pertenecen a la frontera entrante. Si \(\sigma(a)=b\), la componente se cierra por completo. Si no, con \(\sigma(a)=p_a\) y \(\sigma(b)=p_b\), al eliminar \(a\) y \(b\) los antiguos compañeros \(p_a\) y \(p_b\) deben quedar emparejados entre sí.
Viejo-nuevo. Si \(a\) es viejo y \(c\) es una etiqueta nueva saliente, entonces el antiguo compañero \(\sigma(a)\) se transfiere a \(c\).
Nuevo-nuevo. Dos etiquetas nuevas salientes se emparejan directamente.
Eso es exactamente lo que implementa apply_pair. Tras aplicar todas las parejas locales, las etiquetas salientes supervivientes se renombran y forman el siguiente estado \(\sigma_{v+1}\).
El objetivo es un único ciclo euleriano global, no varios ciclos desconectados. Si una componente se cierra antes del último vértice, deja de tocar la frontera y ninguna decisión futura puede fusionarla con el resto. Ese paso debe descartarse.
Por tanto el DP exige
$$\text{en vértices no finales: } \texttt{closed}=0.$$
En el último vértice ocurre lo contrario: debe producirse exactamente un cierre y no puede quedar ninguna etiqueta de frontera:
$$\text{aceptación final: } \texttt{closed}=1 \text{ y } B_{\mathrm{final}}=0.$$
Sea \(D_v(\sigma)\) el número de construcciones parciales válidas tras procesar las primeras \(v\) posiciones del barrido y terminar en el estado de frontera \(\sigma\). Para el siguiente vértice, definimos \(T_v(\sigma,\sigma')\) como el número de emparejamientos locales que transforman \(\sigma\) en \(\sigma'\) sin crear un ciclo prematuro ilegal. Entonces
$$D_{v+1}(\sigma')=\sum_{\sigma} D_v(\sigma)\,T_v(\sigma,\sigma') \pmod{10^{10}}.$$
Es una recurrencia típica de matriz de transferencia / frontier DP, pero el estado no es solo una máscara de bits: es un emparejamiento de conectividad sobre el corte.
La implementación rota el rectángulo para que \(n \le m\). Eso no cambia \(L(m,n)\), pero sí minimiza el ancho de frontera y, por tanto, el número de estados.
Los arreglos row_wires y prefix cuentan cuántas etiquetas viejas quedan a la derecha de la fila actual, cuántas pertenecen al bloque inferior y cuántas al bloque izquierdo. Con esas cantidades, el código construye en \(O(1)\) por vértice el mapa exacto
$$\text{etiquetas viejas} \longrightarrow \text{etiquetas nuevas tras eliminar puertos consumidos e insertar puertos salientes}.$$
Por eso el verdadero coste no está en la geometría, sino en cuántos estados de frontera alcanzables existen.
Antes del cálculo final, el programa verifica varios casos pequeños:
$$L(1,1)=1,\qquad L(1,2)=2,\qquad L(2,2)=37,\qquad L(3,3)=104290.$$
El caso \(L(1,1)=1\) se ve directamente: una sola celda fuerza un único ciclo euleriano. El caso \(1\times2\) ya muestra por qué hace falta el DP: hay varias maneras locales distintas que siguen siendo globalmente válidas.
El código precalcula todos los emparejamientos perfectos de tamaño \(2\), \(4\) y \(8\), y luego barre los \((m+1)(n+1)\) vértices de la retícula. En cada vértice construye un VertexContext, recorre todos los estados actuales, aplica cada emparejamiento local válido mediante process_state y acumula los conteos módulo \(10^{10}\) en la siguiente tabla hash. Las capas grandes pueden dividirse opcionalmente entre hilos, pero el núcleo matemático sigue siendo exactamente la recurrencia de emparejamientos de frontera.
Si \(S_w\) es el número de emparejamientos de frontera alcanzables para ancho \(w=\min(m,n)\), el tiempo total es aproximadamente
$$O\big((m+1)(n+1)\cdot S_w \cdot 105\big),$$
porque cada vértice prueba como mucho \(105\) emparejamientos locales por estado. La memoria es \(O(S_w)\). La dificultad exponencial está concentrada por completo en \(S_w\); por eso es tan importante rotar el rectángulo para que el ancho sea la dimensión menor.
目标是计算 \(L(6,10)\bmod 10^{10}\)。其中 \(L(m,n)\) 表示题目所定义矩形图上的欧拉回路结构数。直接枚举完全不可行，因为每个格点都有多种局部连接方式，而这些局部选择必须一直保持全局兼容。
按固定顺序扫描格点，逐列处理，并且每列从下往上。当前 \(v\) 个位置处理完后，所有已处理局部端口的度都已经是 \(2\)，因此已处理部分一定是若干条路径和若干个回路的并。
未来仍然可能受影响的信息，只有这些未完成路径如何穿过当前切面。把切面上的开放端点标成 \(0,1,\dots,B_v-1\)。每个未完成连通块恰好在切面上留下两个开放端点，所以整个历史可以浓缩成一个完美匹配
$$\sigma_v:\{0,\dots,B_v-1\}\to\{0,\dots,B_v-1\},\qquad \sigma_v(\sigma_v(i))=i,\ \sigma_v(i)\ne i.$$
代码把这个匹配存成伙伴数组 state[i] = \sigma_v(i)。这就足够了；只要知道每个开放端点当前和谁连在一起，就能精确继续处理后面的部分。
一个格点可能接触一格、两格或四格单位小方块。每个相邻小方块向该点贡献两个局部半边，所以角点有 \(2\) 个活动端口，边界点有 \(4\) 个，内部点有 \(8\) 个。程序中这八个端口记为
$$E_L,E_U,N_R,N_L,W_U,W_L,S_L,S_R.$$
欧拉回路要求每次局部接触都被恰好使用一次，因此当前顶点的所有活动端口必须两两配对。\(2k\) 个带标号端口的完美匹配数量为
$$ (2k-1)!!=\frac{(2k)!}{2^k k!}. $$
因此局部分支数正好是
$$2\text{ 个端口 } \to 1,\qquad 4\text{ 个端口 } \to 3,\qquad 8\text{ 个端口 } \to 105.$$
程序把这些配对列表预先生成并缓存在 PairingCache 中。
设某次局部配对把标签 \(a\) 与 \(b\) 接起来。只会出现三种情况。
旧-旧。 两个标签都来自输入前沿。如果 \(\sigma(a)=b\)，那么这一步会把一个连通块完全闭合。如果不是，设 \(\sigma(a)=p_a\)、\(\sigma(b)=p_b\)，那么删去 \(a,b\) 之后，旧伙伴 \(p_a,p_b\) 必须互相配对。
旧-新。 如果 \(a\) 是旧标签而 \(c\) 是新生成的输出标签，那么 \(\sigma(a)\) 会被转接到 \(c\)。
新-新。 两个新的输出标签直接互相配对。
apply_pair 实现的正是这三条规则。全部局部配对完成后，幸存的输出标签重新编号，形成下一层状态 \(\sigma_{v+1}\)。
目标是一个全局唯一的欧拉回路，而不是若干个互不相连的小回路。如果某个连通块在最后一个顶点之前就闭合，它就不再接触前沿，后续决策也无法再把它和剩余部分连起来。因此这种转移必然无效。
所以动态规划要求
$$\text{非最终顶点时: } \texttt{closed}=0.$$
到了最后一个顶点，条件反过来：必须恰好发生一次闭合，而且不能剩余任何前沿标签，即
$$\text{最终接受条件: } \texttt{closed}=1 \text{ 且 } B_{\mathrm{final}}=0.$$
记 \(D_v(\sigma)\) 为扫描前 \(v\) 个位置后、处于前沿状态 \(\sigma\) 的合法部分构造数。对下一个顶点，令 \(T_v(\sigma,\sigma')\) 表示把 \(\sigma\) 变成 \(\sigma'\) 且不产生非法过早闭环的局部配对数，则有
$$D_{v+1}(\sigma')=\sum_{\sigma} D_v(\sigma)\,T_v(\sigma,\sigma') \pmod{10^{10}}.$$
这就是标准的 transfer-matrix / frontier DP 递推。但这里的状态不只是位掩码，而是切面上的配对结构，因为“谁和谁连通”本身就是核心信息。
实现首先交换维度，使 \(n \le m\)。这不会改变 \(L(m,n)\)，但会减小前沿宽度，从而显著减少状态数。
row_wires 和 prefix 这两个数组分别统计当前行右侧的旧标签数量、底部切片中的标签数量、以及左侧切片中的标签数量。有了这些计数，代码就能在每个顶点用 \(O(1)\) 时间构造精确映射
$$\text{旧标签} \longrightarrow \text{删去已消费端口并插入新输出端口后的新标签}.$$
因此真正昂贵的部分不是几何索引，而是可达前沿状态的总数。
正式计算目标前，程序先验证若干小实例：
$$L(1,1)=1,\qquad L(1,2)=2,\qquad L(2,2)=37,\qquad L(3,3)=104290.$$
\(L(1,1)=1\) 很容易理解：单个方格只能形成一个欧拉回路。\(1\times2\) 的情形则已经说明了为什么必须做动态规划，因为不同的局部配对仍可能演化成不同的全局合法回路。
代码先预生成大小为 \(2\)、\(4\)、\(8\) 的所有完美配对，然后扫描 \((m+1)(n+1)\) 个格点。对每个格点建立一个 VertexContext，遍历当前所有前沿状态，用 process_state 应用每个合法局部配对，并把结果按模 \(10^{10}\) 累加到下一层哈希表中。对于很大的 DP 层，程序还可以选择并行拆分，但数学核心始终是上面的前沿匹配递推。
若 \(w=\min(m,n)\) 时可达前沿匹配数为 \(S_w\)，则总时间大致为
$$O\big((m+1)(n+1)\cdot S_w \cdot 105\big),$$
因为每个顶点对每个状态最多检查 \(105\) 种局部配对。空间复杂度是 \(O(S_w)\)。指数级困难完全集中在 \(S_w\) 上，所以把较短边当作宽度是关键优化。
Нужно вычислить \(L(6,10)\bmod 10^{10}\), где \(L(m,n)\) считает структуры эйлеровых циклов на прямоугольном графе из условия. Прямой перебор невозможен: в каждой вершине много локальных способов соединить порты, и все эти локальные решения должны оставаться глобально согласованными до самого конца.
Обрабатываем вершины в фиксированном порядке: по столбцам, а внутри столбца снизу вверх. После обработки первых \(v\) позиций каждый уже рассмотренный локальный порт имеет степень \(2\), поэтому обработанная часть графа представляет собой объединение непересекающихся путей и циклов.
На будущее влияет только то, как незавершённые пути пересекают текущий разрез. Пометим открытые концы на разрезе числами \(0,1,\dots,B_v-1\). Каждая незавершённая компонента касается разреза ровно в двух концах, поэтому вся прошлaя информация сжимается в совершенное паросочетание
$$\sigma_v:\{0,\dots,B_v-1\}\to\{0,\dots,B_v-1\},\qquad \sigma_v(\sigma_v(i))=i,\ \sigma_v(i)\ne i.$$
В коде это хранится как массив партнёров state[i] = \sigma_v(i). Этого достаточно: если известно, с кем соединён каждый открытый конец, будущее однозначно обрабатывается без потери информации.
Точка решётки может прилегать к одной, двум или четырём единичным клеткам. Каждая соседняя клетка даёт два локальных полуребра, поэтому у угловой вершины \(2\) активных порта, у граничной \(4\), а у внутренней \(8\). В программе порты обозначены так:
$$E_L,E_U,N_R,N_L,W_U,W_L,S_L,S_R.$$
Поскольку эйлеров цикл должен использовать каждую локальную инцидентность ровно один раз, активные порты данной вершины надо разбить на пары. Число совершенных попариваний на \(2k\) помеченных портах равно
$$ (2k-1)!!=\frac{(2k)!}{2^k k!}. $$
Поэтому локальные ветвления имеют ровно такие размеры:
$$2\text{ порта } \to 1,\qquad 4\text{ порта } \to 3,\qquad 8\text{ портов } \to 105.$$
Эти списки попариваний код заранее строит в PairingCache.
Пусть локально соединяются метки \(a\) и \(b\). Возможны ровно три случая.
Старый-старый. Обе метки уже лежат на входном фронте. Если \(\sigma(a)=b\), то компонентa полностью замыкается. Иначе, если \(\sigma(a)=p_a\) и \(\sigma(b)=p_b\), то после удаления \(a\) и \(b\) старые партнёры \(p_a\) и \(p_b\) должны стать новой парой.
Старый-новый. Если \(a\) старый, а \(c\) новый исходящий ярлык, то прежний партнёр \(\sigma(a)\) переносится на \(c\).
Новый-новый. Два новых исходящих ярлыка просто соединяются друг с другом.
Именно это делает функция apply_pair. После применения всех локальных пар оставшиеся исходящие ярлыки перенумеровываются и образуют следующее состояние \(\sigma_{v+1}\).
Нужен один глобальный эйлеров цикл, а не несколько несвязанных циклов. Если какая-то компонента замкнулась до последней вершины, она больше не касается фронта и уже никогда не сможет соединиться с остальной частью графа. Значит, такой переход недопустим.
Поэтому DP требует
$$\text{для не последней вершины: } \texttt{closed}=0.$$
В самой последней вершине условие меняется на противоположное: должно произойти ровно одно замыкание, и никаких открытых ярлыков на фронте не должно остаться:
$$\text{финальное принятие: } \texttt{closed}=1 \text{ и } B_{\mathrm{final}}=0.$$
Обозначим через \(D_v(\sigma)\) число допустимых частичных построений после первых \(v\) позиций обхода с frontier-состоянием \(\sigma\). Для следующей вершины пусть \(T_v(\sigma,\sigma')\) — число локальных попариваний, переводящих \(\sigma\) в \(\sigma'\) без недопустимого преждевременного замыкания. Тогда
$$D_{v+1}(\sigma')=\sum_{\sigma} D_v(\sigma)\,T_v(\sigma,\sigma') \pmod{10^{10}}.$$
Это стандартная frontier-DP / transfer-matrix рекурсия, но состояние здесь не просто битовая маска: это именно паросочетание на разрезе, потому что важна структура связности.
Реализация сначала поворачивает прямоугольник так, чтобы \(n \le m\). Значение \(L(m,n)\) от этого не меняется, но ширина фронта уменьшается, а вместе с ней и число состояний.
Массивы row_wires и prefix считают, сколько старых меток лежит справа от текущей строки, сколько относится к нижнему слою и сколько к левому слою. Из этих чисел код за \(O(1)\) на вершину строит точное отображение
$$\text{старые метки} \longrightarrow \text{новые метки после удаления использованных портов и добавления исходящих портов}.$$
Поэтому узкое место алгоритма — не геометрия, а число достижимых frontier-состояний.
Перед вычислением ответа программа проверяет несколько малых случаев:
$$L(1,1)=1,\qquad L(1,2)=2,\qquad L(2,2)=37,\qquad L(3,3)=104290.$$
Случай \(L(1,1)=1\) легко увидеть вручную: одна клетка допускает ровно один эйлеров цикл. Уже полоска \(1\times2\) показывает, почему нужен DP: разные локальные попаривания могут вести к разным корректным глобальным циклам.
Код заранее генерирует все совершенные попаривания размеров \(2\), \(4\) и \(8\), после чего проходит по \((m+1)(n+1)\) вершинам решётки. Для каждой вершины создаётся VertexContext; затем перебираются все текущие состояния, каждое допустимое локальное попаривание применяется в process_state, а счётчики по модулю \(10^{10}\) накапливаются в следующем хеш-словаре. Большие слои DP при желании разбиваются по потокам, но математическая суть остаётся той же frontier-рекурсией по паросочетаниям.
Если \(S_w\) — число достижимых frontier-паросочетаний при ширине \(w=\min(m,n)\), то полное время работы примерно равно
$$O\big((m+1)(n+1)\cdot S_w \cdot 105\big),$$
потому что в каждой вершине для каждого состояния проверяется не более \(105\) локальных попариваний. Память равна \(O(S_w)\). Вся экспоненциальная трудность сосредоточена в \(S_w\), поэтому поворот к меньшей ширине критически важен.
نريد حساب \(L(6,10)\bmod 10^{10}\)، حيث تمثل \(L(m,n)\) عدد البنى ذات الدورات الأويلرية على الرسم المستطيلي المعرَّف في المسألة. التعداد المباشر مستحيل عمليًا، لأن كل عقدة شبكية تسمح بعدة توصيلات محلية، وهذه الاختيارات المحلية يجب أن تبقى متوافقة عالميًا حتى النهاية.
نعالج العقد بترتيب ثابت: عمودًا بعد عمود، وداخل كل عمود من الأسفل إلى الأعلى. بعد معالجة أول \(v\) مواضع، تكون كل المنافذ المحلية المعالجة قد حصلت على درجة \(2\)، لذلك يصبح الجزء المعالج اتحادًا منفصلًا من مسارات ودورات.
المعلومة الوحيدة التي قد تؤثر في المستقبل هي كيفية ملامسة المسارات غير المكتملة لخط القطع الحالي. نرقم النهايات المفتوحة على هذا الحد بـ \(0,1,\dots,B_v-1\). كل مكوّن غير مكتمل يقطع الحد في نهايتين فقط، ولذلك يمكن ضغط الماضي كله في مطابقة كاملة
$$\sigma_v:\{0,\dots,B_v-1\}\to\{0,\dots,B_v-1\},\qquad \sigma_v(\sigma_v(i))=i,\ \sigma_v(i)\ne i.$$
الكود يخزن هذه المطابقة في مصفوفة شركاء من الشكل state[i] = \sigma_v(i). لا نحتاج إلى بنية أغنى من ذلك؛ فمعرفة شريك كل نهاية مفتوحة تكفي لمتابعة الحساب بدقة.
قد تكون نقطة الشبكة مجاورة لخلية واحدة أو خليتين أو أربع خلايا. كل خلية مجاورة تضيف نصفَي ضلع محليين، لذلك تمتلك العقدة الركنية \(2\) منفذًا نشطًا، والعقدة الحدّية \(4\)، والعقدة الداخلية \(8\). أسماء المنافذ في التطبيق هي
$$E_L,E_U,N_R,N_L,W_U,W_L,S_L,S_R.$$
ولأن الدورة الأويلرية يجب أن تستعمل كل تماس محلي مرة واحدة بالضبط، فلا بد من تقسيم المنافذ النشطة إلى أزواج. عدد المطابقات الكاملة على \(2k\) منفذًا معلَّمًا هو
$$ (2k-1)!!=\frac{(2k)!}{2^k k!}. $$
ومن ثم تكون أعداد التفرعات المحلية بالضبط
$$2\text{ منفذ } \to 1,\qquad 4\text{ منافذ } \to 3,\qquad 8\text{ منافذ } \to 105.$$
ولهذا يقوم البرنامج بتوليد هذه القوائم مرة واحدة داخل PairingCache.
لنفترض أن التوصيل المحلي يربط الوسمين \(a\) و\(b\). توجد ثلاث حالات فقط.
قديم-قديم. كلا الوسمين موجودان أصلًا على الحد الداخل. إذا كان \(\sigma(a)=b\)، فهذا يعني أن مكوّنًا كاملاً قد أُغلق. وإذا لم يكن كذلك، ولنا \(\sigma(a)=p_a\) و\(\sigma(b)=p_b\)، فإن حذف \(a\) و\(b\) يفرض أن يصبح \(p_a\) و\(p_b\) زوجًا جديدًا.
قديم-جديد. إذا كان \(a\) وسمًا قديمًا و\(c\) وسمًا جديدًا خارجًا، فإن الشريك السابق \(\sigma(a)\) يُنقل إلى \(c\).
جديد-جديد. يُقترن الوسمان الجديدان مباشرة معًا.
هذا بالضبط ما تنفذه الدالة apply_pair. وبعد تطبيق جميع الأزواج المحلية، يُعاد ترقيم الوسوم الخارجة الباقية لتشكيل الحالة التالية \(\sigma_{v+1}\).
المطلوب دورة أويلرية عالمية واحدة، لا عدة دورات منفصلة. إذا أُغلق مكوّن قبل الوصول إلى العقدة الأخيرة، فلن يعود يلامس الحد، وبالتالي لن تتمكن أي قرارات لاحقة من دمجه مع بقية الرسم. لذلك يكون هذا الانتقال غير صالح.
ولهذا يفرض البرمجة الديناميكية الشرط
$$\text{في العقد غير النهائية: } \texttt{closed}=0.$$
أما في العقدة الأخيرة فينعكس الشرط: يجب أن يحدث إغلاق واحد بالضبط، وألا يبقى أي وسم مفتوح على الحد:
$$\text{القبول النهائي: } \texttt{closed}=1 \text{ و } B_{\mathrm{final}}=0.$$
ليكن \(D_v(\sigma)\) عدد التركيبات الجزئية الصحيحة بعد معالجة أول \(v\) مواضع من المسح مع حالة حد \(\sigma\). وللعقدة التالية، ليكن \(T_v(\sigma,\sigma')\) عدد الاقترانات المحلية التي تحول \(\sigma\) إلى \(\sigma'\) من دون تكوين دورة مبكرة غير مسموح بها. عندئذٍ
$$D_{v+1}(\sigma')=\sum_{\sigma} D_v(\sigma)\,T_v(\sigma,\sigma') \pmod{10^{10}}.$$
هذه علاقة انتقال قياسية من نوع transfer-matrix / frontier-DP، لكن الحالة هنا ليست قناع بتات بسيطًا؛ بل هي مطابقة على الحد، لأن بنية الاتصال نفسها مهمة.
تقوم الخوارزمية أولًا بتدوير المستطيل بحيث يصبح \(n \le m\). هذا لا يغيّر قيمة \(L(m,n)\)، لكنه يقلل عرض الحد، وبالتالي يقلل عدد الحالات بشكل كبير.
المصفوفتان row_wires وprefix تحسبان عدد الوسوم القديمة الواقعة إلى يمين الصف الحالي، وعدد الوسوم التابعة للشريحة السفلية، وعدد الوسوم التابعة للشريحة اليسرى. ومن هذه الأعداد يستطيع الكود بناء التحويل الدقيق في \(O(1)\) لكل عقدة:
$$\text{الوسوم القديمة} \longrightarrow \text{الوسوم الجديدة بعد حذف المنافذ المستهلكة وإدراج المنافذ الخارجة}.$$
لذلك فإن الكلفة الحقيقية ليست في الترتيب الهندسي، بل في عدد حالات الحد الممكنة.
قبل حساب الجواب النهائي، يتحقق البرنامج من عدة حالات صغيرة:
$$L(1,1)=1,\qquad L(1,2)=2,\qquad L(2,2)=37,\qquad L(3,3)=104290.$$
الحالة \(L(1,1)=1\) واضحة بصريًا: خلية واحدة تفرض دورة أويلرية واحدة فقط. لكن حتى الشريط \(1\times2\) يبيّن لماذا نحتاج إلى DP، لأن هناك أكثر من توصيل محلي يبقى صالحًا عالميًا.
يولد الكود مسبقًا جميع المطابقات الكاملة للأحجام \(2\) و\(4\) و\(8\)، ثم يمسح عقد الشبكة وعددها \((m+1)(n+1)\). عند كل عقدة يبني VertexContext، ثم يمر على كل الحالات الحالية، ويطبّق كل اقتران محلي صالح بواسطة process_state، ويجمع النتائج بترديد \(10^{10}\) في جدول تجزئة للحالة التالية. يمكن تقسيم الطبقات الكبيرة على عدة خيوط عند الحاجة، لكن الجوهر الرياضي يبقى تمامًا علاقة مطابقة الحدود المذكورة أعلاه.
إذا كان \(S_w\) هو عدد مطابقات الحد الممكنة عند العرض \(w=\min(m,n)\)، فإن زمن التنفيذ الكلي يقارب
$$O\big((m+1)(n+1)\cdot S_w \cdot 105\big),$$
لأن كل عقدة تختبر في أسوأ الأحوال \(105\) اقترانات محلية لكل حالة. أما الذاكرة فهي \(O(S_w)\). وتتركز الصعوبة الأسية كلها في \(S_w\)، ولهذا فإن جعل البعد الأصغر هو عرض الحد خطوة حاسمة.