The problem asks for the number \(S(n)\) of ways to assign to every vertex of a \(2\times 2n\) strip with a twisted wrap-around one of its three incident directions: left, right, or the vertical edge joining the two rows in the same column. An edge contributes \(1\) to the score when both of its endpoints choose each other, and we want the total score to be exactly \(n\). The answer is required modulo \(998244353\).
A direct enumeration would inspect \(3^{4n}\) global assignments, because the strip has \(4n\) vertices and each vertex has three local options. The implementations avoid that exponential blow-up by processing the strip column by column and keeping only the boundary information that can still influence future mutual matches.
The key observation is that once we cut the strip between two consecutive columns, the future only needs to know which horizontal choices are still waiting for a reciprocal answer from the next column. That turns the entire problem into a finite-state dynamic program with a score counter.
Each column contains two vertices, one in the top row and one in the bottom row. Each vertex chooses exactly one of three directions:
$$L,\qquad R,\qquad V.$$
Here \(L\) means “choose the neighbor in the previous column”, \(R\) means “choose the neighbor in the next column”, and \(V\) means “choose the vertex in the other row of the same column”. Since the top and bottom vertices act independently, each column has
$$3^2=9$$
local configurations.
A score point appears only when an edge is chosen from both ends. A horizontal edge is counted when the previous column pointed right on some row and the current column answers left on the same row. A vertical edge is counted when both vertices of the current column choose \(V\).
Cut the strip between two adjacent columns. At that boundary we only need to know whether the top row and the bottom row already have a pending right-pointing choice coming from the left. Represent that by a state
$$m=(a,b)\in\{0,1\}^2,$$
where \(a=1\) means “the top row is waiting for a left answer” and \(b=1\) means the same for the bottom row. So there are only four possible boundary states.
If the current column chooses directions \(x,y\in\{L,R,V\}\) for the top and bottom vertices, then the score increment is
$$\Delta(m;x,y)=[x=L]a+[y=L]b+[x=V\land y=V].$$
The outgoing state records which rows now point to the right:
$$m'=([x=R],[y=R]).$$
For a fixed incoming state \(m\), many of the 9 local pairs \((x,y)\) lead to the same outgoing state and the same score increment. Therefore the implementations precompute only the multiplicity
$$T_{\mathrm{mid}}(m,m',d)=\#\{(x,y)\in\{L,R,V\}^2:\ m'=([x=R],[y=R]),\ \Delta(m;x,y)=d\}.$$
Because \(d\in\{0,1,2\}\), each incoming state has only a small number of distinct transition classes.
For example, when \(m=(0,0)\), the only way to score \(1\) inside the column is the pair \((V,V)\), while the other eight local assignments merely open or leave unmatched horizontal choices. The aggregated counts are
$$\begin{aligned} T_{\mathrm{mid}}((0,0),(0,0),0)&=3,\\ T_{\mathrm{mid}}((0,0),(0,0),1)&=1,\\ T_{\mathrm{mid}}((0,0),(1,0),0)&=2,\\ T_{\mathrm{mid}}((0,0),(0,1),0)&=2,\\ T_{\mathrm{mid}}((0,0),(1,1),0)&=1. \end{aligned}$$
Choose a seam where the strip is cut open and fix its boundary state \(m_0\). Let \(D_j^{(m_0)}(m,k)\) denote the number of ways to process the first \(j\) columns so that the current boundary state is \(m\) and the accumulated score is \(k\).
The initial condition is
$$D_0^{(m_0)}(m,k)=\begin{cases}1,&m=m_0\text{ and }k=0,\\0,&\text{otherwise.}\end{cases}$$
For every ordinary column, each transition class contributes according to
$$D_{j+1}^{(m_0)}(m',k+d)\leftarrow D_{j+1}^{(m_0)}(m',k+d)+D_j^{(m_0)}(m,k)\,T_{\mathrm{mid}}(m,m',d).$$
This recurrence is the whole reason the method is fast: the exponentially many global configurations collapse to a quadratic-time dynamic program on four boundary states and one score axis.
The final column is special because the strip closes with a twist. A right-pointing choice from the top row returns to the bottom row at the seam, and a right-pointing choice from the bottom row returns to the top row. So the last-column transition table is
$$T_{\mathrm{last}}(m,m',d)=\#\{(x,y)\in\{L,R,V\}^2:\ m'=([y=R],[x=R]),\ \Delta(m;x,y)=d\}.$$
After applying that twisted update, a complete configuration is valid only if it returns to the same seam state and reaches total score \(n\). Summing over the four possible seam states yields
$$S(n)=\sum_{m_0\in\{0,1\}^2} D_{2n}^{(m_0)}(m_0,n)\pmod{998244353}.$$
When \(n=1\), the strip has \(2\) columns and the target score is \(1\). Start with seam state \(m_0=(0,0)\). For the first column, the five transition classes listed above occur with multiplicities \(3,1,2,2,1\).
To finish with total score \(1\) and return to \(m_0=(0,0)\) after the twisted last column, the valid combinations contribute
$$3\cdot 1+1\cdot 3+2\cdot 3+2\cdot 3+1\cdot 3=21.$$
Repeating the same calculation for the other seam states gives
$$m_0=(1,0)\Rightarrow 11,\qquad m_0=(0,1)\Rightarrow 11,\qquad m_0=(1,1)\Rightarrow 5.$$
Therefore
$$S(1)=21+11+11+5=48,$$
which matches the first checkpoint used by the implementation.
The C++, Python, and Java implementations begin by enumerating the 9 local choices for each of the 4 incoming boundary states. They compress those raw possibilities into two tiny transition tables: one for ordinary columns and one for the twisted final column. This preprocessing takes constant time, but it removes repeated case analysis from the main loop.
Next, for each possible seam state, the implementation runs a layered dynamic program indexed by the current boundary state and the accumulated score. Only two layers are stored at any moment, because each column depends only on the previous one. After \(2n-1\) ordinary updates, one last twisted update is applied, and the entry that returns to the starting seam state with score exactly \(n\) is added to the final total.
All arithmetic is performed modulo \(998244353\). The three language versions implement the same recurrence and differ only in syntax and data-structure spelling.
The number of boundary states is fixed at \(4\), the score axis has length \(n+1\), and there are \(2n\) columns. Each state has only a constant number of aggregated transitions, so the total running time is \(O(n^2)\). The rolling-array dynamic program stores only two layers of size \(4\times(n+1)\), so the memory usage is \(O(n)\).
Gesucht ist die Anzahl \(S(n)\) aller Möglichkeiten, auf einem \(2\times 2n\)-Streifen mit verdrilltem Abschluss jedem Knoten genau eine seiner drei inzidenten Richtungen zuzuweisen: links, rechts oder die vertikale Kante zur anderen Zeile derselben Spalte. Eine Kante liefert genau dann einen Punkt, wenn beide Endpunkte einander wählen, und die Gesamtpunktzahl soll genau \(n\) sein. Das Ergebnis wird modulo \(998244353\) verlangt.
Eine direkte Enumeration würde \(3^{4n}\) globale Belegungen betrachten, denn der Streifen besitzt \(4n\) Knoten und jeder Knoten hat drei lokale Optionen. Die Implementierungen vermeiden diese exponentielle Explosion, indem sie spaltenweise arbeiten und nur die Randinformation behalten, die spätere wechselseitige Treffer noch beeinflussen kann.
Die zentrale Beobachtung ist: Schneidet man den Streifen zwischen zwei benachbarten Spalten auf, dann muss man für die Zukunft nur wissen, welche horizontalen Wahlen noch auf eine passende Gegenwahl aus der nächsten Spalte warten. Dadurch wird das Problem zu einer Dynamik auf endlich vielen Zuständen mit zusätzlicher Punktezählung.
Jede Spalte enthält zwei Knoten, einen oben und einen unten. Jeder Knoten wählt genau eine von drei Richtungen:
$$L,\qquad R,\qquad V.$$
Dabei bedeutet \(L\) „wähle den Nachbarn in der vorherigen Spalte“, \(R\) „wähle den Nachbarn in der nächsten Spalte“ und \(V\) „wähle den Knoten in der anderen Zeile derselben Spalte“. Weil obere und untere Wahl unabhängig sind, besitzt jede Spalte
$$3^2=9$$
lokale Konfigurationen.
Ein Punkt entsteht nur dann, wenn eine Kante von beiden Seiten gewählt wird. Horizontal geschieht das, wenn die vorherige Spalte in einer Zeile nach rechts zeigte und die aktuelle Spalte in derselben Zeile nach links antwortet. Vertikal geschieht es genau dann, wenn beide Knoten der aktuellen Spalte \(V\) wählen.
Wir schneiden den Streifen zwischen zwei benachbarten Spalten. An dieser Grenze ist nur relevant, ob in der oberen bzw. unteren Zeile bereits eine nach rechts gerichtete Wahl von links kommt, die noch beantwortet werden kann. Das kodieren wir durch den Zustand
$$m=(a,b)\in\{0,1\}^2,$$
wobei \(a=1\) bedeutet: „oben wartet bereits eine linke Antwort“, und \(b=1\) analog für die untere Zeile. Es gibt also nur vier mögliche Randzustände.
Wählt die aktuelle Spalte die Richtungen \(x,y\in\{L,R,V\}\) für oberen und unteren Knoten, so ist der Punktezuwachs
$$\Delta(m;x,y)=[x=L]a+[y=L]b+[x=V\land y=V].$$
Der ausgehende Zustand merkt sich, welche Zeilen nun nach rechts zeigen:
$$m'=([x=R],[y=R]).$$
Für einen festen eingehenden Zustand \(m\) führen viele der 9 lokalen Paare \((x,y)\) zum selben ausgehenden Zustand und zum selben Punktezuwachs. Deshalb berechnet die Implementierung nur die Multiplizität
$$T_{\mathrm{mid}}(m,m',d)=\#\{(x,y)\in\{L,R,V\}^2:\ m'=([x=R],[y=R]),\ \Delta(m;x,y)=d\}.$$
Da \(d\in\{0,1,2\}\) liegt, hat jeder eingehende Zustand nur wenige verschiedene Übergangsklassen.
Für \(m=(0,0)\) gibt es beispielsweise genau einen lokalen Fall mit Zuwachs \(1\), nämlich \((V,V)\); die übrigen acht Fälle eröffnen nur horizontale Erwartungen oder lassen sie unbeantwortet. Die gebündelten Zahlen sind
$$\begin{aligned} T_{\mathrm{mid}}((0,0),(0,0),0)&=3,\\ T_{\mathrm{mid}}((0,0),(0,0),1)&=1,\\ T_{\mathrm{mid}}((0,0),(1,0),0)&=2,\\ T_{\mathrm{mid}}((0,0),(0,1),0)&=2,\\ T_{\mathrm{mid}}((0,0),(1,1),0)&=1. \end{aligned}$$
Wir wählen eine Schnittstelle, öffnen dort den Streifen und fixieren den Randzustand \(m_0\). Sei \(D_j^{(m_0)}(m,k)\) die Anzahl der Möglichkeiten, die ersten \(j\) Spalten so zu verarbeiten, dass der aktuelle Randzustand \(m\) und die bisherige Punktzahl \(k\) ist.
Die Anfangsbedingung lautet
$$D_0^{(m_0)}(m,k)=\begin{cases}1,&m=m_0\text{ und }k=0,\\0,&\text{sonst.}\end{cases}$$
Für jede gewöhnliche Spalte trägt jede Übergangsklasse bei gemäß
$$D_{j+1}^{(m_0)}(m',k+d)\leftarrow D_{j+1}^{(m_0)}(m',k+d)+D_j^{(m_0)}(m,k)\,T_{\mathrm{mid}}(m,m',d).$$
Genau dadurch wird die globale Suche schnell: Die exponentiell vielen Gesamtbelegungen schrumpfen auf eine quadratische Dynamik mit vier Randzuständen und einer Punkteachse.
Die letzte Spalte ist speziell, weil sich der Streifen nicht gerade, sondern mit Vertauschung der Zeilen schließt. Zeigt der obere Knoten der letzten Spalte nach rechts, so landet diese Erwartung an der unteren Zeile der Schnittstelle, und umgekehrt. Deshalb ist die Übergangstabelle der letzten Spalte
$$T_{\mathrm{last}}(m,m',d)=\#\{(x,y)\in\{L,R,V\}^2:\ m'=([y=R],[x=R]),\ \Delta(m;x,y)=d\}.$$
Nach diesem verdrillten Update ist eine vollständige Konfiguration genau dann gültig, wenn sie in denselben Schnittzustand zurückkehrt und insgesamt die Punktzahl \(n\) erreicht. Summiert über alle vier möglichen Schnittzustände ergibt sich
$$S(n)=\sum_{m_0\in\{0,1\}^2} D_{2n}^{(m_0)}(m_0,n)\pmod{998244353}.$$
Für \(n=1\) besitzt der Streifen \(2\) Spalten und die Zielpunktzahl ist \(1\). Beginnen wir mit dem Schnittzustand \(m_0=(0,0)\). In der ersten Spalte treten die fünf oben notierten Übergangsklassen mit den Multiplizitäten \(3,1,2,2,1\) auf.
Um nach der verdrillten letzten Spalte mit Gesamtpunktzahl \(1\) wieder bei \(m_0=(0,0)\) zu enden, liefern die zulässigen Kombinationen den Beitrag
$$3\cdot 1+1\cdot 3+2\cdot 3+2\cdot 3+1\cdot 3=21.$$
Die analoge Rechnung für die anderen Schnittzustände ergibt
$$m_0=(1,0)\Rightarrow 11,\qquad m_0=(0,1)\Rightarrow 11,\qquad m_0=(1,1)\Rightarrow 5.$$
Also
$$S(1)=21+11+11+5=48,$$
und genau dieser Wert erscheint als erster Kontrollpunkt in der Implementierung.
Die C++-, Python- und Java-Implementierungen enumerieren zunächst für jeden der 4 eingehenden Randzustände die 9 lokalen Wahlpaare. Diese Rohfälle werden zu zwei winzigen Übergangstabellen komprimiert: einer für gewöhnliche Spalten und einer für die verdrillte letzte Spalte. Das kostet nur konstante Zeit, spart aber im Hauptteil alle wiederholten Fallunterscheidungen.
Danach läuft für jeden möglichen Schnittzustand eine schichtweise Dynamische Programmierung über „aktueller Randzustand“ und „bisherige Punktzahl“. Im Speicher liegen immer nur zwei Schichten, weil jede Spalte nur von der direkt vorherigen abhängt. Nach \(2n-1\) gewöhnlichen Updates folgt ein letztes verdrilltes Update, und der Eintrag mit Rückkehr in den Startzustand bei Punktzahl genau \(n\) wird zum Gesamtergebnis addiert.
Alle Rechnungen erfolgen modulo \(998244353\). Die drei Sprachversionen implementieren dieselbe Rekurrenz; unterschiedlich sind nur Syntax und Datentypnotation.
Die Anzahl der Randzustände ist konstant \(4\), die Punkteachse hat Länge \(n+1\), und es gibt \(2n\) Spalten. Jeder Zustand besitzt nur konstant viele gebündelte Übergänge, daher beträgt die Gesamtlaufzeit \(O(n^2)\). Die rollende DP speichert nur zwei Schichten der Größe \(4\times(n+1)\), also \(O(n)\) Speicher.
Bu problem, bükümlü kapanışa sahip \(2\times 2n\) boyutlu bir şeritte her düğüme üç komşu yönünden tam birini atamanın sayısını ister: sol, sağ ya da aynı sütundaki karşı satıra giden dikey kenar. Bir kenar ancak iki ucu da birbirini seçerse \(1\) puan getirir ve toplam puanın tam olarak \(n\) olması gerekir. Sonuç \(998244353\) modunda verilir.
Doğrudan sayım \(3^{4n}\) olasılığı incelemek zorunda kalır; çünkü şeritte \(4n\) düğüm vardır ve her düğümün üç yerel seçeneği bulunur. Uygulama bu üstel büyümeyi, yapıyı sütun sütun işleyip geleceği etkileyebilecek tek bilgi olan sınır durumunu saklayarak aşar.
Ana gözlem şudur: Şeridi iki ardışık sütun arasından kestiğimizde, sonraki adımlar için yalnızca hangi yatay seçimlerin bir sonraki sütundan gelecek karşı cevabı beklediğini bilmek gerekir. Böylece bütün problem, puan ekseni taşıyan sonlu durumlu bir dinamik programa dönüşür.
Her sütunda iki düğüm vardır: biri üst satırda, biri alt satırda. Her düğüm şu üç yönden tam birini seçer:
$$L,\qquad R,\qquad V.$$
Burada \(L\), “bir önceki sütundaki komşuyu seç”; \(R\), “bir sonraki sütundaki komşuyu seç”; \(V\) ise “aynı sütunda karşı satırdaki düğümü seç” anlamına gelir. Üst ve alt düğüm bağımsız seçildiği için her sütunda
$$3^2=9$$
adet yerel yapı vardır.
Puan yalnızca bir kenar iki uçtan da seçilirse oluşur. Yatay bir eşleşme, önceki sütun aynı satırda sağa bakmışken mevcut sütunun sola cevap vermesiyle sayılır. Dikey eşleşme ise mevcut sütunun iki düğümü de \(V\) seçtiğinde oluşur.
Şeridi iki komşu sütun arasından keselim. Bu sınırda bilmemiz gereken tek şey, üst satırda ve alt satırda soldan gelen, henüz karşılanmamış bir sağa yönelmiş seçim olup olmadığıdır. Bunu
$$m=(a,b)\in\{0,1\}^2$$
durumuyla gösterelim. \(a=1\), “üst satır soldan gelen bir sol cevabı bekliyor”; \(b=1\) ise aynı durumun alt satır karşılığıdır. Dolayısıyla yalnızca dört sınır durumu vardır.
Mevcut sütunda üst ve alt düğüm sırasıyla \(x,y\in\{L,R,V\}\) seçsin. O zaman puan artışı
$$\Delta(m;x,y)=[x=L]a+[y=L]b+[x=V\land y=V]$$
olur. Çıkış durumu ise artık hangi satırların sağa baktığını kaydeder:
$$m'=([x=R],[y=R]).$$
Sabit bir giriş durumu \(m\) için, 9 yerel çiftin \((x,y)\) çoğu aynı çıkış durumuna ve aynı puan artışına gider. Bu yüzden uygulama yalnızca şu çokluğu önceden hesaplar:
$$T_{\mathrm{mid}}(m,m',d)=\#\{(x,y)\in\{L,R,V\}^2:\ m'=([x=R],[y=R]),\ \Delta(m;x,y)=d\}.$$
\(d\in\{0,1,2\}\) olduğundan her giriş durumu için ayırt edilmesi gereken sınıf sayısı küçüktür.
Örneğin \(m=(0,0)\) iken sütun içinde \(1\) puan getiren tek yerel seçim \((V,V)\) olur; diğer sekiz seçim sadece yatay beklenti açar ya da beklentiyi karşılamadan bırakır. Toplu sayılar şöyledir:
$$\begin{aligned} T_{\mathrm{mid}}((0,0),(0,0),0)&=3,\\ T_{\mathrm{mid}}((0,0),(0,0),1)&=1,\\ T_{\mathrm{mid}}((0,0),(1,0),0)&=2,\\ T_{\mathrm{mid}}((0,0),(0,1),0)&=2,\\ T_{\mathrm{mid}}((0,0),(1,1),0)&=1. \end{aligned}$$
Şeridi açtığımız dikiş noktasında bir başlangıç durumu \(m_0\) sabitleyelim. \(D_j^{(m_0)}(m,k)\), ilk \(j\) sütun işlendiğinde mevcut sınır durumu \(m\), birikmiş puan da \(k\) olacak şekilde kaç yol bulunduğunu göstersin.
Başlangıç koşulu
$$D_0^{(m_0)}(m,k)=\begin{cases}1,&m=m_0\text{ ve }k=0,\\0,&\text{aksi halde.}\end{cases}$$
Her sıradan sütunda her geçiş sınıfı şu bağıntıyla katkı verir:
$$D_{j+1}^{(m_0)}(m',k+d)\leftarrow D_{j+1}^{(m_0)}(m',k+d)+D_j^{(m_0)}(m,k)\,T_{\mathrm{mid}}(m,m',d).$$
Hızın kaynağı tam olarak budur: üstel sayıdaki küresel yapı, dört sınır durumu ve tek bir puan ekseni üzerinde çalışan kuadratik zamanlı bir DP'ye sıkışır.
Son sütun özeldir; çünkü kapanış düz değil, satırları değiştirerek yapılır. Son sütunun üst düğümü sağa bakarsa bu beklenti dikişte alt satıra döner; alt düğüm sağa bakarsa üst satıra döner. Bu yüzden son sütunun geçiş tablosu
$$T_{\mathrm{last}}(m,m',d)=\#\{(x,y)\in\{L,R,V\}^2:\ m'=([y=R],[x=R]),\ \Delta(m;x,y)=d\}$$
şeklindedir. Bu bükümlü son güncellemeden sonra tam bir yapı ancak aynı dikiş durumuna geri dönüyor ve toplam puan \(n\) oluyorsa geçerlidir. Dört olası dikiş durumunun hepsi toplanınca
$$S(n)=\sum_{m_0\in\{0,1\}^2} D_{2n}^{(m_0)}(m_0,n)\pmod{998244353}$$
elde edilir.
\(n=1\) iken şeritte \(2\) sütun vardır ve hedef puan \(1\)'dir. Dikiş durumu \(m_0=(0,0)\) ile başlayalım. İlk sütunda yukarıdaki beş geçiş sınıfı sırasıyla \(3,1,2,2,1\) çokluklarıyla ortaya çıkar.
Bükümlü son sütundan sonra yine \(m_0=(0,0)\)'a dönüp toplam puanı \(1\) yapmak için geçerli bileşimlerin katkısı
$$3\cdot 1+1\cdot 3+2\cdot 3+2\cdot 3+1\cdot 3=21$$
olur. Aynı hesap diğer dikiş durumları için
$$m_0=(1,0)\Rightarrow 11,\qquad m_0=(0,1)\Rightarrow 11,\qquad m_0=(1,1)\Rightarrow 5$$
sonuçlarını verir. Dolayısıyla
$$S(1)=21+11+11+5=48,$$
ve bu değer uygulamadaki ilk kontrol sonucuyla aynıdır.
C++, Python ve Java uygulamaları önce 4 giriş sınır durumunun her biri için 9 yerel seçimi dolaşır. Bu ham olasılıklar iki küçük geçiş tablosuna sıkıştırılır: biri sıradan sütunlar, biri bükümlü son sütun için. Bu hazırlık sabit zamanlıdır ama ana döngüdeki tekrar eden durum ayrımlarını ortadan kaldırır.
Daha sonra her olası dikiş durumu için, “mevcut sınır durumu” ve “şimdiye kadarki puan” indeksli katmanlı bir dinamik program çalıştırılır. Her adım yalnızca bir önceki katmana bağlı olduğu için bellekte iki katman tutulur. \(2n-1\) sıradan güncellemeden sonra bir son bükümlü güncelleme yapılır ve başlangıç dikiş durumuna puanı tam \(n\) ile dönen hücre sonuca eklenir.
Tüm aritmetik \(998244353\) modunda yapılır. Üç dildeki kod aynı matematiksel bağıntıyı uygular; fark yalnızca sözdizimi düzeyindedir.
Sınır durumu sayısı sabit olarak \(4\)'tür, puan ekseni \(n+1\) uzunluğundadır ve \(2n\) sütun vardır. Her durumdan yalnızca sabit sayıda toplulaştırılmış geçiş çıktığı için toplam zaman maliyeti \(O(n^2)\) olur. Katmanlı DP yalnızca \(4\times(n+1)\) boyutunda iki katman tuttuğundan bellek kullanımı \(O(n)\)'dir.
Se pide calcular \(S(n)\), el numero de formas de asignar a cada vertice de una banda \(2\times 2n\) con cierre retorcido una de sus tres direcciones incidentes: izquierda, derecha o la arista vertical que une las dos filas en la misma columna. Una arista aporta \(1\) al puntaje cuando sus dos extremos se eligen mutuamente, y el puntaje total debe ser exactamente \(n\). La respuesta se toma modulo \(998244353\).
Una enumeracion directa examinaria \(3^{4n}\) asignaciones globales, porque la banda tiene \(4n\) vertices y cada vertice dispone de tres opciones locales. Las implementaciones evitan esa explosion exponencial procesando la banda columna por columna y guardando solo la informacion de frontera que todavia puede afectar coincidencias mutuas futuras.
La observacion central es que, una vez cortada la banda entre dos columnas consecutivas, el futuro solo necesita saber que elecciones horizontales siguen esperando una respuesta reciproca desde la siguiente columna. Eso convierte el problema en una programacion dinamica sobre un conjunto finito de estados mas un contador de puntaje.
Cada columna contiene dos vertices, uno en la fila superior y otro en la inferior. Cada vertice elige exactamente una de tres direcciones:
$$L,\qquad R,\qquad V.$$
Aqui \(L\) significa “elegir al vecino de la columna anterior”, \(R\) significa “elegir al vecino de la columna siguiente” y \(V\) significa “elegir al vertice de la otra fila dentro de la misma columna”. Como los dos vertices de la columna actuan de forma independiente, cada columna tiene
$$3^2=9$$
configuraciones locales.
Solo aparece un punto cuando una arista es elegida desde ambos extremos. Una coincidencia horizontal ocurre si la columna anterior apunto a la derecha en cierta fila y la columna actual responde con \(L\) en esa misma fila. Una coincidencia vertical ocurre exactamente cuando los dos vertices de la columna eligen \(V\).
Cortemos la banda entre dos columnas adyacentes. En esa frontera solo hace falta saber si la fila superior y la fila inferior ya tienen una eleccion hacia la derecha que llega desde la izquierda y aun puede ser correspondida. Lo representamos mediante el estado
$$m=(a,b)\in\{0,1\}^2,$$
donde \(a=1\) significa “la fila superior esta esperando una respuesta hacia la izquierda” y \(b=1\) expresa lo mismo para la fila inferior. Por tanto solo hay cuatro estados de frontera.
Si la columna actual elige \(x,y\in\{L,R,V\}\) para los vertices superior e inferior, el incremento de puntaje es
$$\Delta(m;x,y)=[x=L]a+[y=L]b+[x=V\land y=V].$$
El estado de salida registra que filas quedan ahora apuntando a la derecha:
$$m'=([x=R],[y=R]).$$
Para un estado de entrada fijo \(m\), muchas de las 9 parejas locales \((x,y)\) producen exactamente el mismo estado de salida y el mismo incremento de puntaje. Por eso la implementacion precalcula solo la multiplicidad
$$T_{\mathrm{mid}}(m,m',d)=\#\{(x,y)\in\{L,R,V\}^2:\ m'=([x=R],[y=R]),\ \Delta(m;x,y)=d\}.$$
Como \(d\in\{0,1,2\}\), cada estado de entrada genera solo unas pocas clases distintas.
Por ejemplo, cuando \(m=(0,0)\), la unica forma de anotar \(1\) dentro de la columna es \((V,V)\); las otras ocho elecciones solo abren expectativas horizontales o las dejan sin corresponder. Los conteos agregados son
$$\begin{aligned} T_{\mathrm{mid}}((0,0),(0,0),0)&=3,\\ T_{\mathrm{mid}}((0,0),(0,0),1)&=1,\\ T_{\mathrm{mid}}((0,0),(1,0),0)&=2,\\ T_{\mathrm{mid}}((0,0),(0,1),0)&=2,\\ T_{\mathrm{mid}}((0,0),(1,1),0)&=1. \end{aligned}$$
Elegimos una costura donde se abre la banda y fijamos alli un estado inicial \(m_0\). Sea \(D_j^{(m_0)}(m,k)\) el numero de formas de procesar las primeras \(j\) columnas de modo que el estado de frontera actual sea \(m\) y el puntaje acumulado sea \(k\).
La condicion inicial es
$$D_0^{(m_0)}(m,k)=\begin{cases}1,&m=m_0\text{ y }k=0,\\0,&\text{en otro caso.}\end{cases}$$
Para cada columna ordinaria, cada clase de transicion aporta segun
$$D_{j+1}^{(m_0)}(m',k+d)\leftarrow D_{j+1}^{(m_0)}(m',k+d)+D_j^{(m_0)}(m,k)\,T_{\mathrm{mid}}(m,m',d).$$
Esa recurrencia es la razon de la eficiencia: las configuraciones globales, en apariencia exponenciales, se reducen a una DP cuadratica sobre cuatro estados y un eje de puntaje.
La ultima columna es especial porque el cierre no vuelve recto, sino intercambiando las dos filas. Si el vertice superior de la ultima columna apunta a la derecha, esa espera reaparece en la fila inferior de la costura; y viceversa. Por eso la tabla de transicion final es
$$T_{\mathrm{last}}(m,m',d)=\#\{(x,y)\in\{L,R,V\}^2:\ m'=([y=R],[x=R]),\ \Delta(m;x,y)=d\}.$$
Tras aplicar esta actualizacion retorcida, una configuracion completa solo es valida si regresa al mismo estado de costura y alcanza puntaje total \(n\). Sumando sobre los cuatro estados posibles se obtiene
$$S(n)=\sum_{m_0\in\{0,1\}^2} D_{2n}^{(m_0)}(m_0,n)\pmod{998244353}.$$
Cuando \(n=1\), la banda tiene \(2\) columnas y el puntaje objetivo es \(1\). Empecemos con la costura \(m_0=(0,0)\). En la primera columna aparecen las cinco clases anteriores con multiplicidades \(3,1,2,2,1\).
Para terminar con puntaje total \(1\) y regresar a \(m_0=(0,0)\) despues de la ultima columna retorcida, las combinaciones validas aportan
$$3\cdot 1+1\cdot 3+2\cdot 3+2\cdot 3+1\cdot 3=21.$$
Repitiendo la cuenta para las otras costuras se obtiene
$$m_0=(1,0)\Rightarrow 11,\qquad m_0=(0,1)\Rightarrow 11,\qquad m_0=(1,1)\Rightarrow 5.$$
Por tanto
$$S(1)=21+11+11+5=48,$$
en acuerdo con el primer valor de comprobacion de la implementacion.
Las implementaciones en C++, Python y Java comienzan enumerando las 9 elecciones locales para cada uno de los 4 estados de frontera de entrada. Esas posibilidades en bruto se comprimen en dos tablas diminutas de transiciones: una para columnas ordinarias y otra para la ultima columna retorcida. El preprocesamiento es de tiempo constante, pero elimina ramificaciones repetidas del bucle principal.
Despues, para cada posible estado de costura, la implementacion ejecuta una DP por capas indexada por el estado de frontera actual y el puntaje acumulado. Solo se guardan dos capas en memoria, porque cada columna depende unicamente de la anterior. Tras \(2n-1\) actualizaciones ordinarias, se aplica una ultima actualizacion retorcida, y la entrada que vuelve al estado inicial con puntaje exacto \(n\) se suma a la respuesta final.
Toda la aritmetica se realiza modulo \(998244353\). Las tres versiones siguen exactamente la misma recurrencia matematica; solo cambian la sintaxis y la forma de almacenar los arreglos.
El numero de estados de frontera es fijo e igual a \(4\), el eje de puntaje tiene longitud \(n+1\) y hay \(2n\) columnas. Cada estado posee solo un numero constante de transiciones agregadas, asi que el tiempo total es \(O(n^2)\). La DP con capas rodantes almacena solo dos capas de tamaño \(4\times(n+1)\), por lo que la memoria es \(O(n)\).
这道题要求计算 \(S(n)\)：在一个带有扭转闭合的 \(2\times 2n\) 条带上，给每个顶点指定三种相邻方向之一的方法数。三个方向分别是向左、向右，以及连接同一列上下两行的竖直边。当一条边的两个端点恰好互相选择时，这条边贡献 \(1\) 分；我们要求总得分恰好等于 \(n\)。答案对 \(998244353\) 取模。
如果直接暴力枚举，那么一共有 \(4n\) 个顶点、每个顶点有 \(3\) 种选择，总状态数达到 \(3^{4n}\)，显然不可行。真正可行的做法是按列推进，只保留那些将来仍可能影响“互选成边”计数的边界信息。
核心思想是：如果我们把整条带在相邻两列之间切开，那么后续部分只需要知道哪些横向选择已经从左侧伸出，并且正在等待下一列给出对应的反向选择。这样问题就被压缩成“有限个边界状态 + 一个分数维度”的动态规划。
每一列有两个顶点，一个在上排，一个在下排。每个顶点必须从下面三种方向中恰好选一种：
$$L,\qquad R,\qquad V.$$
其中 \(L\) 表示“选择前一列同一行的邻点”，\(R\) 表示“选择后一列同一行的邻点”，\(V\) 表示“选择本列另一行的那个顶点”。由于上下两个顶点独立选择，所以单列一共有
$$3^2=9$$
种局部配置。
只有当一条边被两个端点同时选中时才会得分。横向边的互选发生在“前一列这一行选了向右，而当前列这一行选了向左”的时候；竖直边的互选则恰好发生在当前列上下两个顶点都选择 \(V\) 的时候。
把条带在两列之间切开。对于右边尚未处理的部分来说，真正重要的只有两件事：上排是否已经有一个从左边伸来的“向右选择”等待被当前列用 \(L\) 回应，下排是否也有同样的等待。于是定义边界状态
$$m=(a,b)\in\{0,1\}^2,$$
其中 \(a=1\) 表示上排存在一个待回应的横向选择，\(b=1\) 表示下排存在一个待回应的横向选择。这样总共只有四种边界状态。
如果当前列上下两个顶点分别选择 \(x,y\in\{L,R,V\}\)，那么这一列带来的分数增量是
$$\Delta(m;x,y)=[x=L]a+[y=L]b+[x=V\land y=V].$$
新的边界状态只需要记录这一列是否向右继续发出了新的横向请求：
$$m'=([x=R],[y=R]).$$
当输入状态 \(m\) 固定后，9 个局部选择对 \((x,y)\) 中有很多会产生同样的输出状态 \(m'\) 和同样的得分增量 \(d\)。因此程序没有逐个保存这 9 种情况，而是只预处理它们的重数
$$T_{\mathrm{mid}}(m,m',d)=\#\{(x,y)\in\{L,R,V\}^2:\ m'=([x=R],[y=R]),\ \Delta(m;x,y)=d\}.$$
由于 \(d\) 只可能是 \(0,1,2\)，所以每个输入状态对应的不同转移类很少。
例如，当 \(m=(0,0)\) 时，单列内部唯一能得到 \(1\) 分的情况就是 \((V,V)\)；其余 8 种选择都只是打开横向等待，或者把等待留给后面处理。聚合后的结果是
$$\begin{aligned} T_{\mathrm{mid}}((0,0),(0,0),0)&=3,\\ T_{\mathrm{mid}}((0,0),(0,0),1)&=1,\\ T_{\mathrm{mid}}((0,0),(1,0),0)&=2,\\ T_{\mathrm{mid}}((0,0),(0,1),0)&=2,\\ T_{\mathrm{mid}}((0,0),(1,1),0)&=1. \end{aligned}$$
这五类就已经把原本 9 种局部选择完整地压缩了。
先选定一个切口，把条带从那里打开，并固定切口的边界状态 \(m_0\)。定义 \(D_j^{(m_0)}(m,k)\) 为：处理完前 \(j\) 列之后，当前边界状态等于 \(m\)、累计得分等于 \(k\) 的方案数。
初始条件为
$$D_0^{(m_0)}(m,k)=\begin{cases}1,&m=m_0\text{ 且 }k=0,\\0,&\text{否则。}\end{cases}$$
对于普通列，转移公式就是
$$D_{j+1}^{(m_0)}(m',k+d)\leftarrow D_{j+1}^{(m_0)}(m',k+d)+D_j^{(m_0)}(m,k)\,T_{\mathrm{mid}}(m,m',d).$$
这一步解释了为什么算法会快：看似指数级的全局配置，被压缩成只有四个边界状态和一条分数轴的二次时间 DP。
最后一列和前面的普通列不同，因为条带闭合时发生了上下两行的交换。也就是说，如果最后一列的上排顶点选择了向右，那么这个等待会回到切口的下排；反之亦然。于是最后一列的转移表变成
$$T_{\mathrm{last}}(m,m',d)=\#\{(x,y)\in\{L,R,V\}^2:\ m'=([y=R],[x=R]),\ \Delta(m;x,y)=d\}.$$
应用完这一步扭转转移后，一个完整配置只有在“回到同一个切口状态”并且“总得分正好为 \(n\)”时才算有效。把四种可能的切口状态都加起来，就得到
$$S(n)=\sum_{m_0\in\{0,1\}^2} D_{2n}^{(m_0)}(m_0,n)\pmod{998244353}.$$
当 \(n=1\) 时，一共只有 \(2\) 列，目标得分为 \(1\)。先看切口状态 \(m_0=(0,0)\)。第一列正好对应上面列出的五种转移类，它们的重数分别是 \(3,1,2,2,1\)。
如果要求经过最后那一列的扭转闭合之后，既回到 \(m_0=(0,0)\)，又让总得分等于 \(1\)，那么所有合法组合的贡献为
$$3\cdot 1+1\cdot 3+2\cdot 3+2\cdot 3+1\cdot 3=21.$$
对其他三个切口状态做同样的计算，得到
$$m_0=(1,0)\Rightarrow 11,\qquad m_0=(0,1)\Rightarrow 11,\qquad m_0=(1,1)\Rightarrow 5.$$
因此
$$S(1)=21+11+11+5=48,$$
这正好与实现中的第一个校验值一致。
C++、Python 和 Java 三个实现都会先枚举 4 个输入边界状态在 9 种局部选择下的结果，然后把这些原始情况压缩成两张很小的转移表：一张对应普通列，一张对应最后的扭转列。这个预处理本身只是常数规模，但它消除了主循环中的重复分类判断。
接下来，对每一个可能的切口状态，程序都运行一个分层动态规划。状态下标是“当前边界状态”和“当前累计得分”。因为每一列只依赖上一列，所以内存中只保留两层。做完 \(2n-1\) 次普通更新后，再做一次最后的扭转更新，把“回到起始切口状态且得分恰为 \(n\)”的那一项加到答案里。
所有运算都在模 \(998244353\) 下进行。三种语言版本实现的是同一条数学递推，差别只在语法形式和容器写法。
边界状态数固定为 \(4\)，得分维度长度为 \(n+1\)，列数为 \(2n\)。每个状态只有常数个聚合转移，因此总时间复杂度是 \(O(n^2)\)。滚动数组只保存两层 \(4\times(n+1)\) 的表，所以空间复杂度是 \(O(n)\)。
Требуется вычислить \(S(n)\): число способов назначить каждой вершине полосы \(2\times 2n\) с перекрученным замыканием одно из трех инцидентных направлений: влево, вправо или по вертикальному ребру к вершине другой строки той же колонки. Ребро дает \(1\) очко тогда и только тогда, когда оба его конца выбирают друг друга, а суммарный счет должен быть ровно равен \(n\). Ответ нужен по модулю \(998244353\).
Прямой перебор должен был бы рассматривать \(3^{4n}\) глобальных назначений, потому что в полосе \(4n\) вершин и у каждой вершины есть три локальных варианта. Реальные программы уходят от этой экспоненты: они обрабатывают конструкцию по колонкам и хранят только ту граничную информацию, которая еще может повлиять на будущие взаимные совпадения.
Главная идея такова: если разрезать полосу между двумя соседними колонками, то для продолжения важны лишь те горизонтальные выборы, которые уже пришли слева и ждут ответного выбора из следующей колонки. Поэтому вся задача сводится к динамике по небольшому числу состояний с дополнительным счетчиком очков.
В каждой колонке находятся две вершины: верхняя и нижняя. Каждая вершина выбирает ровно одно из трех направлений:
$$L,\qquad R,\qquad V.$$
Здесь \(L\) означает «выбрать соседа в предыдущей колонке», \(R\) означает «выбрать соседа в следующей колонке», а \(V\) означает «выбрать вершину в другой строке той же колонки». Так как верхняя и нижняя вершины выбирают независимо, одна колонка имеет
$$3^2=9$$
локальных конфигураций.
Очко возникает только тогда, когда ребро выбрано с двух концов. Горизонтальное взаимное ребро появляется, если предыдущая колонка на некоторой строке выбрала вправо, а текущая колонка на той же строке отвечает выбором \(L\). Вертикальное взаимное ребро появляется тогда и только тогда, когда обе вершины текущей колонки выбирают \(V\).
Разрежем полосу между двумя соседними колонками. На этой границе важно только, есть ли в верхней и нижней строке уже пришедший слева выбор вправо, который еще может получить ответ \(L\). Это кодируется состоянием
$$m=(a,b)\in\{0,1\}^2,$$
где \(a=1\) означает «верхняя строка ждет ответ слева», а \(b=1\) означает то же самое для нижней строки. Итак, возможны всего четыре граничных состояния.
Если текущая колонка выбирает \(x,y\in\{L,R,V\}\) для верхней и нижней вершин, то приращение счета равно
$$\Delta(m;x,y)=[x=L]a+[y=L]b+[x=V\land y=V].$$
Выходное состояние просто запоминает, какие строки теперь указывают вправо:
$$m'=([x=R],[y=R]).$$
При фиксированном входном состоянии \(m\) многие из 9 пар \((x,y)\) приводят к одному и тому же выходному состоянию и одному и тому же приращению счета. Поэтому реализация заранее считает только кратность
$$T_{\mathrm{mid}}(m,m',d)=\#\{(x,y)\in\{L,R,V\}^2:\ m'=([x=R],[y=R]),\ \Delta(m;x,y)=d\}.$$
Так как \(d\in\{0,1,2\}\), число различных классов переходов для каждого входа очень мало.
Например, при \(m=(0,0)\) единственный локальный случай с вкладом \(1\) внутри колонки равен \((V,V)\); остальные восемь вариантов лишь открывают горизонтальные ожидания или оставляют их без ответа. Сжатые значения таковы:
$$\begin{aligned} T_{\mathrm{mid}}((0,0),(0,0),0)&=3,\\ T_{\mathrm{mid}}((0,0),(0,0),1)&=1,\\ T_{\mathrm{mid}}((0,0),(1,0),0)&=2,\\ T_{\mathrm{mid}}((0,0),(0,1),0)&=2,\\ T_{\mathrm{mid}}((0,0),(1,1),0)&=1. \end{aligned}$$
Выберем место разреза и зафиксируем там начальное состояние \(m_0\). Пусть \(D_j^{(m_0)}(m,k)\) обозначает число способов обработать первые \(j\) колонок так, чтобы текущее граничное состояние было \(m\), а накопленный счет был равен \(k\).
Начальное условие имеет вид
$$D_0^{(m_0)}(m,k)=\begin{cases}1,&m=m_0\text{ и }k=0,\\0,&\text{иначе.}\end{cases}$$
Для каждой обычной колонки каждая переходная кратность дает вклад по правилу
$$D_{j+1}^{(m_0)}(m',k+d)\leftarrow D_{j+1}^{(m_0)}(m',k+d)+D_j^{(m_0)}(m,k)\,T_{\mathrm{mid}}(m,m',d).$$
Именно эта рекурсия и делает алгоритм быстрым: вместо экспоненциального числа глобальных конфигураций остается квадратичное DP на четырех состояниях границы и одной оси счета.
Последняя колонка отличается от обычной, потому что полоса замыкается с перестановкой строк. Если верхняя вершина последней колонки выбрала вправо, то это ожидание возвращается в нижнюю строку разреза, и наоборот. Поэтому таблица переходов для последней колонки равна
$$T_{\mathrm{last}}(m,m',d)=\#\{(x,y)\in\{L,R,V\}^2:\ m'=([y=R],[x=R]),\ \Delta(m;x,y)=d\}.$$
После этого перекрученного шага полная конфигурация допустима тогда и только тогда, когда она возвращается в то же состояние разреза и имеет суммарный счет \(n\). Суммируя по всем четырем возможным состояниям разреза, получаем
$$S(n)=\sum_{m_0\in\{0,1\}^2} D_{2n}^{(m_0)}(m_0,n)\pmod{998244353}.$$
При \(n=1\) полоса содержит \(2\) колонки, а целевой счет равен \(1\). Начнем с состояния разреза \(m_0=(0,0)\). Для первой колонки пять переходных классов выше имеют кратности \(3,1,2,2,1\).
Чтобы после последней перекрученной колонки вернуться в \(m_0=(0,0)\) и получить суммарно \(1\) очко, допустимые комбинации дают вклад
$$3\cdot 1+1\cdot 3+2\cdot 3+2\cdot 3+1\cdot 3=21.$$
Точно такой же подсчет для остальных состояний разреза дает
$$m_0=(1,0)\Rightarrow 11,\qquad m_0=(0,1)\Rightarrow 11,\qquad m_0=(1,1)\Rightarrow 5.$$
Следовательно,
$$S(1)=21+11+11+5=48,$$
что совпадает с первым контрольным значением реализации.
Реализации на C++, Python и Java сначала перебирают 9 локальных выборов для каждого из 4 входных граничных состояний. Затем эти сырые случаи сжимаются в две маленькие таблицы переходов: одну для обычных колонок и одну для последней перекрученной колонки. Такое предварительное вычисление занимает константное время, но избавляет основной алгоритм от повторяющегося разбора случаев.
Далее для каждого возможного состояния разреза запускается послойное DP по двум индексам: текущему граничному состоянию и накопленному счету. В памяти хранятся только два слоя, потому что очередная колонка зависит лишь от предыдущего слоя. После \(2n-1\) обычных обновлений выполняется одно последнее перекрученное обновление, и значение, которое возвращается в исходное состояние разреза со счетом ровно \(n\), добавляется к ответу.
Все вычисления ведутся по модулю \(998244353\). Во всех трех версиях используется одна и та же математическая рекурсия; различается только синтаксис.
Число граничных состояний постоянно и равно \(4\), ось счета имеет длину \(n+1\), а колонок ровно \(2n\). Из каждого состояния выходит лишь константное число агрегированных переходов, поэтому общее время работы равно \(O(n^2)\). Хранятся только два слоя размера \(4\times(n+1)\), значит, память составляет \(O(n)\).
المطلوب هو حساب \(S(n)\): عدد الطرق التي نعيّن بها لكل رأس في شريط \(2\times 2n\) ذي إغلاق ملتف أحد الاتجاهات الثلاثة المتصلة به: إلى اليسار، أو إلى اليمين، أو على الحافة العمودية التي تصل الصفين داخل العمود نفسه. وتحسب الحافة نقطة واحدة إذا اختار طرفاها بعضهما بعضًا، ونريد أن يكون مجموع النقاط مساويًا تمامًا لـ \(n\). ثم نأخذ الجواب بترديد \(998244353\).
العدّ المباشر يحتاج إلى فحص \(3^{4n}\) تعيينًا عالميًا، لأن الشريط يحتوي على \(4n\) رأسًا ولكل رأس ثلاثة اختيارات محلية. لذلك تتجنب الخوارزمية هذا الانفجار الأسي عبر معالجة الأعمدة واحدًا بعد الآخر والاحتفاظ فقط بالمعلومة الحدّية التي ما زالت قادرة على التأثير في التطابقات المتبادلة لاحقًا.
الفكرة الحاسمة هي أنه إذا قطعنا الشريط بين عمودين متجاورين، فإن الجزء المتبقي لا يحتاج إلا إلى معرفة أي الاختيارات الأفقية القادمة من اليسار ما زالت تنتظر جوابًا معاكسًا من العمود التالي. وهكذا تتحول المسألة إلى برمجة ديناميكية على عدد صغير من الحالات مع محور إضافي للنقاط.
كل عمود يحتوي على رأسين: رأس علوي ورأس سفلي. وكل رأس يختار بالضبط أحد الاتجاهات الثلاثة:
$$L,\qquad R,\qquad V.$$
حيث إن \(L\) يعني «اختر الجار في العمود السابق»، و\(R\) يعني «اختر الجار في العمود التالي»، و\(V\) يعني «اختر الرأس في الصف الآخر داخل العمود نفسه». وبما أن اختيار الرأس العلوي مستقل عن اختيار الرأس السفلي، فإن عدد الترتيبات المحلية في العمود الواحد هو
$$3^2=9.$$
ولا تظهر نقطة إلا إذا اختيرت الحافة من الطرفين. فالمطابقة الأفقية تحدث عندما يكون العمود السابق قد اختار اليمين في صف ما ويأتي العمود الحالي في الصف نفسه باختيار \(L\). أما المطابقة العمودية فتحدث بالضبط عندما يختار رأسا العمود الحالي كلاهما \(V\).
لنقطع الشريط بين عمودين متجاورين. عند هذا الحد لا يهمنا إلا هل يوجد في الصف العلوي أو الصف السفلي اختيار سابق باتجاه اليمين قادم من اليسار وينتظر جوابًا معاكسًا. نمثل ذلك بالحالة
$$m=(a,b)\in\{0,1\}^2,$$
بحيث يعني \(a=1\) أن الصف العلوي ينتظر جوابًا من نوع \(L\)، ويعني \(b=1\) الشيء نفسه للصف السفلي. وبالتالي لا توجد إلا أربع حالات حدية ممكنة.
إذا اختار العمود الحالي الاتجاهين \(x,y\in\{L,R,V\}\) للرأسين العلوي والسفلي، فإن الزيادة في النقاط تساوي
$$\Delta(m;x,y)=[x=L]a+[y=L]b+[x=V\land y=V].$$
أما حالة الخرج فتكفيها معرفة أي الصفين يشير الآن إلى اليمين:
$$m'=([x=R],[y=R]).$$
عند تثبيت حالة الدخول \(m\)، نجد أن كثيرًا من الأزواج المحلية \((x,y)\) التسعة تعطي الحالة الخارجة نفسها وزيادة النقاط نفسها. لذلك لا تخزن الخوارزمية كل زوج على حدة، بل تحسب فقط المضاعف
$$T_{\mathrm{mid}}(m,m',d)=\#\{(x,y)\in\{L,R,V\}^2:\ m'=([x=R],[y=R]),\ \Delta(m;x,y)=d\}.$$
ولأن \(d\) لا يأخذ إلا القيم \(0,1,2\)، فإن عدد فئات الانتقال المختلفة صغير جدًا لكل حالة دخول.
فعلى سبيل المثال، عندما \(m=(0,0)\)، فإن الحالة المحلية الوحيدة التي تعطي نقطة واحدة داخل العمود هي \((V,V)\)، أما الحالات الثماني الأخرى فلا تفعل إلا فتح طلبات أفقية جديدة أو تركها من دون إغلاق. وتكون الأعداد المجمعة كما يلي:
$$\begin{aligned} T_{\mathrm{mid}}((0,0),(0,0),0)&=3,\\ T_{\mathrm{mid}}((0,0),(0,0),1)&=1,\\ T_{\mathrm{mid}}((0,0),(1,0),0)&=2,\\ T_{\mathrm{mid}}((0,0),(0,1),0)&=2,\\ T_{\mathrm{mid}}((0,0),(1,1),0)&=1. \end{aligned}$$
نختار موضع القطع في الشريط ونثبت عنده حالة ابتدائية \(m_0\). ولتكن \(D_j^{(m_0)}(m,k)\) عدد الطرق التي تعالج أول \(j\) عمودًا بحيث تكون الحالة الحدية الحالية هي \(m\) ويكون مجموع النقاط المتراكم هو \(k\).
شرط البداية هو
$$D_0^{(m_0)}(m,k)=\begin{cases}1,&m=m_0,\ k=0,\\0,&\mathrm{otherwise.}\end{cases}$$
أما في كل عمود عادي فتعطي كل فئة انتقال المساهمة التالية:
$$D_{j+1}^{(m_0)}(m',k+d)\leftarrow D_{j+1}^{(m_0)}(m',k+d)+D_j^{(m_0)}(m,k)\,T_{\mathrm{mid}}(m,m',d).$$
وهنا يكمن سبب الكفاءة: ما يبدو في البداية بحثًا أسيًا في عدد هائل من التعيينات العالمية يتحول إلى برمجة ديناميكية بزمن تربيعي على أربع حالات حدية ومحور واحد للنقاط.
العمود الأخير يختلف عن الأعمدة العادية لأن الإغلاق لا يعود مستقيمًا، بل مع تبديل الصفين. فإذا اختار الرأس العلوي في العمود الأخير الاتجاه \(R\)، فإن هذا الطلب يعود عند موضع القطع إلى الصف السفلي، والعكس بالعكس. لذلك تصبح طاولة الانتقال الأخيرة
$$T_{\mathrm{last}}(m,m',d)=\#\{(x,y)\in\{L,R,V\}^2:\ m'=([y=R],[x=R]),\ \Delta(m;x,y)=d\}.$$
وبعد تنفيذ هذا الانتقال الملتف، لا تكون البنية الكاملة صالحة إلا إذا عادت إلى حالة القطع نفسها وحققت مجموع نقاط يساوي \(n\). وبجمع الحالات الأربع الممكنة لموضع القطع نحصل على
$$S(n)=\sum_{m_0\in\{0,1\}^2} D_{2n}^{(m_0)}(m_0,n)\pmod{998244353}.$$
عندما \(n=1\)، يكون لدينا عمودان فقط ويكون الهدف هو نقطة واحدة. لنبدأ من حالة القطع \(m_0=(0,0)\). في العمود الأول تظهر فئات الانتقال الخمس المذكورة أعلاه بالمضاعفات \(3,1,2,2,1\).
ولكي ننتهي بعد العمود الأخير الملتف في الحالة نفسها \(m_0=(0,0)\) وبمجموع نقاط يساوي \(1\)، فإن التركيبات الصالحة تعطي
$$3\cdot 1+1\cdot 3+2\cdot 3+2\cdot 3+1\cdot 3=21.$$
وبتكرار الحساب نفسه للحالات الحدية الأخرى نحصل على
$$m_0=(1,0)\Rightarrow 11,\qquad m_0=(0,1)\Rightarrow 11,\qquad m_0=(1,1)\Rightarrow 5.$$
إذن
$$S(1)=21+11+11+5=48,$$
وهو نفس أول مقدار تحقق تستخدمه الخوارزمية.
تبدأ تطبيقات C++ وPython وJava بعدّ الخيارات المحلية التسعة لكل واحدة من حالات الدخول الحدية الأربع. ثم تُضغط هذه الحالات الخام في جدولين صغيرين جدًا للانتقالات: أحدهما للأعمدة العادية والآخر للعمود الأخير ذي الإغلاق الملتف. هذه المرحلة ثابتة الزمن، لكنها تزيل تكرار تحليل الحالات من الحلقة الرئيسية.
بعد ذلك، ولكل حالة قطع ممكنة، تنفذ الخوارزمية برمجة ديناميكية طبقية مفهرسة بالحالة الحدية الحالية وبعدد النقاط المتراكمة. ولا يُحتفظ في الذاكرة إلا بطبقتين فقط، لأن كل عمود يعتمد على الطبقة السابقة مباشرة. وبعد \(2n-1\) تحديثًا عاديًا، يجرى تحديث ملتف أخير، ثم تضاف القيمة التي تعود إلى حالة القطع الابتدائية مع نقاط تساوي \(n\) إلى الجواب الكلي.
جميع العمليات الحسابية تتم بترديد \(998244353\). والنسخ الثلاث تطبق العلاقة الرياضية نفسها، ولا يختلف بينها إلا أسلوب الكتابة البرمجية.
عدد الحالات الحدية ثابت ويساوي \(4\)، وطول محور النقاط هو \(n+1\)، وعدد الأعمدة هو \(2n\). ولكل حالة عدد ثابت فقط من الانتقالات المجمعة، لذا يكون الزمن الكلي \(O(n^2)\). أما الذاكرة فتبقى \(O(n)\)، لأن البرمجة الديناميكية تحتفظ بطبقتين فقط بحجم \(4\times(n+1)\).