For each \(n\), three rods are placed at positions \(3^n\), \(6^n\), and \(9^n\) on a circular track of length \(10^n\). The task is to perform the canonical three-rod Hanoi transfer from the first rod to the third rod, using the middle rod as auxiliary, and to measure the total weighted travel cost of the mover.
The mover begins at the middle rod. A direct simulation would expand a Hanoi move list of exponential length, so the solution does not enumerate individual disk states. Instead, it counts how many times each directed rod-to-rod transition occurs and combines those counts with a closed-form cost for the corresponding geometric movement.
The required output is
$$\sum_{n=1}^{10000} E_n \pmod{10^9},$$
where \(E_n\) denotes the cost of the \(n\)-disk instance.
The key observation is that the Hanoi recursion only needs a tiny fixed state: the orientation of the subproblem and the number of directed transitions between the three rods.
Label the rods \(0,1,2\) in increasing position order. An orientation \((f,t,a)\) means: move the whole tower from source rod \(f\) to target rod \(t\), using rod \(a\) as auxiliary. Since \((f,t,a)\) is a permutation of \((0,1,2)\), there are exactly six orientations.
For each orientation and disk count \(n\), define a \(3\times 3\) matrix
$$T_n^{(f,t,a)}=\bigl(T_n^{(f,t,a)}(i,j)\bigr)_{0\le i,j\le 2},$$
where \(T_n^{(f,t,a)}(i,j)\) is the number of directed transitions \(i\to j\) that occur after the mover has already reached the source rod of that subproblem. This convention leaves the very first walk of the whole instance to a separate term.
Let \(U_{u,v}\) be the \(3\times 3\) matrix whose only nonzero entry is a \(1\) at row \(u\), column \(v\). For one disk, once the mover is already standing at the source rod, the task is just a single loaded move:
$$T_1^{(f,t,a)}=U_{f,t}.$$
For \(n\ge 2\), the standard Hanoi decomposition says:
1. move the top \(n-1\) disks from \(f\) to \(a\) using \(t\),
2. return from \(a\) to \(f\),
3. carry the largest disk from \(f\) to \(t\),
4. walk from \(t\) to \(a\),
5. move the \(n-1\) disks from \(a\) to \(t\) using \(f\).
Therefore
$$T_n^{(f,t,a)}=T_{n-1}^{(f,a,t)}+\Delta^{(f,t,a)}+T_{n-1}^{(a,t,f)},$$
with
$$\Delta^{(f,t,a)}=U_{a,f}+U_{f,t}+U_{t,a}.$$
This recurrence is exact, and it only updates six fixed-size matrices for each new \(n\).
Now fix a circle size \(K\) and rod positions \(1\le x,y\le K\). The code uses a weighted travel rule that depends on direction.
If \(x<y\), the move goes forward through the arc from \(x\) to \(y\). The crossed segment weights are
$$2x-1,\ 2x+1,\ \dots,\ 2y-3,$$
so the cost is the arithmetic-series sum
$$h_K(x,y)=\sum_{r=x}^{y-1}(2r-1)=(y-x)(x+y-2).$$
If \(x>y\), the directed move wraps around the far side of the circle. The segment weights are then
$$2K-2y+1,\ 2K-2y-1,\ \dots,\ 2K-2x+3,$$
which gives
$$h_K(x,y)=\sum_{r=y}^{x-1}(2K-2r-1)=(x-y)(2K-x-y).$$
Combining both cases,
$$h_K(x,y)=\begin{cases} (y-x)(x+y-2), & x<y,\\ (x-y)(2K-x-y), & x>y,\\ 0, & x=y. \end{cases}$$
Suppose the three rod positions are \(p_0<p_1<p_2\) on a circle of size \(K\), and the tower must move from rod \(0\) to rod \(2\) using rod \(1\). The mover starts at rod \(1\), so the initial walk is \(1\to 0\), with cost \(h_K(p_1,p_0)\).
After that initial placement, every directed transition counted by \(T_n^{(0,2,1)}(i,j)\) contributes the cost \(h_K(p_i,p_j)\). Hence
$$E(n,K,p_0,p_1,p_2)=h_K(p_1,p_0)+\sum_{i=0}^{2}\sum_{j=0}^{2}T_n^{(0,2,1)}(i,j)\,h_K(p_i,p_j).$$
This formula converts the abstract transition matrix into the exact weighted cost of the whole \(n\)-disk task.
For the problem sequence, the geometric parameters are
$$K_n=10^n,\qquad p_0=3^n,\qquad p_1=6^n,\qquad p_2=9^n.$$
Because
$$3^n<6^n<9^n<10^n\qquad (n\ge 1),$$
the relative rod order never changes, so the correct branch of \(h_K\) is determined once and for all by the rod indices. The total requested sum is therefore
$$S(N)=\sum_{n=1}^{N} E(n,10^n,3^n,6^n,9^n)\pmod{10^9}.$$
Since only the last nine digits are needed, every multiplication and addition may be reduced modulo \(10^9\) during the dynamic program.
For \(n=2\), the canonical orientation is \((0,2,1)\). The recurrence gives
$$T_2^{(0,2,1)}=U_{0,1}+U_{1,0}+U_{0,2}+U_{2,1}+U_{1,2}.$$
So after the initial walk \(1\to 0\), the mover performs the directed transitions
$$0\to 1,\qquad 1\to 0,\qquad 0\to 2,\qquad 2\to 1,\qquad 1\to 2.$$
With \(K=5\) and positions \((1,3,5)\), the individual costs are
$$h_5(3,1)=12,\qquad h_5(1,3)=4,\qquad h_5(1,5)=16,\qquad h_5(5,3)=4,\qquad h_5(3,5)=12.$$
Therefore
$$E(2,5,1,3,5)=12+4+12+16+4+12=60,$$
which matches the small exact checkpoint used by the implementation.
The C++, Python, and Java implementations first enumerate the six orientations and store one \(3\times 3\) transition-count matrix for each of them. At \(n=1\), every orientation contains exactly one source-to-target move. For each larger \(n\), every new matrix is produced from two previously stored matrices plus the three fixed bridge transitions \(a\to f\), \(f\to t\), and \(t\to a\).
In parallel, the implementations advance the four power sequences \(3^n\), \(6^n\), \(9^n\), and \(10^n\) modulo \(10^9\). After each update they evaluate the canonical orientation \((0,2,1)\), apply the cost kernel to the current positions, and add the result to a running sum modulo \(10^9\).
The C++ implementation also checks the derivation on two exact small instances before computing the long sum:
$$E(2,5,1,3,5)=60,\qquad E(3,20,4,9,17)=2358.$$
Those checkpoints confirm that both the transition recurrence and the geometric cost formula are wired correctly.
There are always 6 orientations, and each orientation stores only 9 transition counts. Every step from \(n\) to \(n+1\) performs constant-time arithmetic on this fixed state, followed by one fixed-size cost evaluation. Hence the total running time is \(O(N)\) for summing up to \(N\), and the working memory is \(O(1)\).
Für jedes \(n\) stehen drei Stäbe an den Positionen \(3^n\), \(6^n\) und \(9^n\) auf einem Kreis der Länge \(10^n\). Gesucht sind die gewichteten Gesamtkosten, wenn der Hanoi-Turm vom ersten Stab auf den dritten bewegt wird und der mittlere Stab als Hilfsstab dient.
Der Träger startet auf dem mittleren Stab. Eine direkte Simulation der Hanoi-Zugfolge wäre exponentiell in \(n\). Deshalb zählt die Lösung nicht einzelne Scheibenbewegungen aus, sondern nur, wie oft jede gerichtete Stab-zu-Stab-Transition vorkommt, und multipliziert diese Häufigkeiten mit einer geschlossenen geometrischen Kostenformel.
Ausgegeben werden soll
$$\sum_{n=1}^{10000} E_n \pmod{10^9},$$
wobei \(E_n\) die Kosten der \(n\)-Scheiben-Instanz bezeichnet.
Die entscheidende Beobachtung ist, dass die Rekursion nur einen winzigen festen Zustand benötigt: die Orientierung des Teilproblems und die Anzahl gerichteter Übergänge zwischen den drei Stäben.
Nummeriere die Stäbe in aufsteigender Positionsreihenfolge mit \(0,1,2\). Eine Orientierung \((f,t,a)\) bedeutet: bewege den gesamten Turm vom Quellstab \(f\) zum Zielstab \(t\), wobei \(a\) der Hilfsstab ist. Da \((f,t,a)\) eine Permutation von \((0,1,2)\) ist, gibt es genau sechs Orientierungen.
Für jede Orientierung und jede Scheibenanzahl \(n\) definieren wir eine \(3\times 3\)-Matrix
$$T_n^{(f,t,a)}=\bigl(T_n^{(f,t,a)}(i,j)\bigr)_{0\le i,j\le 2},$$
wobei \(T_n^{(f,t,a)}(i,j)\) angibt, wie oft der gerichtete Übergang \(i\to j\) auftritt, nachdem der Träger den Quellstab dieses Teilproblems bereits erreicht hat. Der allererste Weg des Gesamtproblems wird also separat behandelt.
Sei \(U_{u,v}\) die \(3\times 3\)-Matrix mit genau einer \(1\) an Position \((u,v)\). Für eine Scheibe gilt, sobald der Träger bereits am Quellstab steht:
$$T_1^{(f,t,a)}=U_{f,t}.$$
Für \(n\ge 2\) zerlegt die klassische Hanoi-Rekursion die Aufgabe in:
1. bewege \(n-1\) Scheiben von \(f\) nach \(a\) mit \(t\) als Hilfe,
2. gehe von \(a\) zurück nach \(f\),
3. trage die größte Scheibe von \(f\) nach \(t\),
4. gehe von \(t\) nach \(a\),
5. bewege \(n-1\) Scheiben von \(a\) nach \(t\) mit \(f\) als Hilfe.
Daraus folgt
$$T_n^{(f,t,a)}=T_{n-1}^{(f,a,t)}+\Delta^{(f,t,a)}+T_{n-1}^{(a,t,f)},$$
mit
$$\Delta^{(f,t,a)}=U_{a,f}+U_{f,t}+U_{t,a}.$$
Diese Formel ist exakt und aktualisiert pro \(n\) nur sechs Matrizen fester Größe.
Fixiere nun eine Kreisgröße \(K\) und zwei Stabpositionen \(1\le x,y\le K\). Die Implementierung benutzt eine gewichtete Bewegungsregel, die von der Richtung abhängt.
Für \(x<y\) läuft die Bewegung vorwärts über den Bogen von \(x\) nach \(y\). Die Segmentgewichte sind
$$2x-1,\ 2x+1,\ \dots,\ 2y-3,$$
also
$$h_K(x,y)=\sum_{r=x}^{y-1}(2r-1)=(y-x)(x+y-2).$$
Für \(x>y\) geht die gerichtete Bewegung über die andere Seite des Kreises. Dann erhält man
$$2K-2y+1,\ 2K-2y-1,\ \dots,\ 2K-2x+3,$$
und somit
$$h_K(x,y)=\sum_{r=y}^{x-1}(2K-2r-1)=(x-y)(2K-x-y).$$
Zusammengefasst gilt
$$h_K(x,y)=\begin{cases} (y-x)(x+y-2), & x<y,\\ (x-y)(2K-x-y), & x>y,\\ 0, & x=y. \end{cases}$$
Seien \(p_0<p_1<p_2\) die drei Stabpositionen auf einem Kreis der Größe \(K\), und der Turm soll von Stab \(0\) nach Stab \(2\) mit Stab \(1\) als Hilfsstab bewegt werden. Da der Träger auf Stab \(1\) startet, ist der erste unvermeidliche Weg \(1\to 0\), mit Kosten \(h_K(p_1,p_0)\).
Danach trägt jeder von \(T_n^{(0,2,1)}(i,j)\) gezählte Übergang die Kosten \(h_K(p_i,p_j)\). Also
$$E(n,K,p_0,p_1,p_2)=h_K(p_1,p_0)+\sum_{i=0}^{2}\sum_{j=0}^{2}T_n^{(0,2,1)}(i,j)\,h_K(p_i,p_j).$$
Damit wird die abstrakte Übergangsmatrix in die exakten gewichteten Kosten der gesamten \(n\)-Scheiben-Aufgabe übersetzt.
Für die Problemfamilie lauten die geometrischen Parameter
$$K_n=10^n,\qquad p_0=3^n,\qquad p_1=6^n,\qquad p_2=9^n.$$
Wegen
$$3^n<6^n<9^n<10^n\qquad (n\ge 1)$$
ändert sich die Reihenfolge der Stäbe nie. Deshalb ist die richtige Fallunterscheidung in \(h_K\) allein durch die Stabindizes festgelegt. Gesucht ist also
$$S(N)=\sum_{n=1}^{N} E(n,10^n,3^n,6^n,9^n)\pmod{10^9}.$$
Da nur die letzten neun Ziffern benötigt werden, dürfen alle Zwischenrechnungen bereits während der Dynamik modulo \(10^9\) reduziert werden.
Für \(n=2\) ist die kanonische Orientierung \((0,2,1)\). Die Rekurrenz liefert
$$T_2^{(0,2,1)}=U_{0,1}+U_{1,0}+U_{0,2}+U_{2,1}+U_{1,2}.$$
Nach dem initialen Weg \(1\to 0\) führt der Träger also die gerichteten Übergänge
$$0\to 1,\qquad 1\to 0,\qquad 0\to 2,\qquad 2\to 1,\qquad 1\to 2$$
aus. Für \(K=5\) und die Positionen \((1,3,5)\) sind die Einzelkosten
$$h_5(3,1)=12,\qquad h_5(1,3)=4,\qquad h_5(1,5)=16,\qquad h_5(5,3)=4,\qquad h_5(3,5)=12.$$
Damit erhält man
$$E(2,5,1,3,5)=12+4+12+16+4+12=60,$$
genau den kleinen Kontrollwert der Implementierung.
Die C++-, Python- und Java-Implementierungen erzeugen zuerst die sechs Orientierungen und speichern für jede davon genau eine \(3\times 3\)-Matrix mit Übergangszahlen. Für \(n=1\) enthält jede Orientierung genau einen Quell-Ziel-Zug. Für jedes größere \(n\) wird jede neue Matrix aus zwei älteren Matrizen sowie den drei festen Brückenübergängen \(a\to f\), \(f\to t\) und \(t\to a\) zusammengesetzt.
Parallel dazu werden die vier Potenzfolgen \(3^n\), \(6^n\), \(9^n\) und \(10^n\) modulo \(10^9\) fortgeschrieben. Nach jedem Schritt wertet die Implementierung die kanonische Orientierung \((0,2,1)\) mit dem Kostenkern aus und addiert das Ergebnis zu einer laufenden Summe modulo \(10^9\).
Die C++-Implementierung prüft die Herleitung außerdem an zwei exakten Kleinbeispielen, bevor die lange Summe berechnet wird:
$$E(2,5,1,3,5)=60,\qquad E(3,20,4,9,17)=2358.$$
Diese Testfälle bestätigen sowohl die Übergangsrekurrenz als auch die geometrische Kostenformel.
Es gibt immer nur 6 Orientierungen, und jede Orientierung speichert genau 9 Übergangszahlen. Jeder Schritt von \(n\) nach \(n+1\) besteht daher aus konstanter Arbeit auf einem festen Zustand, gefolgt von einer Auswertung fester Größe. Die Gesamtlaufzeit bis \(N\) ist also \(O(N)\), und der benötigte Arbeitsspeicher ist \(O(1)\).
Her \(n\) için üç çubuk, uzunluğu \(10^n\) olan dairesel bir pist üzerinde \(3^n\), \(6^n\) ve \(9^n\) konumlarına yerleştirilir. Amaç, Hanoi kulesini birinci çubuktan üçüncü çubuğa, ortadaki çubuğu yardımcı olarak kullanarak taşımak ve taşıyıcının toplam ağırlıklı hareket maliyetini hesaplamaktır.
Taşıyıcı başlangıçta ortadaki çubuktadır. Doğrudan simülasyon, Hanoi hamle listesini üstel uzunlukta açmak zorunda kalır. Bu yüzden çözüm tek tek disk durumlarını izlemez; yalnızca her yönlü çubuklar-arası geçişin kaç kez gerçekleştiğini sayar ve bu sayıları ilgili geometrik hareketin kapalı form maliyetiyle birleştirir.
İstenen çıktı
$$\sum_{n=1}^{10000} E_n \pmod{10^9}$$
ifadesidir; burada \(E_n\), \(n\) diskli örneğin maliyetidir.
Temel gözlem şudur: Hanoi özyinelemesi aslında çok küçük, sabit boyutlu bir duruma indirgenebilir. Bu durum, alt problemin yönelimi ile üç çubuk arasındaki yönlü geçiş sayılarını içerir.
Çubukları artan konum sırasına göre \(0,1,2\) diye numaralandıralım. \((f,t,a)\) yönelimi, tüm kuleyi kaynak çubuk \(f\)'den hedef çubuk \(t\)'ye, \(a\) yardımcı çubuğunu kullanarak taşı demektir. \((f,t,a)\), \((0,1,2)\)'nin bir permütasyonu olduğundan toplam 6 yönelim vardır.
Her yönelim ve disk sayısı \(n\) için
$$T_n^{(f,t,a)}=\bigl(T_n^{(f,t,a)}(i,j)\bigr)_{0\le i,j\le 2}$$
şeklinde bir \(3\times 3\) matris tanımlayalım. Burada \(T_n^{(f,t,a)}(i,j)\), taşıyıcı o alt problemin kaynak çubuğuna zaten ulaşmışken gerçekleşen \(i\to j\) yönlü geçişlerinin sayısıdır. Böylece tüm problemin en başındaki ilk yürüyüş ayrı bir terim olarak tutulur.
\(U_{u,v}\), yalnızca \((u,v)\) girişinde \(1\) bulunan \(3\times 3\) matris olsun. Tek disk için, taşıyıcı kaynak çubuktaysa görev yalnızca bir yük taşıma hareketidir:
$$T_1^{(f,t,a)}=U_{f,t}.$$
\(n\ge 2\) olduğunda klasik Hanoi ayrışımı şu sırayı verir:
1. üstteki \(n-1\) diski \(f\)'den \(a\)'ya, \(t\)'yi kullanarak taşı,
2. \(a\)'dan geri \(f\)'ye yürü,
3. en büyük diski \(f\)'den \(t\)'ye taşı,
4. \(t\)'den \(a\)'ya yürü,
5. \(n-1\) diski \(a\)'dan \(t\)'ye, \(f\)'yi kullanarak taşı.
Dolayısıyla
$$T_n^{(f,t,a)}=T_{n-1}^{(f,a,t)}+\Delta^{(f,t,a)}+T_{n-1}^{(a,t,f)},$$
ve burada
$$\Delta^{(f,t,a)}=U_{a,f}+U_{f,t}+U_{t,a}.$$
Bu ilişki tamdır ve her yeni \(n\) için yalnızca sabit boyutlu 6 matrisi günceller.
Şimdi çember boyu \(K\) ve çubuk konumları \(1\le x,y\le K\) olsun. Uygulama, yöne bağlı ağırlıklı bir hareket kuralı kullanır.
Eğer \(x<y\) ise hareket, \(x\)'den \(y\)'ye doğru ileri yay üzerinden gider. Geçilen parça ağırlıkları
$$2x-1,\ 2x+1,\ \dots,\ 2y-3$$
olduğundan maliyet
$$h_K(x,y)=\sum_{r=x}^{y-1}(2r-1)=(y-x)(x+y-2)$$
olur. Eğer \(x>y\) ise yönlü hareket çemberin diğer tarafından dolaşır. O zaman ağırlıklar
$$2K-2y+1,\ 2K-2y-1,\ \dots,\ 2K-2x+3$$
şeklindedir ve
$$h_K(x,y)=\sum_{r=y}^{x-1}(2K-2r-1)=(x-y)(2K-x-y)$$
elde edilir. Böylece tek formül
$$h_K(x,y)=\begin{cases} (y-x)(x+y-2), & x<y,\\ (x-y)(2K-x-y), & x>y,\\ 0, & x=y \end{cases}$$
olur.
\(p_0<p_1<p_2\) bir çember üzerinde üç çubuk konumu ve çember boyu \(K\) olsun. Kule, \(1\) numaralı çubuğu yardımcı kullanarak \(0\)'dan \(2\)'ye taşınacaktır. Taşıyıcı başlangıçta \(1\) numaralı çubukta olduğundan ilk zorunlu yürüyüş \(1\to 0\)'dır ve maliyeti \(h_K(p_1,p_0)\)'dır.
Bundan sonra \(T_n^{(0,2,1)}(i,j)\) sayısı kadar \(i\to j\) yönlü geçiş olur ve her biri \(h_K(p_i,p_j)\) maliyeti taşır. Bu yüzden
$$E(n,K,p_0,p_1,p_2)=h_K(p_1,p_0)+\sum_{i=0}^{2}\sum_{j=0}^{2}T_n^{(0,2,1)}(i,j)\,h_K(p_i,p_j)$$
formülü, soyut matris sayımını tam ağırlıklı görev maliyetine dönüştürür.
Bu problemde geometrik parametreler
$$K_n=10^n,\qquad p_0=3^n,\qquad p_1=6^n,\qquad p_2=9^n$$
şeklindedir. Ayrıca
$$3^n<6^n<9^n<10^n\qquad (n\ge 1)$$
olduğu için çubukların göreli sırası hiç değişmez. Böylece \(h_K\)'de hangi dalın kullanılacağı yalnızca çubuk indekslerinden belirlenir. İstenen toplam
$$S(N)=\sum_{n=1}^{N} E(n,10^n,3^n,6^n,9^n)\pmod{10^9}$$
olur. Sonuçtan yalnızca son dokuz basamak gerektiği için dinamik program boyunca tüm işlemler \(10^9\) modunda yürütülebilir.
\(n=2\) için kanonik yönelim \((0,2,1)\)'dir. Özyineleme
$$T_2^{(0,2,1)}=U_{0,1}+U_{1,0}+U_{0,2}+U_{2,1}+U_{1,2}$$
sonucunu verir. Yani ilk \(1\to 0\) yürüyüşünden sonra taşıyıcı şu yönlü geçişleri yapar:
$$0\to 1,\qquad 1\to 0,\qquad 0\to 2,\qquad 2\to 1,\qquad 1\to 2.$$
\(K=5\) ve konumlar \((1,3,5)\) için tekil maliyetler
$$h_5(3,1)=12,\qquad h_5(1,3)=4,\qquad h_5(1,5)=16,\qquad h_5(5,3)=4,\qquad h_5(3,5)=12$$
olur. Böylece
$$E(2,5,1,3,5)=12+4+12+16+4+12=60,$$
ki bu, uygulamanın kullandığı küçük kesin kontrol değeriyle aynıdır.
C++, Python ve Java uygulamaları önce 6 yönelimi oluşturur ve her biri için bir adet \(3\times 3\) geçiş sayısı matrisi saklar. \(n=1\) durumunda her yönelimde yalnızca bir kaynak-hedef hareketi vardır. Daha büyük her \(n\) için yeni matris, iki eski matris ile üç sabit köprü geçişi \(a\to f\), \(f\to t\) ve \(t\to a\) eklenerek elde edilir.
Aynı anda \(3^n\), \(6^n\), \(9^n\) ve \(10^n\) dizileri \(10^9\) modunda güncellenir. Her adımda kanonik yönelim \((0,2,1)\) maliyet çekirdeğiyle değerlendirilir ve sonuç çalışan toplama yine \(10^9\) modunda eklenir.
C++ uygulaması uzun toplamı hesaplamadan önce iki küçük kesin örnekle türetimi de doğrular:
$$E(2,5,1,3,5)=60,\qquad E(3,20,4,9,17)=2358.$$
Bu denetimler hem geçiş özyinelemesinin hem de geometrik maliyet formülünün doğru bağlandığını gösterir.
Her zaman yalnızca 6 yönelim vardır ve her yönelim 9 geçiş sayısı tutar. \(n\)'den \(n+1\)'e her geçiş, bu sabit durum üzerinde sabit sayıda aritmetik işlem ve ardından sabit boyutlu bir maliyet hesabı yapar. Bu nedenle \(N\)'ye kadar toplam süre \(O(N)\), çalışma belleği ise \(O(1)\)'dir.
Para cada \(n\), tres varillas están situadas en las posiciones \(3^n\), \(6^n\) y \(9^n\) sobre una pista circular de longitud \(10^n\). Hay que realizar el traslado canónico de Hanói desde la primera varilla hasta la tercera, usando la varilla central como auxiliar, y medir el coste total ponderado del recorrido del transportador.
El transportador empieza en la varilla central. Una simulación directa abriría una lista de movimientos de longitud exponencial, así que la solución no sigue estados individuales de discos. En su lugar, cuenta cuántas veces aparece cada transición dirigida entre varillas y combina esos conteos con una fórmula cerrada para el coste geométrico correspondiente.
El valor pedido es
$$\sum_{n=1}^{10000} E_n \pmod{10^9},$$
donde \(E_n\) representa el coste del caso con \(n\) discos.
La idea central es que la recursión de Hanói puede comprimirse en un estado fijo muy pequeño: la orientación del subproblema y los conteos de transiciones dirigidas entre las tres varillas.
Numeramos las varillas como \(0,1,2\) en orden creciente de posición. Una orientación \((f,t,a)\) significa: mover toda la torre desde la varilla origen \(f\) hasta la varilla destino \(t\), usando \(a\) como auxiliar. Como \((f,t,a)\) es una permutación de \((0,1,2)\), existen exactamente seis orientaciones.
Para cada orientación y cada número de discos \(n\), definimos una matriz \(3\times 3\)
$$T_n^{(f,t,a)}=\bigl(T_n^{(f,t,a)}(i,j)\bigr)_{0\le i,j\le 2},$$
donde \(T_n^{(f,t,a)}(i,j)\) es el número de transiciones dirigidas \(i\to j\) que ocurren una vez que el transportador ya ha llegado a la varilla origen de ese subproblema. De ese modo, la caminata inicial del problema completo queda separada.
Sea \(U_{u,v}\) la matriz \(3\times 3\) con un único \(1\) en la entrada \((u,v)\). Para un solo disco, si el transportador ya está en la varilla origen, solo hay un movimiento cargado:
$$T_1^{(f,t,a)}=U_{f,t}.$$
Para \(n\ge 2\), la descomposición clásica de Hanói es:
1. mover los \(n-1\) discos superiores de \(f\) a \(a\) usando \(t\),
2. volver de \(a\) a \(f\),
3. transportar el disco mayor de \(f\) a \(t\),
4. caminar de \(t\) a \(a\),
5. mover los \(n-1\) discos de \(a\) a \(t\) usando \(f\).
Por tanto,
$$T_n^{(f,t,a)}=T_{n-1}^{(f,a,t)}+\Delta^{(f,t,a)}+T_{n-1}^{(a,t,f)},$$
con
$$\Delta^{(f,t,a)}=U_{a,f}+U_{f,t}+U_{t,a}.$$
La recurrencia es exacta y solo actualiza seis matrices de tamaño fijo en cada nuevo valor de \(n\).
Fijemos ahora una circunferencia de tamaño \(K\) y dos posiciones \(1\le x,y\le K\). La regla de coste utilizada por la implementación depende de la dirección del desplazamiento.
Si \(x<y\), el movimiento avanza por el arco desde \(x\) hasta \(y\). Los pesos atravesados son
$$2x-1,\ 2x+1,\ \dots,\ 2y-3,$$
y su suma es
$$h_K(x,y)=\sum_{r=x}^{y-1}(2r-1)=(y-x)(x+y-2).$$
Si \(x>y\), el desplazamiento dirigido recorre el lado opuesto del círculo. Entonces los pesos son
$$2K-2y+1,\ 2K-2y-1,\ \dots,\ 2K-2x+3,$$
y se obtiene
$$h_K(x,y)=\sum_{r=y}^{x-1}(2K-2r-1)=(x-y)(2K-x-y).$$
En forma compacta,
$$h_K(x,y)=\begin{cases} (y-x)(x+y-2), & x<y,\\ (x-y)(2K-x-y), & x>y,\\ 0, & x=y. \end{cases}$$
Supongamos que las posiciones de las varillas son \(p_0<p_1<p_2\) sobre un círculo de tamaño \(K\), y que la torre debe ir de la varilla \(0\) a la varilla \(2\) usando la varilla \(1\). Como el transportador empieza en la varilla \(1\), la primera caminata obligatoria es \(1\to 0\), con coste \(h_K(p_1,p_0)\).
Después, cada transición dirigida contada por \(T_n^{(0,2,1)}(i,j)\) aporta \(h_K(p_i,p_j)\). Luego
$$E(n,K,p_0,p_1,p_2)=h_K(p_1,p_0)+\sum_{i=0}^{2}\sum_{j=0}^{2}T_n^{(0,2,1)}(i,j)\,h_K(p_i,p_j).$$
Esta expresión transforma la matriz abstracta de transiciones en el coste ponderado exacto de toda la tarea con \(n\) discos.
En esta familia de casos, los parámetros geométricos son
$$K_n=10^n,\qquad p_0=3^n,\qquad p_1=6^n,\qquad p_2=9^n.$$
Como
$$3^n<6^n<9^n<10^n\qquad (n\ge 1),$$
el orden relativo de las varillas nunca cambia. Por eso, la rama correcta de \(h_K\) queda fijada solo por los índices de las varillas. La suma pedida es
$$S(N)=\sum_{n=1}^{N} E(n,10^n,3^n,6^n,9^n)\pmod{10^9}.$$
Puesto que solo interesan los últimos nueve dígitos, todas las operaciones del programa dinámico pueden reducirse módulo \(10^9\) desde el principio.
Para \(n=2\), la orientación canónica es \((0,2,1)\). La recurrencia produce
$$T_2^{(0,2,1)}=U_{0,1}+U_{1,0}+U_{0,2}+U_{2,1}+U_{1,2}.$$
Así, después de la caminata inicial \(1\to 0\), las transiciones dirigidas son
$$0\to 1,\qquad 1\to 0,\qquad 0\to 2,\qquad 2\to 1,\qquad 1\to 2.$$
Con \(K=5\) y posiciones \((1,3,5)\), los costes individuales valen
$$h_5(3,1)=12,\qquad h_5(1,3)=4,\qquad h_5(1,5)=16,\qquad h_5(5,3)=4,\qquad h_5(3,5)=12.$$
Por consiguiente,
$$E(2,5,1,3,5)=12+4+12+16+4+12=60,$$
que coincide exactamente con el valor de comprobación pequeño usado por la implementación.
Las implementaciones en C++, Python y Java enumeran primero las seis orientaciones y guardan una matriz \(3\times 3\) de conteos para cada una. En \(n=1\), cada orientación contiene un único movimiento de origen a destino. Para cada \(n\) mayor, cada nueva matriz se construye a partir de dos matrices previas más las tres transiciones puente fijas \(a\to f\), \(f\to t\) y \(t\to a\).
Al mismo tiempo, se actualizan módulo \(10^9\) las cuatro sucesiones \(3^n\), \(6^n\), \(9^n\) y \(10^n\). Tras cada actualización, la implementación evalúa la orientación canónica \((0,2,1)\), aplica el núcleo de coste a las posiciones corrientes y añade el resultado a una suma acumulada módulo \(10^9\).
La implementación en C++ también valida la derivación sobre dos casos pequeños exactos antes de calcular la suma larga:
$$E(2,5,1,3,5)=60,\qquad E(3,20,4,9,17)=2358.$$
Esos puntos de control verifican tanto la recurrencia de transiciones como la fórmula geométrica del coste.
Siempre hay solo 6 orientaciones, y cada una almacena 9 conteos de transición. Cada paso de \(n\) a \(n+1\) realiza una cantidad constante de operaciones aritméticas sobre ese estado fijo y luego una evaluación de coste también de tamaño fijo. Por lo tanto, el tiempo total hasta \(N\) es \(O(N)\) y la memoria de trabajo es \(O(1)\).
对每个 \(n\)，三根柱子分别放在长度为 \(10^n\) 的圆环上的位置 \(3^n\)、\(6^n\) 和 \(9^n\)。题目要求执行标准的三柱汉诺塔搬运：把整座塔从第一根柱子搬到第三根柱子，中间柱子作为辅助柱，并计算搬运者在整个过程中产生的加权总路程代价。
搬运者一开始站在中间那根柱子上。如果直接展开汉诺塔的全部动作序列，那么每个 \(n\) 都会产生指数级长度的步骤，根本无法用于 \(n=10000\) 这样的范围。因此实现并不去显式模拟每一张盘子的状态，而是只统计“三根柱子之间每一种有向转移一共出现多少次”，再把这些次数乘上对应几何移动的闭式代价。
最终要求的是
$$\sum_{n=1}^{10000} E_n \pmod{10^9},$$
其中 \(E_n\) 表示第 \(n\) 个实例的总成本。
整个解法的核心是：汉诺塔递归虽然会展开出很长的动作序列，但真正需要维护的信息只有一个很小的固定状态，也就是“当前子问题的方向”以及“三根柱子之间各类有向转移出现的次数”。
按位置从小到大把三根柱子标为 \(0,1,2\)。一个方向三元组 \((f,t,a)\) 表示：把整座塔从源柱 \(f\) 搬到目标柱 \(t\)，柱 \(a\) 作为辅助柱。因为 \((f,t,a)\) 是 \((0,1,2)\) 的一个排列，所以一共只有 6 种可能的方向状态。
对每一种方向状态和每一个盘子数 \(n\)，定义一个 \(3\times 3\) 矩阵
$$T_n^{(f,t,a)}=\bigl(T_n^{(f,t,a)}(i,j)\bigr)_{0\le i,j\le 2},$$
其中 \(T_n^{(f,t,a)}(i,j)\) 表示：在搬运者已经走到该子问题的源柱之后，整个 \(n\) 盘子子问题中有多少次从柱 \(i\) 到柱 \(j\) 的有向移动。这样定义的好处是，整道题最开始那一次“先走到第一根柱子”的动作可以单独处理，不会和递归内部的结构混在一起。
记 \(U_{u,v}\) 为只有 \((u,v)\) 位置是 \(1\)、其余位置都是 \(0\) 的 \(3\times 3\) 基础矩阵。对 \(n=1\) 来说，如果搬运者已经站在源柱上，那么整个任务只剩下一次真正的搬运动作：
$$T_1^{(f,t,a)}=U_{f,t}.$$
当 \(n\ge 2\) 时，标准汉诺塔分解是完全确定的：
1. 先把上面的 \(n-1\) 个盘子从 \(f\) 搬到 \(a\)，以 \(t\) 为辅助；
2. 然后从 \(a\) 走回 \(f\)；
3. 再把最大的盘子从 \(f\) 搬到 \(t\)；
4. 接着从 \(t\) 走到 \(a\)；
5. 最后把那 \(n-1\) 个盘子从 \(a\) 搬到 \(t\)，以 \(f\) 为辅助。
因此，转移次数满足
$$T_n^{(f,t,a)}=T_{n-1}^{(f,a,t)}+\Delta^{(f,t,a)}+T_{n-1}^{(a,t,f)},$$
其中
$$\Delta^{(f,t,a)}=U_{a,f}+U_{f,t}+U_{t,a}.$$
这个公式非常重要，因为它说明每个新的 \(n\) 只需要由两个旧方向状态和 3 个固定“桥接动作”构成，完全不需要展开整条长度为 \(2^n-1\) 的盘子搬运序列。
接下来固定一个圆环长度 \(K\)，并考虑圆环上的两个位置 \(x,y\)，其中 \(1\le x,y\le K\)。程序使用的代价规则是“有方向的”：从较小位置走向较大位置，与从较大位置绕回较小位置，代价公式并不相同。
如果 \(x<y\)，那么移动沿着正向弧从 \(x\) 走到 \(y\)。途中跨过的区段权重是
$$2x-1,\ 2x+1,\ \dots,\ 2y-3,$$
所以代价就是一个等差数列求和：
$$h_K(x,y)=\sum_{r=x}^{y-1}(2r-1)=(y-x)(x+y-2).$$
如果 \(x>y\)，则这次有向移动不是直接“倒着走”，而是沿着圆环的另一侧绕回去。此时跨过的区段权重为
$$2K-2y+1,\ 2K-2y-1,\ \dots,\ 2K-2x+3,$$
于是得到
$$h_K(x,y)=\sum_{r=y}^{x-1}(2K-2r-1)=(x-y)(2K-x-y).$$
把两种情形合并起来，就得到实现中真正使用的分段函数
$$h_K(x,y)=\begin{cases} (y-x)(x+y-2), & x<y,\\ (x-y)(2K-x-y), & x>y,\\ 0, & x=y. \end{cases}$$
设三根柱子的实际位置为 \(p_0<p_1<p_2\)，圆环长度为 \(K\)，并考虑标准任务：把塔从柱 \(0\) 搬到柱 \(2\)，柱 \(1\) 为辅助柱。因为搬运者最开始站在柱 \(1\)，所以在任何盘子真正移动之前，先要走一次 \(1\to 0\)，这部分成本是 \(h_K(p_1,p_0)\)。
之后，矩阵 \(T_n^{(0,2,1)}(i,j)\) 中的每个条目告诉我们：方向 \(i\to j\) 总共发生了多少次，而每发生一次就产生 \(h_K(p_i,p_j)\) 的成本。因此
$$E(n,K,p_0,p_1,p_2)=h_K(p_1,p_0)+\sum_{i=0}^{2}\sum_{j=0}^{2}T_n^{(0,2,1)}(i,j)\,h_K(p_i,p_j).$$
这一步把“递归结构的组合计数”直接变成了“整个搬运过程的几何总代价”。
在 Problem 497 中，几何参数随着 \(n\) 变化，但变化方式非常规则：
$$K_n=10^n,\qquad p_0=3^n,\qquad p_1=6^n,\qquad p_2=9^n.$$
并且对所有 \(n\ge 1\) 都有
$$3^n<6^n<9^n<10^n.$$
这意味着三根柱子的相对顺序永远不会改变，所以在代价函数 \(h_K\) 里，究竟该走“\(x<y\)”那一支还是“\(x>y\)”那一支，始终只由柱子的编号关系决定，不会因为取模而发生混乱。于是目标和可以写成
$$S(N)=\sum_{n=1}^{N} E(n,10^n,3^n,6^n,9^n)\pmod{10^9}.$$
由于题目只要求最后 9 位，所以在动态规划的每一步里，位置幂次、转移计数和累计总和都可以直接按 \(10^9\) 取模处理。
考虑 \(n=2\) 的标准方向 \((0,2,1)\)。由上面的递推式可得
$$T_2^{(0,2,1)}=U_{0,1}+U_{1,0}+U_{0,2}+U_{2,1}+U_{1,2}.$$
也就是说，在初始的 \(1\to 0\) 走位之后，搬运者依次会产生这些有向转移：
$$0\to 1,\qquad 1\to 0,\qquad 0\to 2,\qquad 2\to 1,\qquad 1\to 2.$$
当 \(K=5\)、三根柱子位置为 \((1,3,5)\) 时，各项代价分别是
$$h_5(3,1)=12,\qquad h_5(1,3)=4,\qquad h_5(1,5)=16,\qquad h_5(5,3)=4,\qquad h_5(3,5)=12.$$
因此总成本为
$$E(2,5,1,3,5)=12+4+12+16+4+12=60,$$
这正好和实现中使用的小规模精确校验值一致。
C++、Python 和 Java 实现都会先枚举 6 种方向状态，并为每种状态维护一个 \(3\times 3\) 的转移计数矩阵。对于 \(n=1\)，每个方向状态都只包含一次“源柱到目标柱”的搬运。对更大的 \(n\)，新矩阵由两个旧矩阵加上 3 条固定桥接转移 \(a\to f\)、\(f\to t\)、\(t\to a\) 组成。
与此同时，实现还会同步更新四个幂序列 \(3^n\)、\(6^n\)、\(9^n\) 和 \(10^n\) 的模 \(10^9\) 值。每轮更新后，只需取标准方向 \((0,2,1)\) 的那一个矩阵，套用代价函数，就能得到当前 \(E_n\)，再把它累加到答案里。
C++ 实现还会先检查两个小规模精确例子：
$$E(2,5,1,3,5)=60,\qquad E(3,20,4,9,17)=2358.$$
这两个检查点同时验证了递推结构和代价公式都与推导一致。
状态规模始终固定不变：只有 6 个方向状态，每个状态只有 9 个转移计数。每次从 \(n\) 更新到 \(n+1\) 时，只做常数次矩阵加法、常数次模运算和一次固定大小的代价评估。因此累加到 \(N\) 的总时间复杂度是 \(O(N)\)，额外空间复杂度是 \(O(1)\)。
Для каждого \(n\) три стержня расположены в точках \(3^n\), \(6^n\) и \(9^n\) на круговой дорожке длины \(10^n\). Нужно выполнить канонический перенос башни Ханоя с первого стержня на третий, используя средний как вспомогательный, и посчитать полный взвешенный путь переносчика.
Переносчик начинает у среднего стержня. Прямое раскрытие последовательности ходов Ханоя было бы экспоненциальным по \(n\), поэтому решение не моделирует отдельные состояния дисков. Вместо этого оно считает, сколько раз возникает каждый направленный переход между стержнями, а затем умножает эти количества на замкнутую формулу стоимости соответствующего геометрического перемещения.
Требуется найти
$$\sum_{n=1}^{10000} E_n \pmod{10^9},$$
где \(E_n\) обозначает стоимость случая с \(n\) дисками.
Главная идея состоит в том, что вся рекурсия сводится к очень маленькому состоянию фиксированного размера: ориентации подзадачи и числу направленных переходов между тремя стержнями.
Пронумеруем стержни как \(0,1,2\) в порядке возрастания их координат. Ориентация \((f,t,a)\) означает: перенести всю башню с исходного стержня \(f\) на целевой стержень \(t\), используя \(a\) как вспомогательный. Так как \((f,t,a)\) является перестановкой \((0,1,2)\), всего существует ровно 6 ориентаций.
Для каждой ориентации и каждого числа дисков \(n\) введем матрицу \(3\times 3\)
$$T_n^{(f,t,a)}=\bigl(T_n^{(f,t,a)}(i,j)\bigr)_{0\le i,j\le 2},$$
где \(T_n^{(f,t,a)}(i,j)\) равно числу направленных переходов \(i\to j\), происходящих после того, как переносчик уже добрался до исходного стержня данной подзадачи. Благодаря этому самый первый путь во всей задаче выделяется в отдельное слагаемое.
Пусть \(U_{u,v}\) — матрица \(3\times 3\), у которой единственная единица стоит в позиции \((u,v)\). Для одного диска, если переносчик уже находится у исходного стержня, остается только одно загруженное перемещение:
$$T_1^{(f,t,a)}=U_{f,t}.$$
Для \(n\ge 2\) стандартное разложение Ханоя имеет вид:
1. перенести верхние \(n-1\) дисков из \(f\) в \(a\), используя \(t\),
2. вернуться из \(a\) в \(f\),
3. перенести самый большой диск из \(f\) в \(t\),
4. пройти из \(t\) в \(a\),
5. перенести \(n-1\) дисков из \(a\) в \(t\), используя \(f\).
Следовательно,
$$T_n^{(f,t,a)}=T_{n-1}^{(f,a,t)}+\Delta^{(f,t,a)}+T_{n-1}^{(a,t,f)},$$
где
$$\Delta^{(f,t,a)}=U_{a,f}+U_{f,t}+U_{t,a}.$$
Эта формула точна и требует обновлять лишь шесть матриц постоянного размера на каждом новом \(n\).
Зафиксируем длину окружности \(K\) и две позиции \(x\) и \(y\), где \(1\le x,y\le K\). Используемая в программе стоимость зависит от направления.
Если \(x<y\), движение идет вперед по дуге от \(x\) к \(y\). Весы пересекаемых участков равны
$$2x-1,\ 2x+1,\ \dots,\ 2y-3,$$
поэтому
$$h_K(x,y)=\sum_{r=x}^{y-1}(2r-1)=(y-x)(x+y-2).$$
Если \(x>y\), направленное движение идет по дальней стороне окружности. Тогда веса участков таковы:
$$2K-2y+1,\ 2K-2y-1,\ \dots,\ 2K-2x+3,$$
и получается
$$h_K(x,y)=\sum_{r=y}^{x-1}(2K-2r-1)=(x-y)(2K-x-y).$$
Итак, окончательно
$$h_K(x,y)=\begin{cases} (y-x)(x+y-2), & x<y,\\ (x-y)(2K-x-y), & x>y,\\ 0, & x=y. \end{cases}$$
Пусть \(p_0<p_1<p_2\) — координаты трех стержней на окружности длины \(K\), а башню надо перенести со стержня \(0\) на стержень \(2\), используя стержень \(1\). Так как переносчик стартует у стержня \(1\), первый неизбежный путь — это \(1\to 0\), его стоимость равна \(h_K(p_1,p_0)\).
После этого каждое вхождение \(T_n^{(0,2,1)}(i,j)\) означает, что переход \(i\to j\) происходит столько раз, и каждый раз он стоит \(h_K(p_i,p_j)\). Значит,
$$E(n,K,p_0,p_1,p_2)=h_K(p_1,p_0)+\sum_{i=0}^{2}\sum_{j=0}^{2}T_n^{(0,2,1)}(i,j)\,h_K(p_i,p_j).$$
Именно эта формула переводит абстрактный счет переходов в точную суммарную стоимость всей \(n\)-дисковой задачи.
В данной задаче параметры зависят от \(n\) так:
$$K_n=10^n,\qquad p_0=3^n,\qquad p_1=6^n,\qquad p_2=9^n.$$
Поскольку
$$3^n<6^n<9^n<10^n\qquad (n\ge 1),$$
относительный порядок стержней никогда не меняется. Поэтому правильная ветвь функции \(h_K\) определяется только индексами стержней и не зависит от модульных сокращений. Требуемая сумма равна
$$S(N)=\sum_{n=1}^{N} E(n,10^n,3^n,6^n,9^n)\pmod{10^9}.$$
Так как нужны лишь последние девять цифр, все промежуточные вычисления в динамике можно сразу вести по модулю \(10^9\).
Для \(n=2\) каноническая ориентация — \((0,2,1)\). Рекурсия дает
$$T_2^{(0,2,1)}=U_{0,1}+U_{1,0}+U_{0,2}+U_{2,1}+U_{1,2}.$$
Значит, после начального пути \(1\to 0\) переносчик выполняет переходы
$$0\to 1,\qquad 1\to 0,\qquad 0\to 2,\qquad 2\to 1,\qquad 1\to 2.$$
При \(K=5\) и координатах \((1,3,5)\) отдельные стоимости равны
$$h_5(3,1)=12,\qquad h_5(1,3)=4,\qquad h_5(1,5)=16,\qquad h_5(5,3)=4,\qquad h_5(3,5)=12.$$
Отсюда
$$E(2,5,1,3,5)=12+4+12+16+4+12=60,$$
что в точности совпадает с малой проверкой, используемой в реализации.
Реализации на C++, Python и Java сначала перечисляют 6 ориентаций и хранят по одной матрице переходов \(3\times 3\) для каждой из них. При \(n=1\) каждая ориентация содержит ровно одно перемещение от источника к цели. Для каждого следующего \(n\) новая матрица строится из двух предыдущих матриц и трех фиксированных мостовых переходов \(a\to f\), \(f\to t\) и \(t\to a\).
Параллельно программа обновляет по модулю \(10^9\) четыре последовательности \(3^n\), \(6^n\), \(9^n\) и \(10^n\). После каждого шага берется каноническая ориентация \((0,2,1)\), для нее вычисляется стоимость по текущим координатам, и результат добавляется к накопленной сумме.
Реализация на C++ также проверяет вывод на двух точных малых примерах:
$$E(2,5,1,3,5)=60,\qquad E(3,20,4,9,17)=2358.$$
Эти контрольные значения подтверждают корректность и рекурсии переходов, и геометрической формулы стоимости.
Число состояний всегда постоянно: 6 ориентаций, в каждой по 9 счетчиков переходов. Каждый переход от \(n\) к \(n+1\) выполняет лишь константное число арифметических операций над этим фиксированным состоянием и затем одну оценку стоимости фиксированного размера. Поэтому суммарное время до \(N\) равно \(O(N)\), а используемая память — \(O(1)\).
لكل \(n\)، توضع ثلاثة أعمدة عند المواضع \(3^n\) و\(6^n\) و\(9^n\) على مسار دائري طوله \(10^n\). المطلوب هو تنفيذ النقل القياسي لمسألة هانوي من العمود الأول إلى العمود الثالث مع استخدام العمود الأوسط كمساعد، ثم حساب الكلفة الكلية الموزونة لمسار الناقل أثناء هذه العملية.
يبدأ الناقل عند العمود الأوسط. ولو حاولنا محاكاة جميع حركات هانوي مباشرة فسنحصل على عدد أسي من الخطوات لكل \(n\)، ولذلك لا تتتبع الخوارزمية حالات الأقراص واحدًا واحدًا. بدلًا من ذلك، تعدّ كم مرة يظهر كل انتقال موجّه بين الأعمدة الثلاثة، ثم تضرب هذه الأعداد في صيغة مغلقة لكلفة الحركة الهندسية الموافقة.
القيمة المطلوبة هي
$$\sum_{n=1}^{10000} E_n \pmod{10^9},$$
حيث تمثل \(E_n\) كلفة الحالة ذات \(n\) قرصًا.
الفكرة الأساسية هي أن البنية التراجعية لمسألة هانوي يمكن ضغطها في حالة صغيرة جدًا وثابتة الحجم: اتجاه المسألة الفرعية، وعدد الانتقالات الموجّهة بين الأعمدة الثلاثة.
لنرقم الأعمدة \(0,1,2\) بحسب ترتيب مواضعها تصاعديًا. الثلاثي \((f,t,a)\) يعني: انقل البرج كله من عمود المصدر \(f\) إلى عمود الهدف \(t\) باستخدام العمود \(a\) كعمود مساعد. وبما أن \((f,t,a)\) هو ترتيب لعناصر \((0,1,2)\)، فهناك ست حالات اتجاه فقط.
لكل اتجاه ولكل عدد أقراص \(n\)، نعرّف مصفوفة \(3\times 3\)
$$T_n^{(f,t,a)}=\bigl(T_n^{(f,t,a)}(i,j)\bigr)_{0\le i,j\le 2},$$
حيث تمثل \(T_n^{(f,t,a)}(i,j)\) عدد مرات الانتقال الموجّه \(i\to j\) بعد أن يكون الناقل قد وصل أصلًا إلى عمود المصدر الخاص بهذه المسألة الفرعية. بهذه الطريقة تبقى المسافة الأولى في المسألة الكلية منفصلة في حد مستقل.
لتكن \(U_{u,v}\) هي المصفوفة \(3\times 3\) التي تحتوي على \(1\) واحدة فقط في الموضع \((u,v)\). عندما يكون لدينا قرص واحد فقط، وبعد أن يكون الناقل واقفًا عند عمود المصدر، فلا يبقى إلا حركة تحميل واحدة:
$$T_1^{(f,t,a)}=U_{f,t}.$$
أما عندما \(n\ge 2\)، فإن تفكيك هانوي القياسي يقول:
1. انقل أعلى \(n-1\) قرصًا من \(f\) إلى \(a\) باستخدام \(t\)،
2. ثم عد من \(a\) إلى \(f\)،
3. ثم انقل القرص الأكبر من \(f\) إلى \(t\)،
4. ثم امش من \(t\) إلى \(a\)،
5. وأخيرًا انقل \(n-1\) قرصًا من \(a\) إلى \(t\) باستخدام \(f\).
ومن ثم نحصل على
$$T_n^{(f,t,a)}=T_{n-1}^{(f,a,t)}+\Delta^{(f,t,a)}+T_{n-1}^{(a,t,f)},$$
حيث
$$\Delta^{(f,t,a)}=U_{a,f}+U_{f,t}+U_{t,a}.$$
هذه العلاقة دقيقة تمامًا، ولا تحتاج في كل قيمة جديدة لـ \(n\) إلا إلى تحديث ست مصفوفات صغيرة ذات حجم ثابت.
الآن نثبت طول الدائرة \(K\)، ونأخذ موضعين \(x\) و\(y\) بحيث \(1\le x,y\le K\). الكلفة المستخدمة في التنفيذ تعتمد على اتجاه الحركة.
إذا كان \(x<y\)، فإن الحركة تسير على القوس الأمامي من \(x\) إلى \(y\). الأوزان التي يتم قطعها هي
$$2x-1,\ 2x+1,\ \dots,\ 2y-3,$$
ولذلك تكون الكلفة
$$h_K(x,y)=\sum_{r=x}^{y-1}(2r-1)=(y-x)(x+y-2).$$
أما إذا كان \(x>y\)، فالحركة الموجّهة تدور عبر الجهة الأخرى من الدائرة. في هذه الحالة تكون الأوزان
$$2K-2y+1,\ 2K-2y-1,\ \dots,\ 2K-2x+3,$$
ومنها نحصل على
$$h_K(x,y)=\sum_{r=y}^{x-1}(2K-2r-1)=(x-y)(2K-x-y).$$
إذن الصيغة المجمعة هي
$$h_K(x,y)=\begin{cases} (y-x)(x+y-2), & x<y,\\ (x-y)(2K-x-y), & x>y,\\ 0, & x=y. \end{cases}$$
لنفرض أن مواضع الأعمدة هي \(p_0<p_1<p_2\) على دائرة طولها \(K\)، وأن البرج يجب أن ينتقل من العمود \(0\) إلى العمود \(2\) مع استخدام العمود \(1\) كمساعد. بما أن الناقل يبدأ عند العمود \(1\)، فإن أول انتقال لا بد منه هو \(1\to 0\)، وكلفته \(h_K(p_1,p_0)\).
بعد ذلك، كل عنصر \(T_n^{(0,2,1)}(i,j)\) يخبرنا كم مرة يحدث الانتقال \(i\to j\)، وكل مرة تكلف \(h_K(p_i,p_j)\). لذلك
$$E(n,K,p_0,p_1,p_2)=h_K(p_1,p_0)+\sum_{i=0}^{2}\sum_{j=0}^{2}T_n^{(0,2,1)}(i,j)\,h_K(p_i,p_j).$$
وهذه هي الصيغة التي تحول العدّ التجريدي للانتقالات إلى الكلفة الموزونة الدقيقة للمسألة كاملة.
في هذه المسألة تكون المعلمات الهندسية
$$K_n=10^n,\qquad p_0=3^n,\qquad p_1=6^n,\qquad p_2=9^n.$$
ولأن
$$3^n<6^n<9^n<10^n\qquad (n\ge 1),$$
فإن ترتيب الأعمدة لا يتغير أبدًا. وهذا يعني أن اختيار الفرع الصحيح من \(h_K\) تحدده فقط فهارس الأعمدة، ولا يضيع عند الحساب بترديد \(10^9\). ومن ثم يكون المطلوب هو
$$S(N)=\sum_{n=1}^{N} E(n,10^n,3^n,6^n,9^n)\pmod{10^9}.$$
وبما أن المسألة تطلب فقط آخر تسعة أرقام، فيمكن إجراء جميع عمليات الجمع والضرب أثناء البرمجة الديناميكية مباشرة بترديد \(10^9\).
عندما \(n=2\)، يكون الاتجاه القياسي هو \((0,2,1)\). تعطي العلاقة التراجعية
$$T_2^{(0,2,1)}=U_{0,1}+U_{1,0}+U_{0,2}+U_{2,1}+U_{1,2}.$$
أي أنه بعد المشي الابتدائي \(1\to 0\)، ينفذ الناقل الانتقالات الموجّهة
$$0\to 1,\qquad 1\to 0,\qquad 0\to 2,\qquad 2\to 1,\qquad 1\to 2.$$
وعند \(K=5\) والمواضع \((1,3,5)\)، تكون القيم الفردية
$$h_5(3,1)=12,\qquad h_5(1,3)=4,\qquad h_5(1,5)=16,\qquad h_5(5,3)=4,\qquad h_5(3,5)=12.$$
لذلك نحصل على
$$E(2,5,1,3,5)=12+4+12+16+4+12=60,$$
وهو تمامًا مقدار التحقق الصغير المستخدم في التنفيذ.
تبدأ تطبيقات C++ وPython وJava بحصر حالات الاتجاه الست، ثم تخزن لكل حالة مصفوفة \(3\times 3\) لعدد الانتقالات. عند \(n=1\) تحتوي كل حالة على حركة واحدة فقط من المصدر إلى الهدف. ولكل \(n\) أكبر، تُبنى المصفوفة الجديدة من مصفوفتين سابقتين مع إضافة الانتقالات الجسرية الثلاثة الثابتة \(a\to f\) و\(f\to t\) و\(t\to a\).
وفي الوقت نفسه، يتم تحديث المتتاليات \(3^n\) و\(6^n\) و\(9^n\) و\(10^n\) بترديد \(10^9\). وبعد كل تحديث، تُقيَّم حالة الاتجاه القياسية \((0,2,1)\) باستعمال دالة الكلفة الحالية، ثم تُضاف النتيجة إلى مجموع تراكمي بترديد \(10^9\).
كما أن تنفيذ C++ يتحقق أولًا من الاشتقاق على حالتين صغيرتين مضبوطتين:
$$E(2,5,1,3,5)=60,\qquad E(3,20,4,9,17)=2358.$$
وهذان الفحصان يؤكدان صحة كل من علاقة الانتقالات وصيغة الكلفة الهندسية.
عدد الحالات ثابت دائمًا: 6 اتجاهات فقط، وفي كل اتجاه 9 عدادات انتقال. كل انتقال من \(n\) إلى \(n+1\) يحتاج عددًا ثابتًا من العمليات الحسابية على هذه الحالة الصغيرة، ثم تقييم كلفة ثابت الحجم. لذلك فإن الزمن الكلي حتى \(N\) هو \(O(N)\)، والذاكرة العاملة هي \(O(1)\).