Problem 907 works with cup sizes \(1,2,\dots,n\), but each size can appear in two oriented states, written \((s,0)\) and \((s,1)\). A legal stack is not an arbitrary sequence: from the current oriented cup you may move only along a small list of allowed transitions, and by the end you must have used every size exactly once. The path therefore has length \(n\), not \(2n\), because using size \(s\) in one orientation already forbids using the same size again in the opposite orientation.
If \(S(n)\) denotes the number of legal full-length paths, the implementations aim at \(S(10^7)\bmod (10^9+7)\). A brute-force search over all admissible paths is feasible only for very small \(n\), so the solution strategy has two layers: an exact state-space count for small cases and a fixed linear recurrence for large \(n\).
The mathematical content of the implementations is completely driven by three problem-specific objects: the directed graph on oriented cups, the invariant that only sizes matter for the visited-set, and the order-\(8\) recurrence that takes over once the initial values have been certified.
For each size \(s\in\{1,\dots,n\}\) and orientation \(o\in\{0,1\}\), introduce a vertex \((s,o)\). The allowed transitions are
$$ (s,0)\to(s-1,0),\qquad (s,0)\to(s-2,1),\qquad (s,0)\to(s+2,1), $$
$$ (s,1)\to(s+1,1),\qquad (s,1)\to(s-2,0),\qquad (s,1)\to(s+2,0), $$
whenever the target size still lies between \(1\) and \(n\). So every state has outdegree at most \(3\). There are two kinds of moves:
same-orientation moves, which change the size by \(1\), and orientation-flipping moves, which change the size by \(2\).
This already explains why the problem is local. A move never jumps arbitrarily far; it only interacts with neighboring sizes. That locality is exactly what later collapses the large-\(n\) problem into a short linear recurrence.
A natural first thought is to count paths on the \(2n\)-vertex directed graph. But that is not the real combinatorial state space, because the rule is "use each size once", not "visit each oriented vertex once". The implementations encode this by remembering only which sizes have already appeared.
Define
$$ F(M,s,o) $$
to be the number of legal completions from current state \((s,o)\) when the set of used sizes is exactly \(M\subseteq\{1,\dots,n\}\), with \(s\in M\). Then the terminal condition is
$$ F(\{1,\dots,n\},s,o)=1, $$
because a path that has already used all sizes is complete. Otherwise, every legal next move must go to an allowed neighbor \((t,p)\) whose size \(t\) is not yet in \(M\), so
$$ F(M,s,o)=\sum_{\substack{(s,o)\to(t,p)\\ t\notin M}} F(M\cup\{t\},t,p). $$
The total number of valid full stacks is therefore
$$ S(n)=\sum_{s=1}^{n}\sum_{o=0}^{1} F(\{s\},s,o). $$
This recurrence is not a generic template; it encodes the central invariant of this problem: opposite orientations of the same size compete for a single slot in the path.
For \(n=3\), consider the start state \((1,1)\). The legal outgoing moves are to \((2,1)\) and \((3,0)\), so
$$ F(\{1\},1,1)=F(\{1,2\},2,1)+F(\{1,3\},3,0). $$
From \((2,1)\) with used sizes \(\{1,2\}\), the only unused legal continuation is \((3,1)\), giving
$$ F(\{1,2\},2,1)=F(\{1,2,3\},3,1)=1. $$
From \((3,0)\) with used sizes \(\{1,3\}\), the only unused legal continuation is \((2,0)\), so
$$ F(\{1,3\},3,0)=F(\{1,2,3\},2,0)=1. $$
Hence
$$ F(\{1\},1,1)=2. $$
The two complete stacks are
$$ (1,1)\to(2,1)\to(3,1) $$
and
$$ (1,1)\to(3,0)\to(2,0). $$
Summing over all possible starts gives \(S(3)=6\), which matches the certified initial table used later by the fast method.
The exact recurrence above is still exponential because \(M\) can be any subset. For large \(n\), the implementations exploit a second structural fact: every move changes the size by only \(1\) or \(2\). When one extends the problem from sizes \(\{1,\dots,n-1\}\) to \(\{1,\dots,n\}\), only a bounded fringe near the largest sizes can interact with the new cup. That means one can compress the effect of the unfinished top end into finitely many boundary patterns.
After eliminating those auxiliary pattern counts, the implementations use the scalar recurrence
$$ S_n=2S_{n-1}-3S_{n-2}+5S_{n-3}-4S_{n-4}+4S_{n-5}-3S_{n-6}+S_{n-7}-S_{n-8}, \qquad n\ge 10. $$
The exact derivation of the auxiliary boundary system is not encoded explicitly in the production code; what the implementations store is the reduced one-dimensional recurrence above. Its correctness is anchored by exact counts for small \(n\), not taken on faith.
The initial values used by the recurrence are
$$ S(1)=2,\ S(2)=2,\ S(3)=6,\ S(4)=12,\ S(5)=16,\ S(6)=22,\ S(7)=36,\ S(8)=58,\ S(9)=82. $$
Applying the recurrence once gives
$$ \begin{aligned} S_{10}&=2\cdot 82-3\cdot 58+5\cdot 36-4\cdot 22+4\cdot 16-3\cdot 12+6-2\\ &=164-174+180-88+64-36+6-2\\ &=114. \end{aligned} $$
The exact small-\(n\) search confirms \(S(10)=114\), so the rolling recurrence starts from values that have already been checked against the real combinatorial count.
The C++, Python, and Java implementations all compute the same mathematical sequence, but the C++ version also contains a built-in exact verifier for small \(n\).
The C++ implementation first builds the directed transition graph on the \(2n\) oriented states. It then memoizes the function \(F(M,s,o)\) using three pieces of information: a bitmask for the used sizes, the current size, and the current orientation. This is the crucial implementation decision dictated by the mathematics: the mask tracks sizes only, because choosing one orientation of size \(s\) consumes size \(s\) completely.
That verifier checks the exact values for \(n=1,\dots,10\), so the base table \(2,2,6,12,16,22,36,58,82,114\) is not guessed. It is computed directly from the path-counting definition.
Once the initial values are known, all three implementations switch to the fast recurrence. They keep only the latest eight sequence values, form the next one with the fixed coefficients, reduce modulo \(10^9+7\), normalize after the subtractions, and slide the window forward by one position.
The C++ implementation also checks several checkpoints, including \(S(4)=12\), \(S(8)=58\), and \(S(20)=5560\). The Python and Java implementations keep only the production part, since the recurrence alone is enough once its seed values are trusted.
The exact verifier has exponentially many subset states. In the worst case there are \(O(n2^n)\) memo states for the pair \((M,s)\), doubled by the orientation bit, and each state examines at most three outgoing edges. So the exact method is exponential and intended only for small certification cases.
The production computation is much smaller. Each new term \(S_n\) requires a constant number of modular additions and subtractions, so computing up to \(S(10^7)\) takes \(O(n)\) time and \(O(1)\) extra memory.
Problem 907 arbeitet mit Bechergrößen \(1,2,\dots,n\), aber jede Größe besitzt zwei orientierte Zustände, geschrieben als \((s,0)\) und \((s,1)\). Ein zulässiger Stapel ist keine beliebige Folge, sondern ein gerichteter Pfad: Vom aktuellen orientierten Becher aus darf man nur über eine kleine Menge erlaubter Übergänge weitergehen, und am Ende muss jede Größe genau einmal benutzt worden sein. Der Pfad hat also Länge \(n\) und nicht \(2n\), denn sobald Größe \(s\) in einer Orientierung verwendet wurde, ist dieselbe Größe in der anderen Orientierung ebenfalls verbraucht.
Bezeichnet \(S(n)\) die Anzahl aller zulässigen vollständigen Pfade, dann zielen die Implementierungen auf \(S(10^7)\bmod(10^9+7)\). Eine vollständige Tiefensuche ist nur für sehr kleine \(n\) praktikabel. Deshalb besteht die Lösung aus zwei Schichten: exaktes Zustandszählen für kleine Fälle und einer festen linearen Rekurrenz für große \(n\).
Der mathematische Kern der Implementierungen wird von drei problemspezifischen Ideen getragen: dem gerichteten Graphen auf orientierten Bechern, der Invariante "benutzte Größen statt benutzter orientierter Knoten" und der Rekurrenz \(8\). Ordnung, die nach der Validierung der Anfangswerte die große Rechnung übernimmt.
Für jede Größe \(s\in\{1,\dots,n\}\) und jede Orientierung \(o\in\{0,1\}\) führe einen Knoten \((s,o)\) ein. Die erlaubten Übergänge sind
$$ (s,0)\to(s-1,0),\qquad (s,0)\to(s-2,1),\qquad (s,0)\to(s+2,1), $$
$$ (s,1)\to(s+1,1),\qquad (s,1)\to(s-2,0),\qquad (s,1)\to(s+2,0), $$
sofern die Zielgröße weiter in \(\{1,\dots,n\}\) liegt. Jeder Zustand hat also höchstens drei ausgehende Kanten. Dabei gibt es zwei Bewegungstypen:
orientierungserhaltende Schritte, die die Größe um \(1\) ändern, und orientierungswechselnde Schritte, die die Größe um \(2\) ändern.
Damit ist bereits sichtbar, warum die Aufgabe lokal ist. Kein Zug springt beliebig weit; er koppelt nur benachbarte Größen. Genau diese Lokalität sorgt später dafür, dass sich das Verhalten für große \(n\) in eine kurze lineare Rekurrenz zusammenfalten lässt.
Auf den ersten Blick könnte man versuchen, Hamiltonpfade im \(2n\)-Knoten-Graphen zu zählen. Das wäre aber nicht der richtige Zustandsraum, denn die Regel lautet "jede Größe genau einmal" und nicht "jeden orientierten Zustand genau einmal". Die Implementierungen speichern deshalb nur, welche Größen bereits erschienen sind.
Sei
$$ F(M,s,o) $$
die Anzahl zulässiger Fortsetzungen aus dem aktuellen Zustand \((s,o)\), wenn die bereits benutzten Größen genau die Menge \(M\subseteq\{1,\dots,n\}\) bilden und \(s\in M\) gilt. Dann lautet die Endbedingung
$$ F(\{1,\dots,n\},s,o)=1, $$
denn ein Pfad, der schon alle Größen verbraucht hat, ist vollständig. Sonst muss jeder legale nächste Schritt zu einem erlaubten Nachbarn \((t,p)\) führen, dessen Größe \(t\) noch nicht in \(M\) liegt. Also
$$ F(M,s,o)=\sum_{\substack{(s,o)\to(t,p)\\ t\notin M}} F(M\cup\{t\},t,p). $$
Der Gesamtwert ist damit
$$ S(n)=\sum_{s=1}^{n}\sum_{o=0}^{1} F(\{s\},s,o). $$
Diese Rekursion ist keine austauschbare Standardformel, sondern die präzise Übersetzung der Kerninvariante von Problem 907: Die beiden Orientierungen derselben Größe konkurrieren um genau einen Platz im Pfad.
Für \(n=3\) betrachten wir den Startzustand \((1,1)\). Die zulässigen ausgehenden Schritte führen nach \((2,1)\) und \((3,0)\), also
$$ F(\{1\},1,1)=F(\{1,2\},2,1)+F(\{1,3\},3,0). $$
Von \((2,1)\) mit benutzten Größen \(\{1,2\}\) gibt es als einzige unbenutzte zulässige Fortsetzung \((3,1)\). Daher
$$ F(\{1,2\},2,1)=F(\{1,2,3\},3,1)=1. $$
Von \((3,0)\) mit benutzten Größen \(\{1,3\}\) bleibt nur \((2,0)\). Also
$$ F(\{1,3\},3,0)=F(\{1,2,3\},2,0)=1. $$
Somit ist
$$ F(\{1\},1,1)=2. $$
Die beiden vollständigen Stapel sind
$$ (1,1)\to(2,1)\to(3,1) $$
und
$$ (1,1)\to(3,0)\to(2,0). $$
Summiert man über alle möglichen Startzustände, erhält man \(S(3)=6\). Genau dieser Wert steht auch in der verifizierten Anfangstabelle für die schnelle Methode.
Die exakte Rekursion oben bleibt exponentiell, weil \(M\) jede Teilmenge sein kann. Für große \(n\) nutzen die Implementierungen daher eine zweite Struktur aus: Jeder Zug ändert die Größe nur um \(1\) oder \(2\). Vergrößert man das Problem von \(\{1,\dots,n-1\}\) auf \(\{1,\dots,n\}\), dann kann der neue größte Becher nur mit einem beschränkten Randbereich nahe der Spitze wechselwirken. Den noch unvollständigen oberen Rand kann man also durch endlich viele Randmuster kodieren.
Nach Eliminierung dieser Hilfsgrößen verwenden die Implementierungen die skalare Rekurrenz
$$ S_n=2S_{n-1}-3S_{n-2}+5S_{n-3}-4S_{n-4}+4S_{n-5}-3S_{n-6}+S_{n-7}-S_{n-8}, \qquad n\ge 10. $$
Die exakte Herleitung des Hilfssystems ist im Produktivteil nicht ausprogrammiert; gespeichert ist dort direkt die reduzierte eindimensionale Rekurrenz. Deren Gültigkeit wird aber durch exakte Kleinwerte abgesichert und nicht bloß angenommen.
Als Anfangswerte dienen
$$ S(1)=2,\ S(2)=2,\ S(3)=6,\ S(4)=12,\ S(5)=16,\ S(6)=22,\ S(7)=36,\ S(8)=58,\ S(9)=82. $$
Einmal angewendet ergibt die Rekurrenz
$$ \begin{aligned} S_{10}&=2\cdot 82-3\cdot 58+5\cdot 36-4\cdot 22+4\cdot 16-3\cdot 12+6-2\\ &=164-174+180-88+64-36+6-2\\ &=114. \end{aligned} $$
Die exakte Kleinsuche bestätigt \(S(10)=114\). Die Rollrekurrenz startet also von Werten, die bereits mit der echten kombinatorischen Definition abgeglichen wurden.
Die Implementierungen in C++, Python und Java berechnen dieselbe Folge. Die C++-Version enthält zusätzlich eine eingebaute exakte Prüfung für kleine \(n\).
Die C++-Implementierung baut zuerst den gerichteten Übergangsgraphen auf den \(2n\) orientierten Zuständen. Danach memoisiert sie die Funktion \(F(M,s,o)\) anhand von drei Informationen: Bitmaske der benutzten Größen, aktuelle Größe und aktuelle Orientierung. Diese Wahl folgt direkt aus der Mathematik: Die Maske speichert nur Größen, weil die Benutzung einer Orientierung die andere Orientierung derselben Größe automatisch sperrt.
So werden die exakten Werte für \(n=1,\dots,10\) geprüft. Die Tabelle \(2,2,6,12,16,22,36,58,82,114\) ist also nicht erraten, sondern direkt aus der Pfadzählung gewonnen.
Sobald die Anfangswerte feststehen, wechseln alle drei Implementierungen zur schnellen Rekurrenz. Es werden nur die letzten acht Folgenglieder gehalten, der nächste Wert mit den festen Koeffizienten gebildet, modulo \(10^9+7\) reduziert, nach Subtraktionen normalisiert und das Fenster um eine Position weitergeschoben.
Die C++-Implementierung prüft zusätzlich Kontrollpunkte wie \(S(4)=12\), \(S(8)=58\) und \(S(20)=5560\). Python und Java enthalten nur den Produktivteil, weil die Rekurrenz nach bestätigten Startwerten vollständig genügt.
Die exakte Verifikation besitzt exponentiell viele Teilmengen-Zustände. Im Worst Case gibt es \(O(n2^n)\) Memo-Zustände für \((M,s)\), verdoppelt durch das Orientierungsbit, und jeder Zustand untersucht höchstens drei ausgehende Kanten. Deshalb ist die exakte Methode exponentiell und nur für kleine Prüfgrößen gedacht.
Die eigentliche Rechnung ist wesentlich kleiner. Jedes neue Folgenglied \(S_n\) benötigt nur eine konstante Zahl modularer Additionen und Subtraktionen. Damit kostet die Berechnung bis \(S(10^7)\) insgesamt \(O(n)\) Zeit und \(O(1)\) zusätzlichen Speicher.
Problem 907'de kupa boyutları \(1,2,\dots,n\) olarak verilir; fakat her boyut iki yönlü durumda bulunabilir ve bunlar \((s,0)\) ile \((s,1)\) olarak yazılır. Geçerli bir istif dizisi keyfi bir sıralama değildir. Mevcut yönlü kupadan yalnızca izin verilen birkaç geçiş üzerinden ilerlenebilir ve sonunda her boyut tam bir kez kullanılmış olmalıdır. Bu yüzden yolun uzunluğu \(2n\) değil \(n\)'dir; çünkü \(s\) boyutu bir yönde kullanıldığında aynı boyutun öteki yönü de artık kullanılamaz.
\(S(n)\), tüm geçerli tam yolların sayısı olsun. İmplementasyonlar \(S(10^7)\bmod(10^9+7)\) değerini hesaplar. Bütün olası yolları doğrudan taramak sadece çok küçük \(n\) değerlerinde mümkündür. Bu nedenle çözüm iki katmanlıdır: küçük örnekler için tam durum uzayı sayımı ve büyük \(n\) için sabit katsayılı doğrusal rekürans.
İmplementasyonlardaki matematik üç gerçek nesne etrafında kuruludur: yönlü kupalar üzerindeki geçiş grafı, ziyaret bilgisinin yönlü düğümler değil boyutlar üzerinden tutulması ve başlangıç değerleri doğrulandıktan sonra devreye giren \(8\). dereceden rekürans.
Her \(s\in\{1,\dots,n\}\) boyutu ve her \(o\in\{0,1\}\) yönü için bir \((s,o)\) düğümü tanımlayalım. İzinli geçişler şunlardır:
$$ (s,0)\to(s-1,0),\qquad (s,0)\to(s-2,1),\qquad (s,0)\to(s+2,1), $$
$$ (s,1)\to(s+1,1),\qquad (s,1)\to(s-2,0),\qquad (s,1)\to(s+2,0), $$
ve hedef boyutun yine \(\{1,\dots,n\}\) aralığında kalması gerekir. Dolayısıyla her durumun çıkış derecesi en fazla \(3\)'tür. Burada iki farklı hamle türü vardır:
yönü koruyan hamleler boyutu \(1\) değiştirir; yön değiştiren hamleler boyutu \(2\) değiştirir.
Bu gözlem problemin neden yerel olduğunu hemen açıklar. Hamleler çok uzağa sıçramaz; yalnızca yakın boyutlarla etkileşir. Büyük \(n\) için kısa bir doğrusal rekürans çıkmasının temel nedeni de tam olarak bu yerelliktir.
İlk bakışta \(2n\) düğümlü yönlü graf üzerinde Hamilton yolu benzeri bir sayım yapmak cazip görünür. Ancak gerçek durum uzayı bu değildir; çünkü kural "her yönlü durum bir kez kullanılsın" değil, "her boyut bir kez kullanılsın" şeklindedir. Bu yüzden implementasyonlar yalnızca hangi boyutların kullanıldığını hatırlar.
Şimdi
$$ F(M,s,o) $$
niceliğini, kullanılmış boyutlar kümesi tam olarak \(M\subseteq\{1,\dots,n\}\) iken ve mevcut durum \((s,o)\) iken kalan geçerli tamamlamaların sayısı olarak tanımlayalım. Burada \(s\in M\) olmalıdır. Son durum koşulu
$$ F(\{1,\dots,n\},s,o)=1 $$
şeklindedir; çünkü bütün boyutlar kullanıldıysa yol tamamlanmıştır. Aksi halde her geçerli sonraki adım, boyutu henüz \(M\) içinde olmayan bir izinli komşu \((t,p)\)'ye gitmelidir. Dolayısıyla
$$ F(M,s,o)=\sum_{\substack{(s,o)\to(t,p)\\ t\notin M}} F(M\cup\{t\},t,p) $$
olur. Toplam sonuç da
$$ S(n)=\sum_{s=1}^{n}\sum_{o=0}^{1} F(\{s\},s,o) $$
biçimindedir. Bu bağıntı rastgele bir şablon değildir; Problem 907'nin asıl değişmezini, yani aynı boyutun iki yönünün yol içinde tek bir yeri paylaşmasını doğrudan kodlar.
\(n=3\) iken başlangıç durumunu \((1,1)\) alalım. Bu durumdan izinli çıkışlar \((2,1)\) ve \((3,0)\) olduğundan
$$ F(\{1\},1,1)=F(\{1,2\},2,1)+F(\{1,3\},3,0) $$
yazılır. \((2,1)\) durumunda kullanılmış boyutlar \(\{1,2\}\) ise kullanılmamış tek geçerli devam \((3,1)\)'dir. Bu yüzden
$$ F(\{1,2\},2,1)=F(\{1,2,3\},3,1)=1 $$
olur. Benzer biçimde \((3,0)\) durumunda kullanılmış boyutlar \(\{1,3\}\) iken tek devam \((2,0)\)'dır, dolayısıyla
$$ F(\{1,3\},3,0)=F(\{1,2,3\},2,0)=1 $$
elde edilir. Sonuç olarak
$$ F(\{1\},1,1)=2. $$
Bu iki tam yol şunlardır:
$$ (1,1)\to(2,1)\to(3,1) $$
ve
$$ (1,1)\to(3,0)\to(2,0). $$
Tüm başlangıç durumları üzerinden toplandığında \(S(3)=6\) bulunur. Bu değer, hızlı yöntemde kullanılan doğrulanmış başlangıç tablosuyla tam uyumludur.
Yukarıdaki tam bağıntı yine de üstel büyür; çünkü \(M\) herhangi bir alt küme olabilir. Büyük \(n\) için implementasyonlar ikinci bir yapısal gerçeği kullanır: her hamle boyutu yalnızca \(1\) veya \(2\) kadar değiştirir. Problem \(\{1,\dots,n-1\}\)'den \(\{1,\dots,n\}\)'ye genişletildiğinde, yeni eklenen en büyük boyut ancak en üst uçtaki sınırlı sayıda boyutla etkileşebilir. Bu yüzden tamamlanmamış üst sınır, sonlu sayıda sınır desenine sıkıştırılabilir.
Bu yardımcı desen sayıları elimine edildiğinde implementasyonlarda kullanılan skaler rekürans ortaya çıkar:
$$ S_n=2S_{n-1}-3S_{n-2}+5S_{n-3}-4S_{n-4}+4S_{n-5}-3S_{n-6}+S_{n-7}-S_{n-8}, \qquad n\ge 10. $$
Üretim kodu bu yardımcı sınır sistemini açıkça kurmaz; doğrudan indirgenmiş tek boyutlu reküransı kullanır. Ama bu reküransın doğruluğu küçük \(n\) için tam sayımla sınandığı için salt varsayım değildir.
Reküransın kullandığı başlangıç değerleri şöyledir:
$$ S(1)=2,\ S(2)=2,\ S(3)=6,\ S(4)=12,\ S(5)=16,\ S(6)=22,\ S(7)=36,\ S(8)=58,\ S(9)=82. $$
Bir adım ileri gidildiğinde
$$ \begin{aligned} S_{10}&=2\cdot 82-3\cdot 58+5\cdot 36-4\cdot 22+4\cdot 16-3\cdot 12+6-2\\ &=164-174+180-88+64-36+6-2\\ &=114 \end{aligned} $$
elde edilir. Küçük \(n\) için yapılan tam tarama da \(S(10)=114\) sonucunu verdiği için kayan pencere hesabı güvenilir tohumlarla başlar.
C++, Python ve Java implementasyonlarının hepsi aynı diziyi hesaplar; fakat C++ sürümünde ayrıca küçük \(n\) için yerleşik bir tam doğrulama katmanı vardır.
C++ implementasyonu önce \(2n\) yönlü durumdan oluşan geçiş grafını kurar. Ardından \(F(M,s,o)\) fonksiyonunu üç bilgiyle ezberler: kullanılmış boyutları gösteren bit maskesi, mevcut boyut ve mevcut yön. Buradaki kritik tercih doğrudan matematikten gelir: maske yalnızca boyutları tutar, çünkü bir boyutun bir yönde kullanılması diğer yönünü de otomatik olarak kapatır.
Böylece \(n=1,\dots,10\) için tam değerler doğrulanır. Yani \(2,2,6,12,16,22,36,58,82,114\) tablosu tahmin edilmez; doğrudan yol sayımından üretilir.
Başlangıç değerleri kesinleştikten sonra üç implementasyon da hızlı reküransa geçer. Sadece son sekiz değer tutulur, sabit katsayılarla yeni terim hesaplanır, \(10^9+7\) modunda düzeltilir, çıkarma işlemlerinden sonra normalize edilir ve pencere bir adım kaydırılır.
C++ implementasyonu ayrıca \(S(4)=12\), \(S(8)=58\) ve \(S(20)=5560\) gibi kontrol noktalarını sınar. Python ve Java tarafında üretim kısmı bırakılmıştır; çünkü başlangıç değerleri doğrulandıktan sonra tek başına rekürans yeterlidir.
Tam doğrulama üstel sayıda alt küme durumuna sahiptir. En kötü durumda \((M,s)\) çifti için \(O(n2^n)\) kadar ezber durumu vardır; buna yön biti de eklendiğinde yalnızca sabit katsayı büyür. Her durum en fazla üç çıkış kenarı inceler. Dolayısıyla tam yöntem üstel karmaşıklıktadır ve yalnızca küçük doğrulama örnekleri için uygundur.
Asıl hesap çok daha küçüktür. Her yeni \(S_n\) terimi sabit sayıda modüler toplama ve çıkarma gerektirir. Bu nedenle \(S(10^7)\)'ye kadar hesaplama \(O(n)\) zamanda ve \(O(1)\) ek bellekle tamamlanır.
En el problema 907 aparecen los tamaños \(1,2,\dots,n\), pero cada tamaño puede estar en dos estados orientados, escritos como \((s,0)\) y \((s,1)\). Un apilamiento legal no es una secuencia arbitraria: desde la copa orientada actual solo se puede avanzar por una pequeña lista de transiciones permitidas, y al final cada tamaño debe haberse usado exactamente una vez. Por eso la longitud del camino es \(n\) y no \(2n\): usar el tamaño \(s\) en una orientación ya impide volver a usar el mismo tamaño en la orientación opuesta.
Si \(S(n)\) denota el número de caminos completos válidos, las implementaciones calculan \(S(10^7)\bmod(10^9+7)\). Una búsqueda exhaustiva de todos los caminos solo es viable para \(n\) muy pequeño, así que la solución tiene dos capas: conteo exacto en un espacio de estados pequeño y una recurrencia lineal fija para los valores grandes.
El contenido matemático de las implementaciones gira alrededor de tres objetos concretos del problema: el grafo dirigido de copas orientadas, la invariante de que el conjunto visitado se lleva por tamaños y no por vértices orientados, y la recurrencia de orden \(8\) que toma el relevo una vez certificados los valores iniciales.
Para cada tamaño \(s\in\{1,\dots,n\}\) y cada orientación \(o\in\{0,1\}\), introducimos un vértice \((s,o)\). Las transiciones permitidas son
$$ (s,0)\to(s-1,0),\qquad (s,0)\to(s-2,1),\qquad (s,0)\to(s+2,1), $$
$$ (s,1)\to(s+1,1),\qquad (s,1)\to(s-2,0),\qquad (s,1)\to(s+2,0), $$
siempre que el tamaño destino siga dentro de \(\{1,\dots,n\}\). Cada estado tiene, por tanto, grado de salida a lo sumo \(3\). Hay dos clases de movimiento:
los movimientos que conservan la orientación cambian el tamaño en \(1\), y los movimientos que cambian la orientación cambian el tamaño en \(2\).
Esto ya explica la naturaleza local del problema. Ningún paso salta arbitrariamente lejos; todo ocurre entre tamaños vecinos. Esa localidad es la razón profunda por la que, para \(n\) grande, todo acaba reducido a una recurrencia corta.
Podría parecer natural contar caminos sobre el grafo dirigido de \(2n\) vértices. Sin embargo, ese no es el espacio de estados correcto, porque la regla es "usar cada tamaño una sola vez", no "visitar cada vértice orientado una sola vez". Por eso las implementaciones recuerdan únicamente qué tamaños ya aparecieron.
Definimos
$$ F(M,s,o) $$
como el número de completaciones legales desde el estado actual \((s,o)\) cuando el conjunto de tamaños ya usados es exactamente \(M\subseteq\{1,\dots,n\}\), con \(s\in M\). La condición terminal es
$$ F(\{1,\dots,n\},s,o)=1, $$
porque un camino que ya ha consumido todos los tamaños está completo. En caso contrario, el siguiente paso debe ir a un vecino permitido \((t,p)\) cuyo tamaño \(t\) todavía no pertenezca a \(M\), así que
$$ F(M,s,o)=\sum_{\substack{(s,o)\to(t,p)\\ t\notin M}} F(M\cup\{t\},t,p). $$
El total buscado es entonces
$$ S(n)=\sum_{s=1}^{n}\sum_{o=0}^{1} F(\{s\},s,o). $$
Esta relación no es una plantilla genérica: expresa exactamente la invariante central de Problem 907, a saber, que las dos orientaciones de un mismo tamaño comparten un único puesto en el camino.
Para \(n=3\), tomemos el estado inicial \((1,1)\). Las salidas permitidas son \((2,1)\) y \((3,0)\), de modo que
$$ F(\{1\},1,1)=F(\{1,2\},2,1)+F(\{1,3\},3,0). $$
Desde \((2,1)\) con tamaños usados \(\{1,2\}\), la única continuación legal no usada es \((3,1)\), por lo que
$$ F(\{1,2\},2,1)=F(\{1,2,3\},3,1)=1. $$
Desde \((3,0)\) con tamaños usados \(\{1,3\}\), la única continuación posible es \((2,0)\), así que
$$ F(\{1,3\},3,0)=F(\{1,2,3\},2,0)=1. $$
Por tanto,
$$ F(\{1\},1,1)=2. $$
Los dos caminos completos son
$$ (1,1)\to(2,1)\to(3,1) $$
y
$$ (1,1)\to(3,0)\to(2,0). $$
Al sumar sobre todos los estados iniciales se obtiene \(S(3)=6\), exactamente el valor certificado que luego alimenta el método rápido.
La recurrencia exacta anterior sigue siendo exponencial porque \(M\) puede ser cualquier subconjunto. Para \(n\) grande, las implementaciones explotan un segundo hecho estructural: cada movimiento cambia el tamaño solo en \(1\) o \(2\). Al pasar de los tamaños \(\{1,\dots,n-1\}\) a \(\{1,\dots,n\}\), la nueva copa más grande solo puede interactuar con una franja acotada cerca del extremo superior. Eso permite comprimir el borde aún no completado en un número finito de patrones.
Tras eliminar esos contadores auxiliares, las implementaciones usan la recurrencia escalar
$$ S_n=2S_{n-1}-3S_{n-2}+5S_{n-3}-4S_{n-4}+4S_{n-5}-3S_{n-6}+S_{n-7}-S_{n-8}, \qquad n\ge 10. $$
El código de producción no expone ese sistema auxiliar de frontera; almacena directamente la forma reducida de una dimensión. Pero su validez no se supone sin más, porque se apoya en conteos exactos para \(n\) pequeño.
Los valores iniciales usados por la recurrencia son
$$ S(1)=2,\ S(2)=2,\ S(3)=6,\ S(4)=12,\ S(5)=16,\ S(6)=22,\ S(7)=36,\ S(8)=58,\ S(9)=82. $$
Una aplicación de la recurrencia da
$$ \begin{aligned} S_{10}&=2\cdot 82-3\cdot 58+5\cdot 36-4\cdot 22+4\cdot 16-3\cdot 12+6-2\\ &=164-174+180-88+64-36+6-2\\ &=114. \end{aligned} $$
La búsqueda exacta para casos pequeños confirma que \(S(10)=114\), de modo que la recurrencia rápida parte de valores ya contrastados con el conteo combinatorio real.
Las implementaciones en C++, Python y Java calculan la misma sucesión. La versión en C++ además incorpora una verificación exacta para \(n\) pequeño.
La implementación en C++ construye primero el grafo dirigido sobre los \(2n\) estados orientados. Después memoiza la función \(F(M,s,o)\) usando tres datos: una máscara de bits para los tamaños usados, el tamaño actual y la orientación actual. Esta elección es la traducción directa de la matemática: la máscara registra tamaños, porque elegir una orientación del tamaño \(s\) consume el tamaño \(s\) por completo.
Con ello se comprueban los valores exactos para \(n=1,\dots,10\). La tabla \(2,2,6,12,16,22,36,58,82,114\) no se toma como hipótesis, sino que se obtiene directamente del conteo exacto de caminos.
Una vez fijadas las semillas, las tres implementaciones pasan a la recurrencia rápida. Conservan solo los últimos ocho valores, forman el siguiente término con coeficientes fijos, reducen módulo \(10^9+7\), normalizan tras las restas y desplazan la ventana una posición.
La implementación en C++ también comprueba puntos de control como \(S(4)=12\), \(S(8)=58\) y \(S(20)=5560\). Las implementaciones en Python y Java contienen solo la parte de producción, porque la recurrencia basta una vez verificados los valores iniciales.
La verificación exacta tiene un número exponencial de estados de subconjuntos. En el peor caso hay \(O(n2^n)\) estados memorizados para \((M,s)\), duplicados por el bit de orientación, y cada estado inspecciona a lo sumo tres aristas salientes. Por eso el método exacto es exponencial y solo sirve para certificar casos pequeños.
La computación principal es mucho más ligera. Cada nuevo término \(S_n\) requiere un número constante de sumas y restas modulares, así que calcular hasta \(S(10^7)\) cuesta \(O(n)\) tiempo y \(O(1)\) memoria extra.
在 Problem 907 中，杯子的尺寸是 \(1,2,\dots,n\)，但每个尺寸都有两个带方向的状态，记作 \((s,0)\) 与 \((s,1)\)。合法的叠杯顺序并不是任意排列，而是一条受限的有向路径：从当前的有向杯子出发，只能沿着规定的几种转移继续走，并且最终每个尺寸必须恰好使用一次。因此路径长度是 \(n\)，不是 \(2n\)。原因在于，一旦尺寸 \(s\) 已经以某个方向出现过，那么同一个尺寸的另一种方向也就不能再使用了。
记 \(S(n)\) 为所有合法完整路径的总数。实现的目标是计算 \(S(10^7)\bmod(10^9+7)\)。如果直接枚举所有可能路径，只有在很小的 \(n\) 上才可行，所以解法分成两层：先对小 \(n\) 做精确状态计数，再对大 \(n\) 使用一个固定的线性递推。
这些实现中的数学结构围绕三个真正的题目对象展开：带方向杯子构成的有向图、只按“尺寸是否已用”而不是按“有向状态是否访问过”来记录历史的核心不变量，以及在初值被验证之后接管大规模计算的 \(8\) 阶线性递推。
对每个尺寸 \(s\in\{1,\dots,n\}\) 和方向 \(o\in\{0,1\}\)，引入一个顶点 \((s,o)\)。允许的转移为
$$ (s,0)\to(s-1,0),\qquad (s,0)\to(s-2,1),\qquad (s,0)\to(s+2,1), $$
$$ (s,1)\to(s+1,1),\qquad (s,1)\to(s-2,0),\qquad (s,1)\to(s+2,0), $$
前提是目标尺寸仍然位于 \(\{1,\dots,n\}\) 内。所以每个状态的出度至多为 \(3\)。这些边可以分成两类：
保持方向不变的边会把尺寸改动 \(1\)，改变方向的边会把尺寸改动 \(2\)。
这一点直接体现了问题的“局部性”。每一步都只会接触到邻近尺寸，而不会跨越很远。正是这种局部性，最终让大规模情形能够压缩成一个很短的线性递推。
如果只看原始图，很容易误以为这是在 \(2n\) 个有向顶点上的 Hamilton 路径计数。但这并不正确，因为题目的限制不是“每个有向顶点访问一次”，而是“每个尺寸使用一次”。因此实现中记录的不是访问过哪些有向状态，而是哪些尺寸已经出现过。
定义
$$ F(M,s,o) $$
表示当前位于状态 \((s,o)\)，并且已使用尺寸集合恰为 \(M\subseteq\{1,\dots,n\}\) 时，后续合法完成方式的数量，其中 \(s\in M\)。终止条件是
$$ F(\{1,\dots,n\},s,o)=1, $$
因为如果所有尺寸都已经出现，那么这条路径就已经完整。否则，下一步必须走向一个允许的邻居 \((t,p)\)，并且尺寸 \(t\) 还没有出现在 \(M\) 中，因此有
$$ F(M,s,o)=\sum_{\substack{(s,o)\to(t,p)\\ t\notin M}} F(M\cup\{t\},t,p). $$
总计数于是为
$$ S(n)=\sum_{s=1}^{n}\sum_{o=0}^{1} F(\{s\},s,o). $$
这不是一个可以套用到任何题目的通用模板，而是对本题核心不变量的精确表达：同一尺寸的两种方向共享路径中的同一个“名额”。
当 \(n=3\) 时，考虑起点 \((1,1)\)。它的合法后继是 \((2,1)\) 和 \((3,0)\)，因此
$$ F(\{1\},1,1)=F(\{1,2\},2,1)+F(\{1,3\},3,0). $$
对于 \((2,1)\) 且已使用尺寸为 \(\{1,2\}\) 的情况，唯一仍未使用且合法的下一步是 \((3,1)\)，所以
$$ F(\{1,2\},2,1)=F(\{1,2,3\},3,1)=1. $$
对于 \((3,0)\) 且已使用尺寸为 \(\{1,3\}\) 的情况，唯一还能走的合法下一步是 \((2,0)\)，于是
$$ F(\{1,3\},3,0)=F(\{1,2,3\},2,0)=1. $$
因此
$$ F(\{1\},1,1)=2. $$
这两个完整路径分别是
$$ (1,1)\to(2,1)\to(3,1) $$
以及
$$ (1,1)\to(3,0)\to(2,0). $$
再对所有可能起点求和，就得到 \(S(3)=6\)。这个值也正是后续快速算法所依赖的已验证初值之一。
上面的精确递归虽然正确，但因为 \(M\) 可以是任意子集，所以复杂度仍然是指数级。对于大 \(n\)，实现利用了另一个结构事实：每次移动只会把尺寸改变 \(1\) 或 \(2\)。当问题从 \(\{1,\dots,n-1\}\) 扩展到 \(\{1,\dots,n\}\) 时，新加入的最大尺寸只可能与顶部附近有限个尺寸发生相互作用。换句话说，真正需要跟踪的只是靠近边界的有限种局部模式。
把这些辅助边界计数消去之后，实现中使用的是下面这个一维标量递推：
$$ S_n=2S_{n-1}-3S_{n-2}+5S_{n-3}-4S_{n-4}+4S_{n-5}-3S_{n-6}+S_{n-7}-S_{n-8}, \qquad n\ge 10. $$
生产代码并没有把那套辅助边界状态显式写出来；它直接保存了已经化简后的最终递推式。但这个递推并不是凭空相信的，因为它的种子值已经由小规模精确计数验证过。
递推所使用的初值是
$$ S(1)=2,\ S(2)=2,\ S(3)=6,\ S(4)=12,\ S(5)=16,\ S(6)=22,\ S(7)=36,\ S(8)=58,\ S(9)=82. $$
将递推式应用一次即可得到
$$ \begin{aligned} S_{10}&=2\cdot 82-3\cdot 58+5\cdot 36-4\cdot 22+4\cdot 16-3\cdot 12+6-2\\ &=164-174+180-88+64-36+6-2\\ &=114. \end{aligned} $$
小规模精确搜索同样会确认 \(S(10)=114\)。因此，滚动递推并不是在未经验证的数列上机械外推，而是建立在真实组合计数已经核对过的起点之上。
C++、Python 和 Java 实现最终都在计算同一个序列，只是 C++ 版本额外内置了一个小规模精确验证器。
C++ 实现首先建立 \(2n\) 个有向状态组成的转移图，然后对 \(F(M,s,o)\) 做记忆化搜索。状态由三部分信息决定：已使用尺寸的位掩码、当前尺寸、当前方向。这里最关键的实现选择正是来自数学本身：位掩码记录的是尺寸，而不是有向顶点，因为一旦选择了尺寸 \(s\) 的某个方向，尺寸 \(s\) 整体都已经被占用。
借助这一层精确计算，\(n=1,\dots,10\) 的值都被直接核对出来，所以表格 \(2,2,6,12,16,22,36,58,82,114\) 不是猜测，而是由原始路径定义直接算出的。
初值确定之后，三个实现都会切换到快速递推部分。它们只保留最近的八项，用固定系数组合出新值，对 \(10^9+7\) 取模，在减法之后做规范化，然后把滑动窗口向前推进一格。
C++ 实现还会额外检查若干校验点，包括 \(S(4)=12\)、\(S(8)=58\) 以及 \(S(20)=5560\)。Python 和 Java 实现只保留生产计算部分，因为在种子值可信之后，递推本身已经足够完成目标计算。
精确验证器的状态数随子集数量呈指数增长。最坏情况下，\((M,s)\) 这对信息对应 \(O(n2^n)\) 个记忆化状态，再乘上一个方向位也只是常数倍；每个状态最多检查三条出边。因此精确方法是指数级的，只适合做小规模认证。
真正的生产计算则非常轻量。每个新项 \(S_n\) 只需要常数次模加法和模减法，所以一直算到 \(S(10^7)\) 的总代价是 \(O(n)\) 时间和 \(O(1)\) 额外空间。
В Problem 907 размеры стаканов равны \(1,2,\dots,n\), но у каждого размера есть два ориентированных состояния, записываемых как \((s,0)\) и \((s,1)\). Допустимая укладка не является произвольной последовательностью. Из текущего ориентированного стакана можно переходить только по небольшому набору разрешённых дуг, и в конце каждый размер должен быть использован ровно один раз. Поэтому длина пути равна \(n\), а не \(2n\): если размер \(s\) уже появился в одной ориентации, то во второй ориентации его использовать уже нельзя.
Обозначим через \(S(n)\) число всех допустимых полных путей. Реализации вычисляют \(S(10^7)\bmod(10^9+7)\). Полный перебор возможен лишь для очень малых \(n\), поэтому решение построено в два слоя: точный подсчёт по состояниям для малых значений и фиксированная линейная рекурсия для больших.
Математическая структура реализаций опирается на три конкретных объекта задачи: ориентированный граф на состояниях стаканов, инвариант "множество использованных размеров", а не "множество посещённых ориентированных вершин", и рекурсию порядка \(8\), которая начинает работать после проверки начальных значений.
Для каждого размера \(s\in\{1,\dots,n\}\) и ориентации \(o\in\{0,1\}\) введём вершину \((s,o)\). Разрешённые переходы имеют вид
$$ (s,0)\to(s-1,0),\qquad (s,0)\to(s-2,1),\qquad (s,0)\to(s+2,1), $$
$$ (s,1)\to(s+1,1),\qquad (s,1)\to(s-2,0),\qquad (s,1)\to(s+2,0), $$
если целевой размер остаётся внутри \(\{1,\dots,n\}\). Значит, у каждого состояния не более трёх исходящих дуг. При этом есть два типа ходов:
ходы без смены ориентации меняют размер на \(1\), а ходы со сменой ориентации меняют размер на \(2\).
Отсюда сразу видна локальность задачи. Ни один ход не затрагивает далёкие размеры; взаимодействуют только соседние области. Именно эта локальность позже позволяет сжать задачу при больших \(n\) до короткой линейной рекурсии.
Сначала может показаться, что нужно считать гамильтоновы пути в ориентированном графе на \(2n\) вершинах. Но это неверная постановка: правило задачи требует использовать каждый размер ровно один раз, а не посещать каждую ориентированную вершину. Поэтому реализации хранят только то, какие размеры уже были использованы.
Обозначим через
$$ F(M,s,o) $$
число допустимых продолжений из состояния \((s,o)\), если множество уже использованных размеров равно \(M\subseteq\{1,\dots,n\}\), причём \(s\in M\). Граничное условие таково:
$$ F(\{1,\dots,n\},s,o)=1, $$
потому что путь, в котором уже использованы все размеры, завершён. В остальных случаях следующий ход должен вести в допустимого соседа \((t,p)\), где размер \(t\) ещё не входит в \(M\). Поэтому
$$ F(M,s,o)=\sum_{\substack{(s,o)\to(t,p)\\ t\notin M}} F(M\cup\{t\},t,p). $$
Полный ответ тогда равен
$$ S(n)=\sum_{s=1}^{n}\sum_{o=0}^{1} F(\{s\},s,o). $$
Это не универсальная формула-заготовка, а точное выражение ключевого инварианта задачи: две ориентации одного и того же размера борются за одно место в пути.
Пусть \(n=3\), и мы начинаем из состояния \((1,1)\). Разрешённые выходы ведут в \((2,1)\) и \((3,0)\), так что
$$ F(\{1\},1,1)=F(\{1,2\},2,1)+F(\{1,3\},3,0). $$
Из \((2,1)\) при использованных размерах \(\{1,2\}\) единственное допустимое продолжение на новый размер ведёт в \((3,1)\), следовательно
$$ F(\{1,2\},2,1)=F(\{1,2,3\},3,1)=1. $$
Из \((3,0)\) при использованных размерах \(\{1,3\}\) остаётся только \((2,0)\), и поэтому
$$ F(\{1,3\},3,0)=F(\{1,2,3\},2,0)=1. $$
Значит,
$$ F(\{1\},1,1)=2. $$
Два полных пути таковы:
$$ (1,1)\to(2,1)\to(3,1) $$
и
$$ (1,1)\to(3,0)\to(2,0). $$
Если просуммировать по всем стартовым состояниям, получится \(S(3)=6\). Это точно совпадает с проверенным начальным значением, которое затем используется в быстром алгоритме.
Точная рекурсия выше остаётся экспоненциальной, потому что \(M\) может быть любым подмножеством. Для больших \(n\) реализации используют другой структурный факт: каждый ход меняет размер только на \(1\) или \(2\). Когда задача расширяется с \(\{1,\dots,n-1\}\) до \(\{1,\dots,n\}\), новый максимальный размер может взаимодействовать только с ограниченной каймой возле верхнего края. Значит, незавершённую верхнюю границу можно описать конечным числом локальных шаблонов.
После исключения этих вспомогательных счётчиков реализации используют скалярную рекурсию
$$ S_n=2S_{n-1}-3S_{n-2}+5S_{n-3}-4S_{n-4}+4S_{n-5}-3S_{n-6}+S_{n-7}-S_{n-8}, \qquad n\ge 10. $$
В производственной части программ вспомогательная краевая система явно не хранится; там сразу записана её одномерная свёртка. Но эта рекурсия не берётся на веру, потому что её начальные значения подтверждены точным перебором.
В качестве начальных значений используются
$$ S(1)=2,\ S(2)=2,\ S(3)=6,\ S(4)=12,\ S(5)=16,\ S(6)=22,\ S(7)=36,\ S(8)=58,\ S(9)=82. $$
Одно применение рекурсии даёт
$$ \begin{aligned} S_{10}&=2\cdot 82-3\cdot 58+5\cdot 36-4\cdot 22+4\cdot 16-3\cdot 12+6-2\\ &=164-174+180-88+64-36+6-2\\ &=114. \end{aligned} $$
Точный перебор для малых \(n\) также подтверждает, что \(S(10)=114\). Значит, быстрая рекурсия стартует с чисел, уже сверенных с подлинным комбинаторным подсчётом.
Реализации на C++, Python и Java вычисляют одну и ту же последовательность. Версия на C++ дополнительно содержит встроенную точную проверку для малых \(n\).
Сначала C++-реализация строит ориентированный граф на \(2n\) состояниях. Затем она мемоизирует функцию \(F(M,s,o)\), используя три компоненты: битовую маску использованных размеров, текущий размер и текущую ориентацию. Это ключевое решение диктуется самой математикой: маска хранит именно размеры, потому что выбор одной ориентации размера \(s\) полностью расходует размер \(s\).
Так проверяются точные значения для \(n=1,\dots,10\). Последовательность \(2,2,6,12,16,22,36,58,82,114\) не предполагается заранее, а получается напрямую из определения через подсчёт путей.
После фиксации начальных значений все три реализации переходят к быстрой рекурсии. Они держат только последние восемь значений, собирают следующий член с фиксированными коэффициентами, берут остаток по модулю \(10^9+7\), нормализуют после вычитаний и сдвигают окно на один шаг.
Версия на C++ дополнительно проверяет контрольные точки \(S(4)=12\), \(S(8)=58\) и \(S(20)=5560\). Реализации на Python и Java оставляют только производственную часть, поскольку после подтверждения начальных значений самой рекурсии уже достаточно.
Точный проверочный алгоритм имеет экспоненциально много состояний по подмножествам. В худшем случае существует \(O(n2^n)\) мемо-состояний для пары \((M,s)\), а бит ориентации добавляет лишь постоянный множитель; каждое состояние рассматривает не более трёх исходящих дуг. Поэтому точный метод экспоненциален и пригоден только для малых сертификационных примеров.
Основное вычисление гораздо дешевле. Каждый новый член \(S_n\) требует лишь константного числа модульных сложений и вычитаний, так что подсчёт до \(S(10^7)\) занимает \(O(n)\) времени и \(O(1)\) дополнительной памяти.
في Problem 907 لدينا أحجام الأكواب \(1,2,\dots,n\)، لكن لكل حجم حالتان اتجاهيتان تُكتبان \((s,0)\) و\((s,1)\). والتكديس القانوني ليس مجرد ترتيب عشوائي، بل هو مسار موجّه مقيّد: من الكوب الحالي ذي الاتجاه المعين لا يجوز الانتقال إلا عبر عدد صغير من الحركات المسموح بها، وفي النهاية يجب أن يكون كل حجم قد استُخدم مرة واحدة بالضبط. لهذا يكون طول المسار \(n\) لا \(2n\)، لأن استعمال الحجم \(s\) في أحد الاتجاهين يمنع استعمال الحجم نفسه مرة أخرى في الاتجاه الآخر.
إذا رمزنا بعدد المسارات الكاملة الصحيحة بـ \(S(n)\)، فإن التطبيقات تحسب \(S(10^7)\bmod(10^9+7)\). والبحث الشامل في جميع المسارات الممكنة لا يصلح إلا للقيم الصغيرة جدًا من \(n\)، لذلك يتكون الحل من مستويين: عدّ دقيق في فضاء الحالات للحالات الصغيرة، ثم علاقة تكرارية خطية ثابتة للحالات الكبيرة.
البنية الرياضية في التطبيقات تدور حول ثلاثة أشياء حقيقية خاصة بهذه المسألة: الرسم البياني الموجّه على حالات الأكواب الاتجاهية، والثابتة التي تقول إن ما نتابعه هو الأحجام المستعملة لا الرؤوس الاتجاهية المزارة، ثم العلاقة التكرارية من الرتبة الثامنة التي تتولى الحساب الكبير بعد التحقق من القيم الابتدائية.
لكل حجم \(s\in\{1,\dots,n\}\) ولكل اتجاه \(o\in\{0,1\}\)، نعرّف رأسًا \((s,o)\). والانتقالات المسموح بها هي
$$ (s,0)\to(s-1,0),\qquad (s,0)\to(s-2,1),\qquad (s,0)\to(s+2,1), $$
$$ (s,1)\to(s+1,1),\qquad (s,1)\to(s-2,0),\qquad (s,1)\to(s+2,0), $$
بشرط أن يبقى الحجم الهدف داخل المجموعة \(\{1,\dots,n\}\). ولذلك فدرجة الخروج لكل حالة لا تتجاوز \(3\). وهناك نوعان من الحركات:
حركات تحافظ على الاتجاه وتغيّر الحجم بمقدار \(1\)، وحركات تقلب الاتجاه وتغيّر الحجم بمقدار \(2\).
ومن هنا تظهر الطبيعة المحلية للمسألة. فلا توجد قفزات بعيدة اعتباطية؛ كل خطوة تتفاعل فقط مع أحجام قريبة. وهذه المحلية هي السبب البنيوي الذي يسمح في النهاية بضغط المسألة الكبيرة إلى علاقة تكرارية قصيرة.
قد يبدو في البداية أن المطلوب هو عدّ مسارات هاملتونية في الرسم البياني ذي \(2n\) رأسًا. لكن هذا ليس هو فضاء الحالات الصحيح، لأن القاعدة في المسألة هي "استعمل كل حجم مرة واحدة" لا "زر كل حالة اتجاهية مرة واحدة". ولهذا تحتفظ التطبيقات فقط بمعلومة الأحجام التي ظهرت بالفعل.
لنعرّف
$$ F(M,s,o) $$
على أنه عدد الإكمالات الصحيحة انطلاقًا من الحالة الحالية \((s,o)\) عندما تكون مجموعة الأحجام المستعملة بالضبط هي \(M\subseteq\{1,\dots,n\}\)، مع الشرط \(s\in M\). أما شرط التوقف فهو
$$ F(\{1,\dots,n\},s,o)=1, $$
لأن المسار يكون قد اكتمل إذا استُعملت جميع الأحجام. وفي غير ذلك يجب أن تكون الخطوة التالية إلى جار مسموح \((t,p)\) بحيث لا يكون الحجم \(t\) قد استُعمل بعد، ومن ثم
$$ F(M,s,o)=\sum_{\substack{(s,o)\to(t,p)\\ t\notin M}} F(M\cup\{t\},t,p). $$
وبذلك يصبح العدد الكلي المطلوب
$$ S(n)=\sum_{s=1}^{n}\sum_{o=0}^{1} F(\{s\},s,o). $$
هذه ليست صيغة عامة تصلح لعشرات المسائل، بل هي الترجمة الدقيقة للثابتة الأساسية هنا: الاتجاهان الممكنان للحجم نفسه يتنافسان على موضع واحد فقط داخل المسار.
عندما \(n=3\)، خذ الحالة الابتدائية \((1,1)\). الحركتان المسموح بهما من هذه الحالة هما إلى \((2,1)\) وإلى \((3,0)\)، ولذلك
$$ F(\{1\},1,1)=F(\{1,2\},2,1)+F(\{1,3\},3,0). $$
من الحالة \((2,1)\) مع الأحجام المستعملة \(\{1,2\}\)، يكون الامتداد الوحيد القانوني إلى حجم غير مستعمل هو \((3,1)\)، ومن ثم
$$ F(\{1,2\},2,1)=F(\{1,2,3\},3,1)=1. $$
ومن الحالة \((3,0)\) مع الأحجام المستعملة \(\{1,3\}\)، يبقى الامتداد الوحيد الممكن هو \((2,0)\)، لذا
$$ F(\{1,3\},3,0)=F(\{1,2,3\},2,0)=1. $$
إذن
$$ F(\{1\},1,1)=2. $$
والمساران الكاملان هما
$$ (1,1)\to(2,1)\to(3,1) $$
و
$$ (1,1)\to(3,0)\to(2,0). $$
وبجمع جميع حالات البداية نحصل على \(S(3)=6\)، وهو بالضبط أحد القيم الابتدائية الموثقة التي يعتمد عليها الجزء السريع لاحقًا.
العلاقة الدقيقة السابقة ما تزال أُسّية لأن \(M\) يمكن أن تكون أي مجموعة جزئية. أما في القيم الكبيرة لـ \(n\)، فتستفيد التطبيقات من حقيقة بنيوية ثانية: كل حركة تغيّر الحجم بمقدار \(1\) أو \(2\) فقط. وعندما نوسّع المسألة من \(\{1,\dots,n-1\}\) إلى \(\{1,\dots,n\}\)، فإن أكبر حجم جديد لا يمكنه أن يتفاعل إلا مع شريط محدود قريب من الطرف الأعلى. وهذا يعني أن الحدّ غير المكتمل قرب الطرف يمكن ضغطه في عدد منتهٍ من الأنماط المحلية.
وبعد حذف هذه العدادات المساعدة، تستعمل التطبيقات العلاقة التكرارية العددية
$$ S_n=2S_{n-1}-3S_{n-2}+5S_{n-3}-4S_{n-4}+4S_{n-5}-3S_{n-6}+S_{n-7}-S_{n-8}, \qquad n\ge 10. $$
الكود الإنتاجي لا يبني نظام الأنماط الحدّية هذا بشكل صريح، بل يخزّن مباشرة الصورة المختزلة أحادية البعد. لكن صحة هذه العلاقة ليست افتراضًا مجردًا، لأنها مثبتة عمليًا عبر العدّ الدقيق للقيم الصغيرة.
القيم الابتدائية المستعملة هي
$$ S(1)=2,\ S(2)=2,\ S(3)=6,\ S(4)=12,\ S(5)=16,\ S(6)=22,\ S(7)=36,\ S(8)=58,\ S(9)=82. $$
وباستخدام العلاقة مرة واحدة نحصل على
$$ \begin{aligned} S_{10}&=2\cdot 82-3\cdot 58+5\cdot 36-4\cdot 22+4\cdot 16-3\cdot 12+6-2\\ &=164-174+180-88+64-36+6-2\\ &=114. \end{aligned} $$
والعدّ الدقيق للحالات الصغيرة يؤكد أيضًا أن \(S(10)=114\). لذلك فإن التكرار السريع لا يبدأ من قيم مفترضة، بل من قيم طابقت العدّ التوافقي الحقيقي للمسألة.
تقوم تطبيقات C++ وPython وJava كلها بحساب المتتالية نفسها، لكن نسخة C++ تحتوي أيضًا على طبقة تحقق دقيقة للقيم الصغيرة.
تبدأ نسخة C++ ببناء الرسم البياني الموجّه على \(2n\) حالة اتجاهية. ثم تقوم بتخزين الدالة \(F(M,s,o)\) اعتمادًا على ثلاث قطع من المعلومات: قناع بتّي للأحجام المستعملة، والحجم الحالي، والاتجاه الحالي. وهذا القرار البرمجي هو انعكاس مباشر للرياضيات: القناع يتتبع الأحجام فقط، لأن اختيار اتجاه واحد للحجم \(s\) يستهلك الحجم \(s\) بالكامل.
وبهذه الطريقة يتم التحقق من القيم الدقيقة لـ \(n=1,\dots,10\). وبالتالي فإن الجدول \(2,2,6,12,16,22,36,58,82,114\) ليس تخمينًا، بل ناتج مباشرة من تعريف المسارات القانونية.
بعد تثبيت البذور، تنتقل التطبيقات الثلاثة إلى الجزء السريع. فهي تحتفظ بآخر ثمانية حدود فقط، وتكوّن الحد الجديد بمعاملات ثابتة، ثم تأخذ النتيجة بترديد \(10^9+7\)، وتعيد التطبيع بعد الطروح، ثم تحرك النافذة خطوة واحدة إلى الأمام.
كما تختبر نسخة C++ نقاط تحقق إضافية مثل \(S(4)=12\) و\(S(8)=58\) و\(S(20)=5560\). أما نسختا Python وJava فتكتفيان بجزء الإنتاج، لأن العلاقة وحدها تكفي بعد الوثوق بالقيم الابتدائية.
خوارزمية التحقق الدقيقة تملك عددًا أُسّيًا من حالات المجموعات الجزئية. ففي أسوأ الأحوال يوجد \(O(n2^n)\) من الحالات المخزنة للزوج \((M,s)\)، ويضيف بت الاتجاه مجرد عامل ثابت، كما أن كل حالة تفحص في الأكثر ثلاث حواف خارجة. لذلك فالطريقة الدقيقة أُسّية ولا تصلح إلا لأمثلة التحقق الصغيرة.
أما الحساب الفعلي فهو أخف بكثير. فكل حد جديد \(S_n\) يحتاج إلى عدد ثابت من عمليات الجمع والطرح بترديد \(10^9+7\)، ولذلك فإن الوصول إلى \(S(10^7)\) يكلف \(O(n)\) زمنًا و\(O(1)\) ذاكرة إضافية.