In the standard optimal Tower of Hanoi transfer with \(n\) disks, after each move we record the peg populations \((a,b,c)\). The position is losing in normal Nim exactly when
$$a\oplus b\oplus c=0.$$
The required quantity is the sum of all move numbers \(t\in\{1,\dots,2^n-1\}\) for which the Hanoi position is Nim-losing. The C++, Python, and Java implementations compute this value modulo \(10^9+7\) without simulating the full exponential move sequence.
The key reduction is to count how many losing times correspond to each admissible ordered population triple, and only at the very end convert that count into a sum of move indices.
The optimal Hanoi path has length \(2^n-1\). Reversing time sends move \(t\) to move \(2^n-1-t\), and this reversal only permutes peg roles, so the Nim condition is preserved. Therefore losing times come in complementary pairs whose indices add to \(2^n-1\).
If \(\Lambda(n)\) denotes the total number of losing times, then
$$S(n)=\frac{2^n-1}{2}\,\Lambda(n)\pmod{10^9+7}.$$
So the real task is to compute \(\Lambda(n)\), the number of Nim-losing moments along the Hanoi path.
Any Hanoi state satisfies
$$a+b+c=n.$$
For a losing Nim state we also need
$$a\oplus b\oplus c=0.$$
Bit by bit, xor zero means that at every binary position there are either zero 1s or exactly two 1s among \(a,b,c\). So the contribution of bit \(2^r\) to the sum \(a+b+c\) is either \(0\) or \(2^{r+1}\). This immediately shows that \(n\) must be even; if \(n\) is odd, the answer is \(0\).
Write \(n=2m\), and let the binary expansion of \(m\) be
$$m=\sum_{r\in R}2^r.$$
For each \(r\in R\), exactly one peg omits the bit \(2^r\), so the local contribution is one of
$$\left(0,2^r,2^r\right),\qquad \left(2^r,0,2^r\right),\qquad \left(2^r,2^r,0\right).$$
Adding these choices independently over all set bits of \(m\) generates every ordered triple \((a,b,c)\) with \(a+b+c=n\) and \(a\oplus b\oplus c=0\), and it generates each such triple exactly once. Hence the number of admissible losing triples is
$$3^{s_2(m)}=3^{s_2(n/2)},$$
where \(s_2(\cdot)\) is the number of 1s in the binary expansion.
The implementation evaluates an auxiliary coefficient extracted from
$$\Psi(X,Y,Z)=\frac{1}{1-X^2-Y^2-Z^2-2XYZ}.$$
Define
$$\mathcal{A}(\alpha,\beta,\gamma)=\left[X^\alpha Y^\beta Z^\gamma\right]\Psi(X,Y,Z).$$
Using the geometric-series expansion,
$$\Psi(X,Y,Z)=\sum_{i\ge 0}\left(X^2+Y^2+Z^2+2XYZ\right)^i.$$
So in the \(i\)-th layer we choose some copies of \(X^2\), some of \(Y^2\), some of \(Z^2\), and some of \(2XYZ\). That multinomial expansion is exactly the algebra encoded by the implementations.
Fix nonnegative \(\alpha,\beta,\gamma\) and set
$$m=\alpha+\beta+\gamma.$$
In one term of degree \(i\), suppose \(k\) factors contribute \(2XYZ\). Then
$$k=m-2i,$$
and the remaining exponents must come from squares, so
$$r_X=\frac{\alpha-k}{2},\qquad r_Y=\frac{\beta-k}{2},\qquad r_Z=\frac{\gamma-k}{2}.$$
These must be nonnegative integers. Equivalently, with
$$A=\frac{\beta+\gamma}{2},\qquad B=\frac{\alpha+\gamma}{2},\qquad C=\frac{\alpha+\beta}{2},$$
we have
$$r_X=i-A,\qquad r_Y=i-B,\qquad r_Z=i-C.$$
Therefore the \(i\)-th contribution is
$$Q_i(\alpha,\beta,\gamma)=\frac{i!\,2^{m-2i}}{(m-2i)!\,(i-A)!\,(i-B)!\,(i-C)!},$$
and the full auxiliary term is
$$\mathcal{A}(\alpha,\beta,\gamma)=\sum_{i=\ell}^{\lfloor m/2\rfloor} Q_i(\alpha,\beta,\gamma),$$
where
$$\ell=\max\left(\left\lceil\frac{m}{3}\right\rceil,A,B,C\right).$$
If the parity conditions fail, meaning \(\alpha,\beta,\gamma\) do not all have the same parity as \(m\), then \(\mathcal{A}(\alpha,\beta,\gamma)=0\).
The actual number of losing occurrences of a specific ordered Hanoi population triple is obtained by multiplying the generating function by a correction polynomial. Define
$$M(a,b,c)=\left[X^aY^bZ^c\right]\left(1+X+Z+XY+YZ-Y^2\right)\Psi(X,Y,Z).$$
Extracting coefficients gives the six-term identity
$$\begin{aligned} M(a,b,c)=&\ \mathcal{A}(a,b,c)+\mathcal{A}(a-1,b,c)+\mathcal{A}(a,b,c-1)\\ &+\mathcal{A}(a-1,b-1,c)+\mathcal{A}(a,b-1,c-1)-\mathcal{A}(a,b-2,c). \end{aligned}$$
This expression is intentionally not symmetric in \(a,b,c\). The standard Hanoi transfer treats the three pegs as source, auxiliary, and target in a fixed order, so the middle peg receives a different correction term.
Let \(\mathcal{T}_n\) be the set of ordered triples satisfying
$$a+b+c=n,\qquad a\oplus b\oplus c=0.$$
Then the total number of losing times is
$$\Lambda(n)=\sum_{(a,b,c)\in\mathcal{T}_n} M(a,b,c).$$
Combining this with Step 1 yields the implemented formula
$$\boxed{S(n)=\frac{2^n-1}{2}\sum_{\substack{a+b+c=n\\a\oplus b\oplus c=0}} M(a,b,c)\pmod{10^9+7}.}$$
Here \(n/2=2\) has one set bit, so there are exactly three admissible losing triples:
$$\left(0,2,2\right),\qquad \left(2,0,2\right),\qquad \left(2,2,0\right).$$
For \((2,2,0)\), only one summation level contributes to the auxiliary coefficient, giving
$$\mathcal{A}(2,2,0)=\frac{2!}{0!\,1!\,1!\,0!}=2.$$
Also \(\mathcal{A}(2,0,0)=1\), and the other shifted terms in the six-term identity vanish, so
$$M(2,2,0)=2-1=1.$$
Similarly,
$$M(0,2,2)=1,\qquad M(2,0,2)=2.$$
Therefore
$$\Lambda(4)=1+1+2=4.$$
The required sum of move indices is then
$$S(4)=\frac{2^4-1}{2}\cdot 4=\frac{15}{2}\cdot 4=30,$$
which matches the checkpoint used by the implementations.
The C++, Python, and Java implementations all follow the same mathematical pipeline. First they reject odd \(n\), because Step 2 proves that no losing triple can exist in that case. Next they precompute factorials, inverse factorials, powers of two, and modular inverses up to about \(n/2\), so each multinomial term can be evaluated quickly modulo \(10^9+7\).
Then the implementation enumerates every admissible triple by scanning the set bits of \(n/2\) and, for each such bit, choosing which peg does not receive that contribution. For one ordered triple, the auxiliary coefficient is not recomputed from scratch for every \(i\); instead the code starts at the smallest feasible \(i\) and advances with the exact ratio
$$\frac{Q_{i+1}}{Q_i}=\frac{(i+1)(m-2i)(m-2i-1)}{4(i+1-A)(i+1-B)(i+1-C)}.$$
That turns the inner sum into a linear sweep with \(O(1)\) modular work per step. After the auxiliary values are known, the implementation combines six shifted coefficients to obtain \(M(a,b,c)\), sums these values over all admissible triples to get \(\Lambda(n)\), and finally multiplies by \((2^n-1)/2\). The C++ version parallelizes the outer triple loop; the Python and Java versions keep the same mathematics in serial form.
If \(n\) is odd, the answer is returned immediately. For even \(n\), the number of admissible ordered triples is exactly
$$T=3^{s_2(n/2)}.$$
For each triple, the auxiliary summation runs over at most \(\lfloor n/2\rfloor+1\) indices \(i\), and every transition uses only \(O(1)\) modular operations because the tables are precomputed. Therefore the worst-case running time is
$$O\!\left(n\cdot 3^{s_2(n/2)}\right),$$
with memory usage
$$O(n).$$
Since \(s_2(n/2)\le \lfloor\log_2 n\rfloor\), this is dramatically smaller than brute-force Hanoi simulation, which would require \(\Theta(2^n)\) moves and states.
Beim optimalen Transfer des Turms von Hanoi mit \(n\) Scheiben betrachten wir nach jedem Zug die Belegungszahlen \((a,b,c)\) der drei Stäbe. Eine Stellung ist im normalen Nim genau dann verloren, wenn
$$a\oplus b\oplus c=0.$$
Gesucht ist die Summe aller Zugnummern \(t\in\{1,\dots,2^n-1\}\), für die die Hanoi-Stellung diese Nim-Bedingung erfüllt. Die C++-, Python- und Java-Implementierungen berechnen diesen Wert modulo \(10^9+7\), ohne die vollständige exponentielle Zugfolge auszusimulieren.
Die zentrale Reduktion besteht darin, zuerst zu zählen, wie oft jedes zulässige geordnete Belegungstripel als verlorene Stellung auftritt, und erst danach diese Anzahl in eine Summe von Zugindizes umzuwandeln.
Der optimale Hanoi-Pfad hat Länge \(2^n-1\). Zeitumkehr schickt Zug \(t\) auf Zug \(2^n-1-t\), und dabei werden nur die Rollen der Stäbe permutiert; die Nim-Bedingung bleibt also erhalten. Verlorene Zeitpunkte treten daher in komplementären Paaren auf, deren Indizes sich zu \(2^n-1\) addieren.
Bezeichne \(\Lambda(n)\) als Gesamtzahl der verlorenen Zeitpunkte. Dann gilt
$$S(n)=\frac{2^n-1}{2}\,\Lambda(n)\pmod{10^9+7}.$$
Die eigentliche Aufgabe ist also die Berechnung von \(\Lambda(n)\).
Jede Hanoi-Stellung erfüllt
$$a+b+c=n.$$
Für eine verlorene Nim-Stellung braucht man zusätzlich
$$a\oplus b\oplus c=0.$$
Bitweise bedeutet XOR gleich Null, dass an jeder Binärstelle entweder keine Eins oder genau zwei Einsen unter \(a,b,c\) vorkommen. Der Beitrag des Bits \(2^r\) zur Summe \(a+b+c\) ist also entweder \(0\) oder \(2^{r+1}\). Daraus folgt sofort: \(n\) muss gerade sein; für ungerades \(n\) ist die Antwort \(0\).
Schreibe \(n=2m\) und die Binärdarstellung von \(m\) als
$$m=\sum_{r\in R}2^r.$$
Für jedes \(r\in R\) lässt genau ein Stab das Bit \(2^r\) aus, daher ist der lokale Beitrag eine der drei Möglichkeiten
$$\left(0,2^r,2^r\right),\qquad \left(2^r,0,2^r\right),\qquad \left(2^r,2^r,0\right).$$
Addiert man diese unabhängigen Entscheidungen über alle gesetzten Bits von \(m\), erhält man genau alle geordneten Tripel \((a,b,c)\) mit \(a+b+c=n\) und \(a\oplus b\oplus c=0\), und zwar jeweils genau einmal. Die Anzahl zulässiger verlorener Tripel ist daher
$$3^{s_2(m)}=3^{s_2(n/2)},$$
wobei \(s_2(\cdot)\) die Anzahl der Einsen in der Binärdarstellung bezeichnet.
Die Implementierung wertet einen Hilfskoeffizienten aus, der aus
$$\Psi(X,Y,Z)=\frac{1}{1-X^2-Y^2-Z^2-2XYZ}$$
extrahiert wird. Definiere
$$\mathcal{A}(\alpha,\beta,\gamma)=\left[X^\alpha Y^\beta Z^\gamma\right]\Psi(X,Y,Z).$$
Mit der geometrischen Reihe erhält man
$$\Psi(X,Y,Z)=\sum_{i\ge 0}\left(X^2+Y^2+Z^2+2XYZ\right)^i.$$
In der \(i\)-ten Schicht wählt man also einige Kopien von \(X^2\), einige von \(Y^2\), einige von \(Z^2\) und einige von \(2XYZ\). Genau diese Multinomialstruktur steckt in den Formeln der Implementierung.
Fixiere nichtnegative \(\alpha,\beta,\gamma\) und setze
$$m=\alpha+\beta+\gamma.$$
Angenommen, in einem Term vom Grad \(i\) stammen \(k\) Faktoren von \(2XYZ\). Dann gilt
$$k=m-2i,$$
und die restlichen Exponenten müssen aus Quadraten kommen, also
$$r_X=\frac{\alpha-k}{2},\qquad r_Y=\frac{\beta-k}{2},\qquad r_Z=\frac{\gamma-k}{2}.$$
Diese Zahlen müssen nichtnegative ganze Zahlen sein. Äquivalent dazu, mit
$$A=\frac{\beta+\gamma}{2},\qquad B=\frac{\alpha+\gamma}{2},\qquad C=\frac{\alpha+\beta}{2},$$
gilt
$$r_X=i-A,\qquad r_Y=i-B,\qquad r_Z=i-C.$$
Der Beitrag der Stufe \(i\) lautet daher
$$Q_i(\alpha,\beta,\gamma)=\frac{i!\,2^{m-2i}}{(m-2i)!\,(i-A)!\,(i-B)!\,(i-C)!},$$
und der gesamte Hilfsterm ist
$$\mathcal{A}(\alpha,\beta,\gamma)=\sum_{i=\ell}^{\lfloor m/2\rfloor} Q_i(\alpha,\beta,\gamma),$$
wobei
$$\ell=\max\left(\left\lceil\frac{m}{3}\right\rceil,A,B,C\right).$$
Scheitern die Paritätsbedingungen, also haben \(\alpha,\beta,\gamma\) nicht alle dieselbe Parität wie \(m\), dann ist \(\mathcal{A}(\alpha,\beta,\gamma)=0\).
Die tatsächliche Anzahl verlorener Vorkommen eines bestimmten geordneten Hanoi-Belegungstripels entsteht durch Multiplikation mit einem Korrekturpolynom. Definiere
$$M(a,b,c)=\left[X^aY^bZ^c\right]\left(1+X+Z+XY+YZ-Y^2\right)\Psi(X,Y,Z).$$
Durch Koeffizientenvergleich ergibt sich die Sechs-Term-Identität
$$\begin{aligned} M(a,b,c)=&\ \mathcal{A}(a,b,c)+\mathcal{A}(a-1,b,c)+\mathcal{A}(a,b,c-1)\\ &+\mathcal{A}(a-1,b-1,c)+\mathcal{A}(a,b-1,c-1)-\mathcal{A}(a,b-2,c). \end{aligned}$$
Dieser Ausdruck ist bewusst nicht symmetrisch in \(a,b,c\). Beim Standardtransfer des Turms von Hanoi sind die drei Stäbe als Start-, Hilfs- und Zielstab geordnet; daher erhält der mittlere Stab einen anderen Korrekturterm.
Sei \(\mathcal{T}_n\) die Menge aller geordneten Tripel mit
$$a+b+c=n,\qquad a\oplus b\oplus c=0.$$
Dann ist die Gesamtzahl verlorener Zeitpunkte
$$\Lambda(n)=\sum_{(a,b,c)\in\mathcal{T}_n} M(a,b,c).$$
Zusammen mit Schritt 1 erhält man die implementierte Formel
$$\boxed{S(n)=\frac{2^n-1}{2}\sum_{\substack{a+b+c=n\\a\oplus b\oplus c=0}} M(a,b,c)\pmod{10^9+7}.}$$
Hier hat \(n/2=2\) genau ein gesetztes Bit, also gibt es genau drei zulässige verlorene Tripel:
$$\left(0,2,2\right),\qquad \left(2,0,2\right),\qquad \left(2,2,0\right).$$
Für \((2,2,0)\) trägt nur eine Summationsstufe zum Hilfskoeffizienten bei, also
$$\mathcal{A}(2,2,0)=\frac{2!}{0!\,1!\,1!\,0!}=2.$$
Außerdem gilt \(\mathcal{A}(2,0,0)=1\), und die übrigen verschobenen Terme verschwinden, daher
$$M(2,2,0)=2-1=1.$$
Ebenso erhält man
$$M(0,2,2)=1,\qquad M(2,0,2)=2.$$
Damit folgt
$$\Lambda(4)=1+1+2=4.$$
Die gesuchte Summe der Zugindizes ist also
$$S(4)=\frac{2^4-1}{2}\cdot 4=\frac{15}{2}\cdot 4=30,$$
genau der Kontrollwert aus den Implementierungen.
Die C++-, Python- und Java-Implementierungen folgen alle derselben mathematischen Pipeline. Zuerst wird ungerades \(n\) verworfen, weil Schritt 2 beweist, dass dann kein verlorenes Tripel existieren kann. Danach werden Fakultäten, inverse Fakultäten, Zweierpotenzen und modulare Inversen bis ungefähr \(n/2\) vorab berechnet, damit jeder Multinomialterm schnell modulo \(10^9+7\) ausgewertet werden kann.
Anschließend erzeugt die Implementierung jedes zulässige Tripel, indem sie die gesetzten Bits von \(n/2\) durchläuft und für jedes Bit wählt, welcher Stab diesen Beitrag nicht erhält. Für ein geordnetes Tripel wird der Hilfskoeffizient nicht für jedes \(i\) neu aus Fakultäten aufgebaut; stattdessen startet der Code beim kleinsten zulässigen \(i\) und verwendet das exakte Verhältnis
$$\frac{Q_{i+1}}{Q_i}=\frac{(i+1)(m-2i)(m-2i-1)}{4(i+1-A)(i+1-B)(i+1-C)}.$$
Damit wird die innere Summe zu einem linearen Sweep mit \(O(1)\) modularer Arbeit pro Schritt. Sind die Hilfswerte bekannt, kombiniert die Implementierung sechs verschobene Koeffizienten zu \(M(a,b,c)\), summiert diese Größen über alle zulässigen Tripel zu \(\Lambda(n)\) und multipliziert am Ende mit \((2^n-1)/2\). Die C++-Version parallelisiert die äußere Schleife über die Tripel; Python und Java verwenden dieselbe Mathematik seriell.
Für ungerades \(n\) kommt die Antwort sofort. Für gerades \(n\) ist die Anzahl zulässiger geordneter Tripel genau
$$T=3^{s_2(n/2)}.$$
Für jedes Tripel läuft die Hilfssumme über höchstens \(\lfloor n/2\rfloor+1\) Werte von \(i\), und jeder Übergang benötigt wegen der Vorberechnung nur \(O(1)\) modulare Operationen. Daher ist die Laufzeit im schlimmsten Fall
$$O\!\left(n\cdot 3^{s_2(n/2)}\right),$$
bei einem Speicherverbrauch von
$$O(n).$$
Da \(s_2(n/2)\le \lfloor\log_2 n\rfloor\) gilt, ist dieses Verfahren sehr viel kleiner als brute force, das \(\Theta(2^n)\) Züge und Zustände benötigen würde.
\(n\) diskli standart en kısa Hanoi çözümünde her hamleden sonra direklerdeki disk sayıları \((a,b,c)\) ile gösterilsin. Normal Nim'de bir durumun kayıp olması için gereken koşul
$$a\oplus b\oplus c=0$$
eşitliğidir. İstenen değer, Hanoi sürecinde bu koşulu sağlayan tüm hamle numaralarının toplamıdır. C++, Python ve Java uygulamaları bu toplamı \(10^9+7\) modunda, üstel büyüklükteki tüm hareket dizisini simüle etmeden hesaplar.
Ana fikir, önce hangi sıralı nüfus üçlüsünün kaç kez kayıp Nim durumu olarak göründüğünü saymak, sonra da bu sayıyı hamle indisleri toplamına dönüştürmektir.
En kısa Hanoi yolu \(2^n-1\) uzunluğundadır. Zamanı ters çevirdiğimizde \(t\) numaralı hamle \(2^n-1-t\) numaralı hamleye gider; bu işlem yalnızca direk rollerini permüte eder, dolayısıyla Nim kayıp koşulu korunur. Bu yüzden kayıp anlar, indeksleri toplamı \(2^n-1\) olan eşlenik çiftler halinde gelir.
Kayıp anların toplam sayısına \(\Lambda(n)\) dersek
$$S(n)=\frac{2^n-1}{2}\,\Lambda(n)\pmod{10^9+7}$$
olur. Yani asıl hedef \(\Lambda(n)\)'yi hesaplamaktır.
Her Hanoi durumunda
$$a+b+c=n$$
olur. Kayıp Nim durumu için ayrıca
$$a\oplus b\oplus c=0$$
gerekir. Bit düzeyinde xor'un sıfır olması, her ikilik basamakta ya hiç 1 olmaması ya da \(a,b,c\) arasında tam iki tane 1 bulunması demektir. Bu yüzden \(2^r\) bitinin \(a+b+c\)'ye katkısı ya \(0\) ya da \(2^{r+1}\) olur. Buradan hemen \(n\)'nin çift olması gerektiği çıkar; \(n\) tekse cevap doğrudan \(0\)'dır.
\(n=2m\) yazalım ve \(m\)'nin ikilik açılımını
$$m=\sum_{r\in R}2^r$$
şeklinde gösterelim. Her \(r\in R\) için tam bir direk \(2^r\) bitini almaz; dolayısıyla yerel katkı şu üç seçenekten biridir:
$$\left(0,2^r,2^r\right),\qquad \left(2^r,0,2^r\right),\qquad \left(2^r,2^r,0\right).$$
Bu bağımsız seçimleri \(m\)'nin tüm 1 bitleri üzerinde topladığımızda, \(a+b+c=n\) ve \(a\oplus b\oplus c=0\) koşullarını sağlayan tüm sıralı üçlüleri tam bir kez üretmiş oluruz. Demek ki geçerli kayıp üçlülerinin sayısı
$$3^{s_2(m)}=3^{s_2(n/2)}$$
olur; burada \(s_2(\cdot)\), ikilik yazımdaki 1 sayısını gösterir.
Uygulama, şu fonksiyondan bir yardımcı katsayı çıkarır:
$$\Psi(X,Y,Z)=\frac{1}{1-X^2-Y^2-Z^2-2XYZ}.$$
Şimdi
$$\mathcal{A}(\alpha,\beta,\gamma)=\left[X^\alpha Y^\beta Z^\gamma\right]\Psi(X,Y,Z)$$
tanımını yapalım. Geometrik seri açılımı
$$\Psi(X,Y,Z)=\sum_{i\ge 0}\left(X^2+Y^2+Z^2+2XYZ\right)^i$$
şeklindedir. Yani \(i\). kuvvette bazı terimler \(X^2\), bazıları \(Y^2\), bazıları \(Z^2\), bazıları da \(2XYZ\) olarak seçilir. Kodun kullandığı çokterimli yapı tam olarak budur.
Negatif olmayan \(\alpha,\beta,\gamma\) için
$$m=\alpha+\beta+\gamma$$
olsun. Derecesi \(i\) olan bir terimde \(k\) adet \(2XYZ\) faktörü seçildiğini varsayalım. O zaman
$$k=m-2i$$
olur ve geriye kalan üsler kare terimlerden gelmek zorundadır:
$$r_X=\frac{\alpha-k}{2},\qquad r_Y=\frac{\beta-k}{2},\qquad r_Z=\frac{\gamma-k}{2}.$$
Bunların negatif olmayan tamsayı olması gerekir. Eşdeğer biçimde
$$A=\frac{\beta+\gamma}{2},\qquad B=\frac{\alpha+\gamma}{2},\qquad C=\frac{\alpha+\beta}{2}$$
tanımlarıyla
$$r_X=i-A,\qquad r_Y=i-B,\qquad r_Z=i-C$$
yazabiliriz. Böylece \(i\). seviyenin katkısı
$$Q_i(\alpha,\beta,\gamma)=\frac{i!\,2^{m-2i}}{(m-2i)!\,(i-A)!\,(i-B)!\,(i-C)!}$$
olur ve toplam yardımcı terim
$$\mathcal{A}(\alpha,\beta,\gamma)=\sum_{i=\ell}^{\lfloor m/2\rfloor} Q_i(\alpha,\beta,\gamma)$$
şeklindedir. Alt sınır
$$\ell=\max\left(\left\lceil\frac{m}{3}\right\rceil,A,B,C\right)$$
olur. Parite koşulu bozulursa, yani \(\alpha,\beta,\gamma\) değerleri \(m\) ile aynı paritye sahip değilse, \(\mathcal{A}(\alpha,\beta,\gamma)=0\) olur.
Belirli bir sıralı Hanoi nüfus üçlüsünün kayıp olarak kaç kez göründüğü, bir düzeltme polinomu ile elde edilir. Şöyle tanımlayalım:
$$M(a,b,c)=\left[X^aY^bZ^c\right]\left(1+X+Z+XY+YZ-Y^2\right)\Psi(X,Y,Z).$$
Katsayıları açınca altı terimli kimlik gelir:
$$\begin{aligned} M(a,b,c)=&\ \mathcal{A}(a,b,c)+\mathcal{A}(a-1,b,c)+\mathcal{A}(a,b,c-1)\\ &+\mathcal{A}(a-1,b-1,c)+\mathcal{A}(a,b-1,c-1)-\mathcal{A}(a,b-2,c). \end{aligned}$$
Bu ifade özellikle simetrik değildir. Standart Hanoi aktarımında üç direğin rolleri başlangıç, yardımcı ve hedef olarak sıralıdır; bu nedenle ortadaki direğe gelen düzeltme farklıdır.
\(\mathcal{T}_n\),
$$a+b+c=n,\qquad a\oplus b\oplus c=0$$
koşullarını sağlayan sıralı üçlüler kümesi olsun. O zaman kayıp anların toplam sayısı
$$\Lambda(n)=\sum_{(a,b,c)\in\mathcal{T}_n} M(a,b,c)$$
olur. Adım 1 ile birleştirince uygulamanın kullandığı nihai formül
$$\boxed{S(n)=\frac{2^n-1}{2}\sum_{\substack{a+b+c=n\\a\oplus b\oplus c=0}} M(a,b,c)\pmod{10^9+7}.}$$
Burada \(n/2=2\) yalnızca bir tane 1 bit içerir; dolayısıyla tam üç geçerli kayıp üçlü vardır:
$$\left(0,2,2\right),\qquad \left(2,0,2\right),\qquad \left(2,2,0\right).$$
\((2,2,0)\) için yardımcı katsayıya yalnızca tek bir seviye katkı verir ve
$$\mathcal{A}(2,2,0)=\frac{2!}{0!\,1!\,1!\,0!}=2$$
elde edilir. Ayrıca \(\mathcal{A}(2,0,0)=1\) olur; diğer kaydırılmış terimler sıfırlandığı için
$$M(2,2,0)=2-1=1.$$
Benzer şekilde
$$M(0,2,2)=1,\qquad M(2,0,2)=2$$
bulunur. Böylece
$$\Lambda(4)=1+1+2=4$$
olur. İstenen hamle indisleri toplamı da
$$S(4)=\frac{2^4-1}{2}\cdot 4=\frac{15}{2}\cdot 4=30$$
çıkar; bu da uygulamaların doğrulama değerini verir.
C++, Python ve Java uygulamaları aynı matematiksel hattı izler. Önce \(n\) tekse doğrudan çıkılır; çünkü Adım 2, böyle bir durumda hiç kayıp üçlü olmayacağını gösterir. Sonra yaklaşık \(n/2\) seviyesine kadar faktöriyeller, ters faktöriyeller, ikinin kuvvetleri ve modüler tersler önceden hesaplanır; böylece her çokterimli ifade \(10^9+7\) modunda hızlıca bulunur.
Daha sonra uygulama, \(n/2\)'nin 1 bitlerini dolaşarak ve her bit için hangi direğin bu katkıyı almayacağını seçerek tüm geçerli üçlüleri üretir. Tek bir sıralı üçlü için yardımcı katsayı her \(i\) değeri için sıfırdan hesaplanmaz; bunun yerine en küçük mümkün \(i\) ile başlanır ve şu oran kullanılır:
$$\frac{Q_{i+1}}{Q_i}=\frac{(i+1)(m-2i)(m-2i-1)}{4(i+1-A)(i+1-B)(i+1-C)}.$$
Böylece iç toplam, adım başına \(O(1)\) modüler işlemle lineer bir taramaya dönüşür. Yardımcı katsayılar elde edildikten sonra altı kaydırılmış değer birleştirilerek \(M(a,b,c)\) bulunur, bunlar tüm geçerli üçlüler üzerinde toplanarak \(\Lambda(n)\) elde edilir ve son aşamada \((2^n-1)/2\) ile çarpılır. C++ sürümü dış üçlü döngüsünü paralelleştirir; Python ve Java aynı matematiği seri uygular.
\(n\) tekse cevap anında döner. \(n\) çiftse, geçerli sıralı üçlü sayısı tam olarak
$$T=3^{s_2(n/2)}$$
olur. Her üçlü için yardımcı toplam en fazla \(\lfloor n/2\rfloor+1\) adet \(i\) değeri içerir ve ön hesaplama sayesinde her geçiş yalnızca \(O(1)\) modüler işlem gerektirir. Bu nedenle en kötü durum çalışma süresi
$$O\!\left(n\cdot 3^{s_2(n/2)}\right)$$
ve bellek kullanımı
$$O(n)$$
şeklindedir. \(s_2(n/2)\le \lfloor\log_2 n\rfloor\) olduğundan bu yaklaşım, \(\Theta(2^n)\) hareket ve durum gerektiren kaba kuvvet simülasyonundan çok daha küçüktür.
En la transferencia óptima estándar de la Torre de Hanói con \(n\) discos, después de cada movimiento observamos las poblaciones de las tres varillas \((a,b,c)\). La posición es perdedora en Nim normal exactamente cuando
$$a\oplus b\oplus c=0.$$
La cantidad pedida es la suma de todos los números de movimiento \(t\in\{1,\dots,2^n-1\}\) para los que la posición de Hanói es perdedora en Nim. Las implementaciones en C++, Python y Java calculan ese valor módulo \(10^9+7\) sin simular toda la secuencia exponencial de movimientos.
La reducción clave consiste en contar primero cuántas veces aparece cada triple ordenado admisible como estado perdedor, y solo al final convertir ese conteo en una suma de índices de movimientos.
La trayectoria óptima de Hanói tiene longitud \(2^n-1\). Al invertir el tiempo, el movimiento \(t\) se empareja con el movimiento \(2^n-1-t\); esta inversión solo permuta los papeles de las varillas, así que la condición de Nim se conserva. Por tanto, los tiempos perdedores aparecen en pares complementarios cuyas posiciones suman \(2^n-1\).
Si \(\Lambda(n)\) denota el número total de tiempos perdedores, entonces
$$S(n)=\frac{2^n-1}{2}\,\Lambda(n)\pmod{10^9+7}.$$
Así, la tarea central es calcular \(\Lambda(n)\).
Cualquier estado de Hanói cumple
$$a+b+c=n.$$
Para que además sea un estado perdedor de Nim necesitamos
$$a\oplus b\oplus c=0.$$
Bit a bit, xor igual a cero significa que en cada posición binaria hay o bien cero unos o bien exactamente dos unos entre \(a,b,c\). En consecuencia, la contribución del bit \(2^r\) a la suma \(a+b+c\) es \(0\) o \(2^{r+1}\). Esto demuestra enseguida que \(n\) debe ser par; si \(n\) es impar, la respuesta es \(0\).
Escribamos \(n=2m\) y la expansión binaria de \(m\) como
$$m=\sum_{r\in R}2^r.$$
Para cada \(r\in R\), exactamente una de las tres coordenadas omite el bit \(2^r\), de modo que la contribución local es una de
$$\left(0,2^r,2^r\right),\qquad \left(2^r,0,2^r\right),\qquad \left(2^r,2^r,0\right).$$
Sumando estas decisiones independientes sobre todos los bits activos de \(m\) se generan exactamente todos los triples ordenados \((a,b,c)\) que satisfacen \(a+b+c=n\) y \(a\oplus b\oplus c=0\), cada uno una sola vez. Por tanto, el número de triples perdedores admisibles es
$$3^{s_2(m)}=3^{s_2(n/2)},$$
donde \(s_2(\cdot)\) cuenta los unos en la escritura binaria.
La implementación evalúa un coeficiente auxiliar extraído de
$$\Psi(X,Y,Z)=\frac{1}{1-X^2-Y^2-Z^2-2XYZ}.$$
Definimos
$$\mathcal{A}(\alpha,\beta,\gamma)=\left[X^\alpha Y^\beta Z^\gamma\right]\Psi(X,Y,Z).$$
Usando la serie geométrica,
$$\Psi(X,Y,Z)=\sum_{i\ge 0}\left(X^2+Y^2+Z^2+2XYZ\right)^i.$$
En la capa \(i\) elegimos cierto número de copias de \(X^2\), de \(Y^2\), de \(Z^2\) y de \(2XYZ\). Esa expansión multinomial es exactamente la estructura algebraica que usan las implementaciones.
Fijemos \(\alpha,\beta,\gamma\ge 0\) y pongamos
$$m=\alpha+\beta+\gamma.$$
En un término de grado \(i\), supongamos que \(k\) factores aportan \(2XYZ\). Entonces
$$k=m-2i,$$
y los exponentes restantes deben provenir de cuadrados, de modo que
$$r_X=\frac{\alpha-k}{2},\qquad r_Y=\frac{\beta-k}{2},\qquad r_Z=\frac{\gamma-k}{2}.$$
Estas cantidades deben ser enteros no negativos. De manera equivalente, si definimos
$$A=\frac{\beta+\gamma}{2},\qquad B=\frac{\alpha+\gamma}{2},\qquad C=\frac{\alpha+\beta}{2},$$
entonces
$$r_X=i-A,\qquad r_Y=i-B,\qquad r_Z=i-C.$$
Por tanto, la contribución del nivel \(i\) es
$$Q_i(\alpha,\beta,\gamma)=\frac{i!\,2^{m-2i}}{(m-2i)!\,(i-A)!\,(i-B)!\,(i-C)!},$$
y el término auxiliar completo es
$$\mathcal{A}(\alpha,\beta,\gamma)=\sum_{i=\ell}^{\lfloor m/2\rfloor} Q_i(\alpha,\beta,\gamma),$$
donde
$$\ell=\max\left(\left\lceil\frac{m}{3}\right\rceil,A,B,C\right).$$
Si fallan las condiciones de paridad, es decir, si \(\alpha,\beta,\gamma\) no tienen todas la misma paridad que \(m\), entonces \(\mathcal{A}(\alpha,\beta,\gamma)=0\).
El número real de apariciones perdedoras de un triple ordenado concreto se obtiene multiplicando por un polinomio corrector. Definimos
$$M(a,b,c)=\left[X^aY^bZ^c\right]\left(1+X+Z+XY+YZ-Y^2\right)\Psi(X,Y,Z).$$
Al extraer coeficientes se obtiene la identidad de seis términos
$$\begin{aligned} M(a,b,c)=&\ \mathcal{A}(a,b,c)+\mathcal{A}(a-1,b,c)+\mathcal{A}(a,b,c-1)\\ &+\mathcal{A}(a-1,b-1,c)+\mathcal{A}(a,b-1,c-1)-\mathcal{A}(a,b-2,c). \end{aligned}$$
Esta expresión no es simétrica en \(a,b,c\). La transferencia estándar de Hanói trata las tres varillas como origen, auxiliar y destino en un orden fijo, y por eso la varilla central recibe una corrección distinta.
Sea \(\mathcal{T}_n\) el conjunto de triples ordenados que cumplen
$$a+b+c=n,\qquad a\oplus b\oplus c=0.$$
Entonces el número total de tiempos perdedores es
$$\Lambda(n)=\sum_{(a,b,c)\in\mathcal{T}_n} M(a,b,c).$$
Combinando esto con el Paso 1 se obtiene la fórmula implementada:
$$\boxed{S(n)=\frac{2^n-1}{2}\sum_{\substack{a+b+c=n\\a\oplus b\oplus c=0}} M(a,b,c)\pmod{10^9+7}.}$$
Aquí \(n/2=2\) tiene un solo bit activo, así que existen exactamente tres triples perdedores admisibles:
$$\left(0,2,2\right),\qquad \left(2,0,2\right),\qquad \left(2,2,0\right).$$
Para \((2,2,0)\), solo un nivel de la suma contribuye al coeficiente auxiliar, por lo que
$$\mathcal{A}(2,2,0)=\frac{2!}{0!\,1!\,1!\,0!}=2.$$
Además, \(\mathcal{A}(2,0,0)=1\) y los demás términos desplazados se anulan, así que
$$M(2,2,0)=2-1=1.$$
De forma análoga,
$$M(0,2,2)=1,\qquad M(2,0,2)=2.$$
Por tanto,
$$\Lambda(4)=1+1+2=4.$$
La suma pedida de índices de movimientos es
$$S(4)=\frac{2^4-1}{2}\cdot 4=\frac{15}{2}\cdot 4=30,$$
que coincide con el valor de comprobación usado por las implementaciones.
Las implementaciones en C++, Python y Java siguen la misma secuencia matemática. Primero descartan \(n\) impar, porque el Paso 2 demuestra que entonces no puede existir ningún triple perdedor. Después precalculan factoriales, factoriales inversos, potencias de dos e inversos modulares hasta aproximadamente \(n/2\), de modo que cada término multinomial pueda evaluarse rápidamente módulo \(10^9+7\).
A continuación, la implementación enumera cada triple admisible recorriendo los bits activos de \(n/2\) y decidiendo, para cada uno de ellos, qué varilla no recibe esa contribución. Para un triple ordenado concreto, el coeficiente auxiliar no se vuelve a reconstruir desde cero para cada \(i\); el código empieza en el menor \(i\) factible y avanza usando la razón exacta
$$\frac{Q_{i+1}}{Q_i}=\frac{(i+1)(m-2i)(m-2i-1)}{4(i+1-A)(i+1-B)(i+1-C)}.$$
Eso convierte la suma interior en un barrido lineal con trabajo modular \(O(1)\) por paso. Una vez calculados los valores auxiliares, la implementación combina seis coeficientes desplazados para obtener \(M(a,b,c)\), suma esos valores sobre todos los triples admisibles para hallar \(\Lambda(n)\) y al final multiplica por \((2^n-1)/2\). La versión en C++ paraleliza el bucle exterior sobre triples; las versiones en Python y Java mantienen la misma matemática en forma secuencial.
Si \(n\) es impar, la respuesta se devuelve inmediatamente. Para \(n\) par, el número de triples ordenados admisibles es exactamente
$$T=3^{s_2(n/2)}.$$
Para cada triple, la suma auxiliar recorre como mucho \(\lfloor n/2\rfloor+1\) valores de \(i\), y cada transición requiere solo \(O(1)\) operaciones modulares gracias a las tablas precalculadas. Por ello, el tiempo de ejecución en el peor caso es
$$O\!\left(n\cdot 3^{s_2(n/2)}\right),$$
con uso de memoria
$$O(n).$$
Como \(s_2(n/2)\le \lfloor\log_2 n\rfloor\), este método es muchísimo más pequeño que la simulación directa de Hanói, que requeriría \(\Theta(2^n)\) movimientos y estados.
在标准最优的 \(n\) 盘汉诺塔转移过程中，每一步之后都可以记录三根柱子上的盘子数量 \((a,b,c)\)。把这三个数量视为 Nim 的三堆时，败态恰好满足
$$a\oplus b\oplus c=0.$$
题目要求的是所有满足这一条件的步号 \(t\in\{1,\dots,2^n-1\}\) 之和。C++、Python 和 Java 实现都在模 \(10^9+7\) 下计算这个和，而且并不显式模拟全部 \(2^n-1\) 次移动。
核心思想是先数清楚每一种可行的有序柱子人口三元组在汉诺塔路径上以 Nim 败态出现多少次，再把这个“出现次数”转换成题目真正需要的“步号之和”。
最优汉诺塔路径的总长度是 \(2^n-1\)。把整条路径反向，时刻 \(t\) 会与时刻 \(2^n-1-t\) 配对；这一反演只会交换三根柱子的角色，而 Nim 的败态条件对柱子置换是不变的。因此，所有败态时刻都会成对出现，并且每一对的步号和都等于 \(2^n-1\)。
设 \(\Lambda(n)\) 表示整条汉诺塔路径上 Nim 败态出现的总次数，则
$$S(n)=\frac{2^n-1}{2}\,\Lambda(n)\pmod{10^9+7}.$$
于是问题的重心就变成了求 \(\Lambda(n)\)。
任何汉诺塔状态都满足
$$a+b+c=n.$$
如果它还是 Nim 败态，就还必须满足
$$a\oplus b\oplus c=0.$$
逐位分析 xor 为 0 的条件：在每一个二进制位上，\((a,b,c)\) 中该位的 1 的个数只能是 0 或 2。于是某一位 \(2^r\) 对总和 \(a+b+c\) 的贡献只能是 \(0\) 或 \(2^{r+1}\)。这立刻说明 \(n\) 必须是偶数；如果 \(n\) 是奇数，就根本不存在这样的败态三元组，答案直接为 \(0\)。
把 \(n\) 写成 \(n=2m\)，再把 \(m\) 的二进制展开写成
$$m=\sum_{r\in R}2^r.$$
对于每个 \(r\in R\)，恰好有一根柱子不拿到位值 \(2^r\)，所以该位对三元组的局部贡献只能是下面三种之一：
$$\left(0,2^r,2^r\right),\qquad \left(2^r,0,2^r\right),\qquad \left(2^r,2^r,0\right).$$
把这些选择在 \(m\) 的所有 1 位上独立叠加，就会恰好得到全部满足 \(a+b+c=n\) 且 \(a\oplus b\oplus c=0\) 的有序三元组，而且每个三元组只会被生成一次。因此可行败态三元组的个数正好是
$$3^{s_2(m)}=3^{s_2(n/2)},$$
其中 \(s_2(\cdot)\) 表示二进制表示中的 1 的个数。
实现中真正计算的是一个来自生成函数的辅助系数：
$$\Psi(X,Y,Z)=\frac{1}{1-X^2-Y^2-Z^2-2XYZ}.$$
定义
$$\mathcal{A}(\alpha,\beta,\gamma)=\left[X^\alpha Y^\beta Z^\gamma\right]\Psi(X,Y,Z).$$
利用几何级数展开，有
$$\Psi(X,Y,Z)=\sum_{i\ge 0}\left(X^2+Y^2+Z^2+2XYZ\right)^i.$$
这表示在第 \(i\) 层展开里，我们要从 \(X^2\)、\(Y^2\)、\(Z^2\) 和 \(2XYZ\) 这四类项中做多项式选择。实现里出现的组合系数，正是这个多项式展开的系数。
固定非负整数 \(\alpha,\beta,\gamma\)，记
$$m=\alpha+\beta+\gamma.$$
在总次数为 \(i\) 的一层中，假设有 \(k\) 个因子选择了 \(2XYZ\)。那么必有
$$k=m-2i,$$
剩余指数只能由平方项提供，因此
$$r_X=\frac{\alpha-k}{2},\qquad r_Y=\frac{\beta-k}{2},\qquad r_Z=\frac{\gamma-k}{2}.$$
这些量必须是非负整数。把条件改写一下，令
$$A=\frac{\beta+\gamma}{2},\qquad B=\frac{\alpha+\gamma}{2},\qquad C=\frac{\alpha+\beta}{2},$$
则有
$$r_X=i-A,\qquad r_Y=i-B,\qquad r_Z=i-C.$$
因此第 \(i\) 层的贡献为
$$Q_i(\alpha,\beta,\gamma)=\frac{i!\,2^{m-2i}}{(m-2i)!\,(i-A)!\,(i-B)!\,(i-C)!},$$
而完整的辅助系数就是
$$\mathcal{A}(\alpha,\beta,\gamma)=\sum_{i=\ell}^{\lfloor m/2\rfloor} Q_i(\alpha,\beta,\gamma),$$
其中下界
$$\ell=\max\left(\left\lceil\frac{m}{3}\right\rceil,A,B,C\right).$$
如果 parity 条件不满足，也就是 \(\alpha,\beta,\gamma\) 不是都与 \(m\) 同奇偶，那么 \(\mathcal{A}(\alpha,\beta,\gamma)=0\)。
具体某个有序汉诺塔人口三元组作为败态出现多少次，不是直接等于 \(\mathcal{A}\)，而是要再乘上一个校正多项式。定义
$$M(a,b,c)=\left[X^aY^bZ^c\right]\left(1+X+Z+XY+YZ-Y^2\right)\Psi(X,Y,Z).$$
展开取系数后得到六项恒等式：
$$\begin{aligned} M(a,b,c)=&\ \mathcal{A}(a,b,c)+\mathcal{A}(a-1,b,c)+\mathcal{A}(a,b,c-1)\\ &+\mathcal{A}(a-1,b-1,c)+\mathcal{A}(a,b-1,c-1)-\mathcal{A}(a,b-2,c). \end{aligned}$$
这个式子刻意不是对称的。原因在于标准汉诺塔最优路径把三根柱子区分为起点、辅助柱和终点，三者是有顺序的，因此中间柱对应的修正项和另外两根柱子不同。
设 \(\mathcal{T}_n\) 为全部满足
$$a+b+c=n,\qquad a\oplus b\oplus c=0$$
的有序三元组集合，则败态出现总次数为
$$\Lambda(n)=\sum_{(a,b,c)\in\mathcal{T}_n} M(a,b,c).$$
再结合步骤 1，就得到实现中真正计算的公式
$$\boxed{S(n)=\frac{2^n-1}{2}\sum_{\substack{a+b+c=n\\a\oplus b\oplus c=0}} M(a,b,c)\pmod{10^9+7}.}$$
此时 \(n/2=2\)，二进制里只有一个 1 位，所以可行的败态三元组只有三个：
$$\left(0,2,2\right),\qquad \left(2,0,2\right),\qquad \left(2,2,0\right).$$
对 \((2,2,0)\)，辅助系数的求和中只有一个层次真正贡献，因此
$$\mathcal{A}(2,2,0)=\frac{2!}{0!\,1!\,1!\,0!}=2.$$
另一方面，\(\mathcal{A}(2,0,0)=1\)，其余平移项都为 \(0\)，所以
$$M(2,2,0)=2-1=1.$$
同理可得
$$M(0,2,2)=1,\qquad M(2,0,2)=2.$$
于是
$$\Lambda(4)=1+1+2=4.$$
最终要求的步号和就是
$$S(4)=\frac{2^4-1}{2}\cdot 4=\frac{15}{2}\cdot 4=30,$$
这与实现中的校验值完全一致。
C++、Python 和 Java 实现遵循完全相同的数学流程。首先，如果 \(n\) 为奇数，就立即返回 \(0\)，因为步骤 2 已经证明此时不存在任何败态三元组。然后实现会预处理大约到 \(n/2\) 为止的阶乘、逆阶乘、2 的幂以及模逆元，这样每个多项式系数都可以在模 \(10^9+7\) 下快速求出。
接着，实现逐个扫描 \(n/2\) 的所有 1 位，并对每一位选择“哪一根柱子不拿这一位的贡献”，从而枚举出全部可行三元组。对于某个固定的有序三元组，辅助系数不会对每个 \(i\) 都从头重算，而是从最小可行的 \(i\) 出发，用下面这个精确比值递推：
$$\frac{Q_{i+1}}{Q_i}=\frac{(i+1)(m-2i)(m-2i-1)}{4(i+1-A)(i+1-B)(i+1-C)}.$$
这样内层求和就变成了一个线性扫描，每次推进只需 \(O(1)\) 次模运算。得到辅助系数后，实现把六个平移后的值组合成 \(M(a,b,c)\)，再对所有可行三元组求和得到 \(\Lambda(n)\)，最后乘上 \((2^n-1)/2\)。其中 C++ 版本把外层三元组循环并行化，Python 和 Java 则采用同样的数学逻辑做串行累加。
若 \(n\) 为奇数，答案立刻返回。若 \(n\) 为偶数，则可行有序三元组的数量恰好是
$$T=3^{s_2(n/2)}.$$
对每个三元组，辅助求和最多遍历 \(\lfloor n/2\rfloor+1\) 个 \(i\) 值，而且由于预处理表已经准备好，每一步转移只需 \(O(1)\) 次模运算。因此最坏情况下总时间复杂度为
$$O\!\left(n\cdot 3^{s_2(n/2)}\right),$$
空间复杂度为
$$O(n).$$
由于 \(s_2(n/2)\le \lfloor\log_2 n\rfloor\)，这个规模比直接模拟汉诺塔路径所需的 \(\Theta(2^n)\) 次移动和状态小得多。
В стандартном оптимальном переносе \(n\) дисков в задаче о Ханойских башнях после каждого хода можно записывать количества дисков на трёх стержнях \((a,b,c)\). Если рассматривать эти количества как три кучи игры Nim, то проигрышное состояние задаётся условием
$$a\oplus b\oplus c=0.$$
Нужно найти сумму всех номеров ходов \(t\in\{1,\dots,2^n-1\}\), на которых состояние Ханоя является проигрышным в Nim. Реализации на C++, Python и Java вычисляют это значение по модулю \(10^9+7\), не моделируя всю экспоненциальную последовательность ходов.
Главная редукция состоит в том, чтобы сначала посчитать, сколько раз каждая допустимая упорядоченная тройка населённостей стержней появляется как проигрышная, и только потом превратить это количество в сумму индексов ходов.
Длина оптимального пути Ханоя равна \(2^n-1\). При обращении времени ход \(t\) переходит в ход \(2^n-1-t\); при этом лишь переставляются роли стержней, поэтому условие проигрыша в Nim сохраняется. Значит, проигрышные моменты образуют пары, суммы индексов в которых равны \(2^n-1\).
Если \(\Lambda(n)\) обозначает общее число проигрышных моментов, то
$$S(n)=\frac{2^n-1}{2}\,\Lambda(n)\pmod{10^9+7}.$$
Следовательно, основная задача сводится к вычислению \(\Lambda(n)\).
Любое состояние Ханоя удовлетворяет равенству
$$a+b+c=n.$$
Чтобы оно было проигрышным в Nim, дополнительно требуется
$$a\oplus b\oplus c=0.$$
Побитовый анализ говорит, что xor, равный нулю, означает следующее: в каждом двоичном разряде среди \(a,b,c\) число единиц равно либо 0, либо 2. Поэтому вклад бита \(2^r\) в сумму \(a+b+c\) может быть только \(0\) или \(2^{r+1}\). Отсюда сразу следует, что \(n\) должно быть чётным; если \(n\) нечётно, ответ равен \(0\).
Запишем \(n=2m\), а двоичное разложение числа \(m\) в виде
$$m=\sum_{r\in R}2^r.$$
Для каждого \(r\in R\) ровно один из трёх стержней не получает бит \(2^r\), поэтому локальный вклад имеет один из трёх видов:
$$\left(0,2^r,2^r\right),\qquad \left(2^r,0,2^r\right),\qquad \left(2^r,2^r,0\right).$$
Складывая эти независимые выборы по всем единичным битам числа \(m\), мы получаем все упорядоченные тройки \((a,b,c)\), удовлетворяющие \(a+b+c=n\) и \(a\oplus b\oplus c=0\), причём каждую ровно один раз. Следовательно, число допустимых проигрышных троек равно
$$3^{s_2(m)}=3^{s_2(n/2)},$$
где \(s_2(\cdot)\) обозначает число единиц в двоичной записи.
В реализации вычисляется вспомогательный коэффициент, извлекаемый из функции
$$\Psi(X,Y,Z)=\frac{1}{1-X^2-Y^2-Z^2-2XYZ}.$$
Определим
$$\mathcal{A}(\alpha,\beta,\gamma)=\left[X^\alpha Y^\beta Z^\gamma\right]\Psi(X,Y,Z).$$
Используя разложение геометрического ряда, получаем
$$\Psi(X,Y,Z)=\sum_{i\ge 0}\left(X^2+Y^2+Z^2+2XYZ\right)^i.$$
Это означает, что на уровне \(i\) мы выбираем некоторое количество множителей \(X^2\), \(Y^2\), \(Z^2\) и \(2XYZ\). Именно эта мультиномиальная структура и реализована в формулах программы.
Зафиксируем неотрицательные \(\alpha,\beta,\gamma\) и положим
$$m=\alpha+\beta+\gamma.$$
Пусть на уровне степени \(i\) ровно \(k\) множителей дают вклад \(2XYZ\). Тогда
$$k=m-2i,$$
а оставшиеся показатели должны получаться из квадратов, то есть
$$r_X=\frac{\alpha-k}{2},\qquad r_Y=\frac{\beta-k}{2},\qquad r_Z=\frac{\gamma-k}{2}.$$
Эти величины обязаны быть неотрицательными целыми. Эквивалентно, если ввести
$$A=\frac{\beta+\gamma}{2},\qquad B=\frac{\alpha+\gamma}{2},\qquad C=\frac{\alpha+\beta}{2},$$
то
$$r_X=i-A,\qquad r_Y=i-B,\qquad r_Z=i-C.$$
Поэтому вклад уровня \(i\) равен
$$Q_i(\alpha,\beta,\gamma)=\frac{i!\,2^{m-2i}}{(m-2i)!\,(i-A)!\,(i-B)!\,(i-C)!},$$
а весь вспомогательный коэффициент имеет вид
$$\mathcal{A}(\alpha,\beta,\gamma)=\sum_{i=\ell}^{\lfloor m/2\rfloor} Q_i(\alpha,\beta,\gamma),$$
где
$$\ell=\max\left(\left\lceil\frac{m}{3}\right\rceil,A,B,C\right).$$
Если нарушается условие чётности, то есть \(\alpha,\beta,\gamma\) не имеют ту же чётность, что и \(m\), тогда \(\mathcal{A}(\alpha,\beta,\gamma)=0\).
Настоящее число появлений конкретной упорядоченной тройки как проигрышной получается после умножения на корректирующий многочлен. Определим
$$M(a,b,c)=\left[X^aY^bZ^c\right]\left(1+X+Z+XY+YZ-Y^2\right)\Psi(X,Y,Z).$$
Извлечение коэффициентов даёт шестичленную формулу
$$\begin{aligned} M(a,b,c)=&\ \mathcal{A}(a,b,c)+\mathcal{A}(a-1,b,c)+\mathcal{A}(a,b,c-1)\\ &+\mathcal{A}(a-1,b-1,c)+\mathcal{A}(a,b-1,c-1)-\mathcal{A}(a,b-2,c). \end{aligned}$$
Этот вид намеренно не симметричен по \(a,b,c\). В стандартном переносе Ханоя три стержня играют роли источника, вспомогательного стержня и цели в фиксированном порядке, поэтому средний стержень получает другую поправку.
Пусть \(\mathcal{T}_n\) обозначает множество всех упорядоченных троек, удовлетворяющих
$$a+b+c=n,\qquad a\oplus b\oplus c=0.$$
Тогда общее число проигрышных моментов равно
$$\Lambda(n)=\sum_{(a,b,c)\in\mathcal{T}_n} M(a,b,c).$$
Совмещая это с шагом 1, получаем формулу, реализованную в программе:
$$\boxed{S(n)=\frac{2^n-1}{2}\sum_{\substack{a+b+c=n\\a\oplus b\oplus c=0}} M(a,b,c)\pmod{10^9+7}.}$$
Здесь \(n/2=2\) имеет ровно один установленный бит, поэтому допустимых проигрышных троек всего три:
$$\left(0,2,2\right),\qquad \left(2,0,2\right),\qquad \left(2,2,0\right).$$
Для \((2,2,0)\) во вспомогательной сумме ненулевой вклад даёт только один уровень, поэтому
$$\mathcal{A}(2,2,0)=\frac{2!}{0!\,1!\,1!\,0!}=2.$$
Кроме того, \(\mathcal{A}(2,0,0)=1\), а остальные сдвинутые члены равны нулю, следовательно
$$M(2,2,0)=2-1=1.$$
Аналогично получаем
$$M(0,2,2)=1,\qquad M(2,0,2)=2.$$
Значит,
$$\Lambda(4)=1+1+2=4.$$
Тогда искомая сумма номеров ходов равна
$$S(4)=\frac{2^4-1}{2}\cdot 4=\frac{15}{2}\cdot 4=30,$$
что совпадает с контрольным значением из реализаций.
Реализации на C++, Python и Java следуют одной и той же математической схеме. Сначала они сразу отбрасывают нечётные \(n\), потому что шаг 2 доказывает невозможность проигрышных троек в этом случае. Затем заранее вычисляются факториалы, обратные факториалы, степени двойки и модульные обратные примерно до \(n/2\), чтобы каждый мультиномиальный член быстро вычислялся по модулю \(10^9+7\).
После этого реализация перечисляет все допустимые тройки, проходя по установленным битам числа \(n/2\) и для каждого бита выбирая, какой стержень не получает соответствующий вклад. Для одной фиксированной упорядоченной тройки вспомогательный коэффициент не пересчитывается с нуля для каждого \(i\); вместо этого код стартует с минимально допустимого \(i\) и переходит дальше по точному отношению
$$\frac{Q_{i+1}}{Q_i}=\frac{(i+1)(m-2i)(m-2i-1)}{4(i+1-A)(i+1-B)(i+1-C)}.$$
Это превращает внутреннюю сумму в линейный проход с \(O(1)\) модульной работой на шаг. Когда вспомогательные коэффициенты получены, реализация комбинирует шесть сдвинутых значений в \(M(a,b,c)\), суммирует их по всем допустимым тройкам для получения \(\Lambda(n)\), а затем умножает результат на \((2^n-1)/2\). Версия на C++ распараллеливает внешний цикл по тройкам; версии на Python и Java используют ту же математику последовательно.
Если \(n\) нечётно, ответ возвращается сразу. Для чётного \(n\) число допустимых упорядоченных троек в точности равно
$$T=3^{s_2(n/2)}.$$
Для каждой тройки вспомогательная сумма пробегает не более \(\lfloor n/2\rfloor+1\) значений \(i\), причём каждый переход требует только \(O(1)\) модульных операций благодаря предварительно построенным таблицам. Поэтому асимптотика времени в худшем случае равна
$$O\!\left(n\cdot 3^{s_2(n/2)}\right),$$
а память составляет
$$O(n).$$
Поскольку \(s_2(n/2)\le \lfloor\log_2 n\rfloor\), этот подход несравнимо меньше прямого моделирования Ханоя, которое потребовало бы \(\Theta(2^n)\) ходов и состояний.
في النقل الأمثل القياسي لأبراج هانوي بعدد \(n\) من الأقراص، نسجل بعد كل حركة أعداد الأقراص على الأعمدة الثلاثة \((a,b,c)\). وإذا اعتبرنا هذه الأعداد أكوامًا في لعبة Nim، فإن الحالة تكون خاسرة بالضبط عندما
$$a\oplus b\oplus c=0.$$
المطلوب هو مجموع أرقام الحركات \(t\in\{1,\dots,2^n-1\}\) التي تتحقق فيها هذه الحالة الخاسرة. تطبّق النسخ المكتوبة بـ C++ وPython وJava هذا الحساب بترديد \(10^9+7\) من دون محاكاة السلسلة الأسية الكاملة للحركات.
الفكرة الأساسية هي أن نحسب أولًا عدد مرات ظهور كل ثلاثية مرتبة ممكنة من توزيعات الأقراص بوصفها حالة خاسرة، ثم نحوّل هذا العدد في النهاية إلى مجموع لفهارس الحركات.
طول المسار الأمثل في هانوي يساوي \(2^n-1\). وعند عكس الزمن تقابل الحركة \(t\) الحركة \(2^n-1-t\)، ولا يحدث سوى تبديل أدوار الأعمدة، لذلك يبقى شرط الخسارة في Nim محفوظًا. ومن ثم تظهر الأزمنة الخاسرة في أزواج متممة يكون مجموع فهارسها \(2^n-1\).
إذا رمزنا إلى العدد الكلي للأزمنة الخاسرة بـ \(\Lambda(n)\)، فإن
$$S(n)=\frac{2^n-1}{2}\,\Lambda(n)\pmod{10^9+7}.$$
إذن المهمة الجوهرية هي حساب \(\Lambda(n)\).
كل حالة في هانوي تحقق
$$a+b+c=n.$$
ولكي تكون الحالة خاسرة في Nim يجب أيضًا أن تحقق
$$a\oplus b\oplus c=0.$$
عند النظر بتًا بتًا، فإن تساوي xor بالصفر يعني أن كل خانة ثنائية تحتوي إما على صفر من الواحدات أو على واحدتين بالضبط بين \(a,b,c\). لذلك فإن مساهمة البت \(2^r\) في المجموع \(a+b+c\) لا يمكن أن تكون إلا \(0\) أو \(2^{r+1}\). وهذا يثبت فورًا أن \(n\) يجب أن يكون زوجيًا؛ فإذا كان \(n\) فرديًا فالإجابة تساوي \(0\).
لنكتب \(n=2m\)، ولتكن الكتابة الثنائية لـ \(m\) هي
$$m=\sum_{r\in R}2^r.$$
لكل \(r\in R\) يوجد عمود واحد فقط لا يحصل على البت \(2^r\)، ولهذا تكون المساهمة المحلية إحدى الصور الثلاث الآتية:
$$\left(0,2^r,2^r\right),\qquad \left(2^r,0,2^r\right),\qquad \left(2^r,2^r,0\right).$$
وعندما نجمع هذه الاختيارات المستقلة على جميع البتات المفعلة في \(m\)، نحصل على جميع الثلاثيات المرتبة \((a,b,c)\) التي تحقق \(a+b+c=n\) و\(a\oplus b\oplus c=0\)، وكل ثلاثية تظهر مرة واحدة فقط. ومن ثم يكون عدد الثلاثيات الخاسرة الممكنة
$$3^{s_2(m)}=3^{s_2(n/2)},$$
حيث \(s_2(\cdot)\) هو عدد الواحدات في التمثيل الثنائي.
التنفيذ يحسب معاملًا مساعدًا مأخوذًا من
$$\Psi(X,Y,Z)=\frac{1}{1-X^2-Y^2-Z^2-2XYZ}.$$
ونعرّف
$$\mathcal{A}(\alpha,\beta,\gamma)=\left[X^\alpha Y^\beta Z^\gamma\right]\Psi(X,Y,Z).$$
وباستخدام متسلسلة هندسية نحصل على
$$\Psi(X,Y,Z)=\sum_{i\ge 0}\left(X^2+Y^2+Z^2+2XYZ\right)^i.$$
هذا يعني أنه في الطبقة ذات الرتبة \(i\) نختار عددًا من الحدود من النوع \(X^2\) و\(Y^2\) و\(Z^2\) و\(2XYZ\). والبنية متعددة الحدود الناتجة هنا هي نفسها تمامًا التي تستعملها التطبيقات.
ثبّت أعدادًا غير سالبة \(\alpha,\beta,\gamma\)، ولتكن
$$m=\alpha+\beta+\gamma.$$
في حد من الدرجة \(i\)، افترض أن \(k\) من العوامل جاءت من \(2XYZ\). عندئذٍ
$$k=m-2i,$$
ويجب أن تأتي الأسس الباقية من الحدود المربعة، أي
$$r_X=\frac{\alpha-k}{2},\qquad r_Y=\frac{\beta-k}{2},\qquad r_Z=\frac{\gamma-k}{2}.$$
يجب أن تكون هذه القيم أعدادًا صحيحة غير سالبة. وبصورة مكافئة، إذا وضعنا
$$A=\frac{\beta+\gamma}{2},\qquad B=\frac{\alpha+\gamma}{2},\qquad C=\frac{\alpha+\beta}{2},$$
فإن
$$r_X=i-A,\qquad r_Y=i-B,\qquad r_Z=i-C.$$
ولذلك تكون مساهمة المستوى \(i\)
$$Q_i(\alpha,\beta,\gamma)=\frac{i!\,2^{m-2i}}{(m-2i)!\,(i-A)!\,(i-B)!\,(i-C)!},$$
ويصبح الحد المساعد الكامل
$$\mathcal{A}(\alpha,\beta,\gamma)=\sum_{i=\ell}^{\lfloor m/2\rfloor} Q_i(\alpha,\beta,\gamma),$$
حيث
$$\ell=\max\left(\left\lceil\frac{m}{3}\right\rceil,A,B,C\right).$$
إذا فشلت شروط التماثل في الفردية والزوجية، أي إذا لم تكن \(\alpha,\beta,\gamma\) جميعًا على نفس زوجية \(m\)، فعندئذٍ \(\mathcal{A}(\alpha,\beta,\gamma)=0\).
عدد مرات ظهور ثلاثية مرتبة معينة بوصفها حالة خاسرة لا يساوي \(\mathcal{A}\) مباشرة، بل ينتج بعد ضرب الدالة المولدة في كثير حدود تصحيحي. نعرّف
$$M(a,b,c)=\left[X^aY^bZ^c\right]\left(1+X+Z+XY+YZ-Y^2\right)\Psi(X,Y,Z).$$
وبأخذ المعاملات نحصل على الهوية ذات الحدود الستة:
$$\begin{aligned} M(a,b,c)=&\ \mathcal{A}(a,b,c)+\mathcal{A}(a-1,b,c)+\mathcal{A}(a,b,c-1)\\ &+\mathcal{A}(a-1,b-1,c)+\mathcal{A}(a,b-1,c-1)-\mathcal{A}(a,b-2,c). \end{aligned}$$
هذه الصيغة غير متناظرة عمدًا في \(a,b,c\). فالمسار القياسي في هانوي يميز بين عمود البداية والعمود الوسيط وعمود النهاية، ولذلك يظهر للعمود الأوسط حد تصحيحي مختلف.
لتكن \(\mathcal{T}_n\) مجموعة جميع الثلاثيات المرتبة التي تحقق
$$a+b+c=n,\qquad a\oplus b\oplus c=0.$$
فعندئذٍ يكون العدد الكلي للأزمنة الخاسرة
$$\Lambda(n)=\sum_{(a,b,c)\in\mathcal{T}_n} M(a,b,c).$$
وبالجمع مع الخطوة 1 نحصل على الصيغة التي تنفذها البرامج:
$$\boxed{S(n)=\frac{2^n-1}{2}\sum_{\substack{a+b+c=n\\a\oplus b\oplus c=0}} M(a,b,c)\pmod{10^9+7}.}$$
هنا \(n/2=2\) يحوي بتًا مفعّلًا واحدًا فقط، ولذلك توجد ثلاث ثلاثيات خاسرة ممكنة لا غير:
$$\left(0,2,2\right),\qquad \left(2,0,2\right),\qquad \left(2,2,0\right).$$
بالنسبة إلى \((2,2,0)\)، لا يساهم في المجموع المساعد إلا مستوى واحد، وبالتالي
$$\mathcal{A}(2,2,0)=\frac{2!}{0!\,1!\,1!\,0!}=2.$$
ولدينا أيضًا \(\mathcal{A}(2,0,0)=1\)، بينما تختفي بقية الحدود المزاحة، لذا
$$M(2,2,0)=2-1=1.$$
وبالمثل نحصل على
$$M(0,2,2)=1,\qquad M(2,0,2)=2.$$
ومن ثم
$$\Lambda(4)=1+1+2=4.$$
فيكون مجموع فهارس الحركات المطلوب
$$S(4)=\frac{2^4-1}{2}\cdot 4=\frac{15}{2}\cdot 4=30,$$
وهو تمامًا مقدار التحقق المستخدم في التطبيقات.
تتبع تطبيقات C++ وPython وJava المسار الرياضي نفسه. أولًا تُرفض قيم \(n\) الفردية مباشرة لأن الخطوة 2 تثبت استحالة وجود أي ثلاثية خاسرة عندئذٍ. ثم تُحسب مسبقًا قيم المضروبات ومعكوساتها ومقادير \(2^k\) والمعكوسات المعيارية حتى حدود تقارب \(n/2\)، حتى يمكن تقييم كل حد متعدد الحدود بسرعة بترديد \(10^9+7\).
بعد ذلك تعدّد الشيفرة جميع الثلاثيات الممكنة عبر المرور على البتات المفعّلة في \(n/2\) واختيار العمود الذي لا يتلقى مساهمة كل بت. وبالنسبة إلى ثلاثية مرتبة ثابتة، لا يُعاد بناء المعامل المساعد من الصفر لكل قيمة من \(i\)، بل يبدأ التنفيذ من أصغر \(i\) ممكن ويستخدم النسبة الدقيقة
$$\frac{Q_{i+1}}{Q_i}=\frac{(i+1)(m-2i)(m-2i-1)}{4(i+1-A)(i+1-B)(i+1-C)}.$$
وهذا يحوّل المجموع الداخلي إلى مسح خطي بكلفة معيارية مقدارها \(O(1)\) في كل خطوة. وبعد معرفة القيم المساعدة، تجمع الشيفرة ستة معاملات مزاحة لتكوين \(M(a,b,c)\)، ثم تجمع هذه القيم على جميع الثلاثيات الممكنة للحصول على \(\Lambda(n)\)، وأخيرًا تضرب في \((2^n-1)/2\). وتقوم نسخة C++ بموازاة الحلقة الخارجية على الثلاثيات، بينما تحافظ نسختا Python وJava على الحساب نفسه بصورة تسلسلية.
إذا كان \(n\) فرديًا فالإجابة تعاد مباشرة. وإذا كان \(n\) زوجيًا فإن عدد الثلاثيات المرتبة الممكنة يساوي تمامًا
$$T=3^{s_2(n/2)}.$$
ولكل ثلاثية، يجري المجموع المساعد على عدد لا يتجاوز \(\lfloor n/2\rfloor+1\) من قيم \(i\)، وكل انتقال يحتاج فقط إلى \(O(1)\) من العمليات المعيارية بسبب الجداول المحسوبة مسبقًا. لذلك يكون تعقيد الزمن في أسوأ الأحوال
$$O\!\left(n\cdot 3^{s_2(n/2)}\right),$$
واستهلاك الذاكرة
$$O(n).$$
وبما أن \(s_2(n/2)\le \lfloor\log_2 n\rfloor\)، فإن هذه الطريقة أصغر بكثير من المحاكاة المباشرة لهانوي، التي تتطلب \(\Theta(2^n)\) من الحركات والحالات.