For each \(n\), let \(f(n)\) be the number of routes in which a frog starts on stone \(1\), ends on stone \(n\), visits every stone \(1,2,\dots,n\) exactly once, and every jump has length at most \(3\).
Equivalently, \(f(n)\) counts Hamiltonian paths from \(1\) to \(n\) in the graph
$$G_n=(\{1,\dots,n\},E_n),\qquad \{i,j\}\in E_n \iff 1\le |i-j|\le 3.$$
The quantity required by the problem is
$$S(L)=\sum_{n=1}^{L} f(n)^3 \pmod{10^9}.$$
Since the main input has \(L=10^{14}\), it is useless to compute the values one by one. The solution instead converts the route count into a finite-state transfer process and then sums cubes by binary lifting in the third tensor power.
The crucial observation is local: when the stones are processed from left to right, a future stone can only connect to the previous three stones. That means the entire history collapses to a small frontier state.
A legal frog route is a permutation
$$a_1,a_2,\dots,a_n$$
of \(\{1,\dots,n\}\) such that
$$a_1=1,\qquad a_n=n,\qquad |a_{t+1}-a_t|\le 3 \text{ for every } t.$$
Viewed as an undirected graph, consecutive jumps form a path that uses every vertex exactly once. So we are counting Hamiltonian paths in \(G_n\) whose endpoints are \(1\) and \(n\).
Because edges only join vertices whose indices differ by at most \(3\), once we have passed far enough to the right, an old vertex can no longer receive any new edge. This is what makes a transfer-matrix approach possible.
Suppose we have already processed stones \(1,\dots,t\). Only the stones
$$\max(1,t-2),\max(1,t-1),t$$
can still connect to a future stone, so only those active stones need to be remembered.
For each active stone we record two pieces of information:
$$\text{its current degree } \in \{0,1,2\},\qquad \text{its connected-component label.}$$
Degree \(2\) is the maximum possible degree in a path. Component labels tell us whether two active stones are already linked through the partial route built so far.
Different label names do not matter; only the partition matters. Therefore component labels are canonically renumbered in first-occurrence order. After this normalization, the set of reachable states is finite.
When stone \(t+1\) is introduced, it may connect to zero, one, or two currently active stones.
The local restrictions are exactly the restrictions for extending a path:
$$\deg(v)\le 2 \text{ for every active stone } v,$$
and if the new stone connects to two active stones, those two stones must lie in different components; otherwise the new edges would close a cycle before the route is complete.
Once \(t+1\ge 4\), the oldest active stone leaves the frontier forever, because later stones are too far away to reach it. At that moment its degree must already be final:
$$\deg(1)=1 \text{ when stone } 1 \text{ leaves},$$
$$\deg(v)=2 \text{ for every later stone } v \text{ when it leaves}.$$
The first condition fixes stone \(1\) as the starting endpoint. The second condition forces every interior stone to be an interior vertex of the Hamiltonian path.
There is one more connectivity condition. If removing the oldest active stone would make its entire connected component disappear from the frontier, then that component is now sealed off from every future stone and can never merge with the rest of the route. Such a transition is impossible and must be discarded.
The first few lengths are exceptional because the frontier has not yet stabilized. Direct inspection gives
$$f(1)=f(2)=f(3)=1.$$
After the first four stones have been processed, the frontier always has size \(3\). Let the reachable canonical frontier states in this stable regime be
$$q_1,q_2,\dots,q_d.$$
Let \(v_n\in (\mathbb Z/10^9\mathbb Z)^d\) be the column vector whose \(i\)-th entry counts partial constructions of size \(n\) currently in state \(q_i\). Then for every \(n\ge 4\),
$$v_{n+1}=A v_n,$$
where \(A_{ij}\) is the number of legal local extensions from state \(q_j\) to state \(q_i\).
Now define a selector vector \(c\) by
$$c_i=\begin{cases}1,&\text{if } q_i \text{ represents one connected path with endpoint } n,\\ 0,&\text{otherwise.}\end{cases}$$
Then
$$f(n)=c^{\mathsf T} v_n \qquad (n\ge 4).$$
For any state vector \(x\),
$$\bigl(c^{\mathsf T}x\bigr)^3=\langle c^{\otimes 3},x^{\otimes 3}\rangle,$$
where \(c^{\otimes 3}=c\otimes c\otimes c\) and \(\langle \cdot,\cdot\rangle\) is the natural dot product on the third tensor power.
Therefore block sums of cubes can be encoded by third-order tensors. For \(r\ge 0\), define
$$\Phi_r(x)=\sum_{m=0}^{2^r-1} \bigl(c^{\mathsf T}A^m x\bigr)^3.$$
There exists a tensor \(T_r\) such that
$$\Phi_r(x)=\langle T_r,x^{\otimes 3}\rangle.$$
The base case is immediate:
$$T_0=c^{\otimes 3}.$$
Let
$$A_r=A^{2^r}.$$
A block of length \(2^{r+1}\) splits into two consecutive blocks of length \(2^r\), so
$$\Phi_{r+1}(x)=\Phi_r(x)+\Phi_r(A_r x).$$
Hence the tensors satisfy
$$T_{r+1}=T_r+\mathcal T_{A_r}(T_r),$$
where \(\mathcal T_M\) means: apply the matrix \(M\) in each of the three tensor slots. By definition,
$$\langle \mathcal T_M(T),x^{\otimes 3}\rangle=\langle T,(Mx)^{\otimes 3}\rangle.$$
This is the tensor analogue of the usual doubling identity for prefix sums.
For \(n=4\), every pair of stones is at distance at most \(3\), so \(G_4\) is the complete graph \(K_4\).
To count routes from \(1\) to \(4\), we only need to place stones \(2\) and \(3\) in the middle while preserving a Hamiltonian path. The two valid routes are
$$1,2,3,4 \qquad \text{and} \qquad 1,3,2,4,$$
so
$$f(4)=2.$$
The implementations also verify the checkpoints
$$f(6)=14,\qquad f(10)=254,$$
$$S(10)=18230635,$$
and
$$S(1000)\equiv 225031475 \pmod{10^9}.$$
These values are strong consistency checks for both the transfer matrix and the tensor-doubling sum.
The C++, Python, and Java implementations all follow the same structure. First they expand the first few stones explicitly, because the frontier size is still growing and the left endpoint has special degree requirements. After this warm-up they enumerate every reachable canonical frontier state and build the stationary transition matrix.
Next they assemble the state vector for length \(4\) and the selector that recognizes a completed route. They then precompute matrix powers \(A^{2^r}\) together with the block tensors \(T_r\) from the doubling formula above.
Finally, they read the binary expansion of \(L-3\). Whenever bit \(r\) is set, they add the contribution of the whole block represented by \(T_r\) for the current state vector and then advance that vector by \(A^{2^r}\). The three trivial initial terms \(f(1)^3,f(2)^3,f(3)^3\) are added separately. All arithmetic is reduced modulo \(10^9\).
Let \(d\) be the number of reachable canonical frontier states. Once the local rule is fixed, \(d\) is a small constant independent of \(L\), so the main cost is logarithmic in \(L\).
Building matrix powers costs \(O(d^3\log L)\). Each tensor transform applies the matrix in three slots, which costs \(O(d^4)\) per level, so all tensor block precomputations cost \(O(d^4\log L)\). Evaluating the selected block tensors during the binary walk costs \(O(d^3\log L)\).
The memory usage is \(O(d^3\log L)\) for the stored third-order tensors and \(O(d^2\log L)\) for the matrix powers.
Für jedes \(n\) bezeichne \(f(n)\) die Anzahl der Routen, bei denen ein Frosch auf Stein \(1\) startet, auf Stein \(n\) endet, jeden Stein \(1,2,\dots,n\) genau einmal besucht und dabei nur Sprünge der Länge höchstens \(3\) ausführt.
Äquivalent dazu zählt \(f(n)\) die Hamilton-Pfade von \(1\) nach \(n\) im Graphen
$$G_n=(\{1,\dots,n\},E_n),\qquad \{i,j\}\in E_n \iff 1\le |i-j|\le 3.$$
Gesucht ist
$$S(L)=\sum_{n=1}^{L} f(n)^3 \pmod{10^9}.$$
Da im eigentlichen Problem \(L=10^{14}\) ist, kann man die Werte nicht einzeln erzeugen. Die Lösung formt das Zählproblem deshalb in einen endlichen Transferprozess um und summiert die Kuben anschließend per Binärzerlegung im dritten Tensorraum.
Der entscheidende Punkt ist lokal: Verarbeitet man die Steine von links nach rechts, dann kann ein neuer Stein nur mit den letzten drei älteren Steinen verbunden werden. Dadurch lässt sich die gesamte Vorgeschichte in einem kleinen Frontzustand speichern.
Eine zulässige Route ist eine Permutation
$$a_1,a_2,\dots,a_n$$
von \(\{1,\dots,n\}\) mit
$$a_1=1,\qquad a_n=n,\qquad |a_{t+1}-a_t|\le 3 \text{ für alle } t.$$
Die aufeinanderfolgenden Sprünge bilden also einen Pfad, der jeden Knoten genau einmal benutzt. Genau deshalb zählt \(f(n)\) Hamilton-Pfade in \(G_n\) mit Endpunkten \(1\) und \(n\).
Weil Kanten nur zwischen Indizes mit Abstand höchstens \(3\) existieren, ist ein hinreichend alter Stein später nicht mehr erreichbar. Das ermöglicht die Zustandskompression.
Angenommen, die Steine \(1,\dots,t\) sind bereits verarbeitet. Dann können nur noch die Steine
$$\max(1,t-2),\max(1,t-1),t$$
mit einem zukünftigen Stein verbunden werden. Nur diese aktiven Steine müssen also im Zustand gespeichert werden.
Für jeden aktiven Stein merkt man sich
$$\text{seinen aktuellen Grad } \in \{0,1,2\},\qquad \text{sein Zusammenhangskomponenten-Label.}$$
Grad \(2\) ist das Maximum in einem Pfad. Die Komponentenlabels sagen aus, welche aktiven Steine über die bereits konstruierten Sprünge schon zusammenhängen.
Die konkreten Labelnamen sind unwichtig; entscheidend ist nur die Partition. Deshalb werden die Labels kanonisch in der Reihenfolge ihres ersten Auftretens neu nummeriert. Danach gibt es nur endlich viele erreichbare Zustände.
Wird Stein \(t+1\) eingeführt, darf er mit null, einem oder zwei aktiven Steinen verbunden werden.
Die lokalen Regeln sind genau die Regeln eines Pfades:
$$\deg(v)\le 2 \text{ für jeden aktiven Stein } v,$$
und wenn der neue Stein mit zwei aktiven Steinen verbunden wird, müssen diese in verschiedenen Komponenten liegen; andernfalls würde man vorzeitig einen Zyklus schließen.
Sobald \(t+1\ge 4\) gilt, verlässt der älteste aktive Stein die Front dauerhaft, weil spätere Steine zu weit entfernt sind. Dann muss sein Grad bereits endgültig sein:
$$\deg(1)=1 \text{ beim Entfernen von Stein } 1,$$
$$\deg(v)=2 \text{ für jeden später entfernten Stein } v.$$
Die erste Bedingung macht Stein \(1\) zum Start-Endpunkt. Die zweite erzwingt, dass jeder innere Stein im Hamilton-Pfad ein innerer Knoten ist.
Zusätzlich darf durch das Entfernen des ältesten aktiven Steins nicht dessen gesamte Komponente aus der Front verschwinden. Sonst wäre diese Komponente vom restlichen späteren Verlauf abgeschnitten und könnte nie mehr zu einem einzigen Gesamtpfad zusammenwachsen.
Die kleinen Längen sind Sonderfälle, weil die Front noch nicht stabil ist. Direkt erhält man
$$f(1)=f(2)=f(3)=1.$$
Nach Verarbeitung der ersten vier Steine hat die Front immer Größe \(3\). Seien
$$q_1,q_2,\dots,q_d$$
die erreichbaren kanonischen Frontzustände im stationären Bereich.
Sei \(v_n\in (\mathbb Z/10^9\mathbb Z)^d\) der Spaltenvektor, dessen \(i\)-ter Eintrag die Anzahl partieller Konstruktionen der Länge \(n\) im Zustand \(q_i\) ist. Dann gilt für jedes \(n\ge 4\)
$$v_{n+1}=A v_n,$$
wobei \(A_{ij}\) die Anzahl zulässiger lokaler Erweiterungen von \(q_j\) nach \(q_i\) ist.
Außerdem definieren wir einen Selektor \(c\) durch
$$c_i=\begin{cases}1,&\text{falls } q_i \text{ genau einen zusammenhängenden Pfad mit Endpunkt } n \text{ darstellt},\\ 0,&\text{sonst.}\end{cases}$$
Dann ist
$$f(n)=c^{\mathsf T} v_n \qquad (n\ge 4).$$
Für jeden Zustandsvektor \(x\) gilt
$$\bigl(c^{\mathsf T}x\bigr)^3=\langle c^{\otimes 3},x^{\otimes 3}\rangle,$$
wobei \(c^{\otimes 3}=c\otimes c\otimes c\) ist.
Damit lassen sich Blocksummen von Kuben durch Tensoren dritter Ordnung kodieren. Für \(r\ge 0\) definieren wir
$$\Phi_r(x)=\sum_{m=0}^{2^r-1} \bigl(c^{\mathsf T}A^m x\bigr)^3.$$
Dann existiert ein Tensor \(T_r\) mit
$$\Phi_r(x)=\langle T_r,x^{\otimes 3}\rangle.$$
Im Basisfall ist
$$T_0=c^{\otimes 3}.$$
Setze
$$A_r=A^{2^r}.$$
Ein Block der Länge \(2^{r+1}\) zerfällt in zwei aufeinanderfolgende Blöcke der Länge \(2^r\). Daher
$$\Phi_{r+1}(x)=\Phi_r(x)+\Phi_r(A_r x).$$
Folglich erfüllen die Tensoren die Rekursion
$$T_{r+1}=T_r+\mathcal T_{A_r}(T_r),$$
wobei \(\mathcal T_M\) bedeutet: Die Matrix \(M\) wird in allen drei Tensor-Slots angewandt. Formal gilt
$$\langle \mathcal T_M(T),x^{\otimes 3}\rangle=\langle T,(Mx)^{\otimes 3}\rangle.$$
Das ist genau das Tensor-Gegenstück zur üblichen Verdopplung von Präfixsummen.
Für \(n=4\) liegen alle Steinpaare in Abstand höchstens \(3\), also ist \(G_4\) der vollständige Graph \(K_4\).
Für eine Route von \(1\) nach \(4\) müssen nur die Steine \(2\) und \(3\) in die Mitte gesetzt werden. Die beiden gültigen Routen sind
$$1,2,3,4 \qquad \text{und} \qquad 1,3,2,4,$$
also
$$f(4)=2.$$
Die Implementierungen prüfen außerdem die Kontrollwerte
$$f(6)=14,\qquad f(10)=254,$$
$$S(10)=18230635,$$
und
$$S(1000)\equiv 225031475 \pmod{10^9}.$$
Diese Werte bestätigen sowohl die Transfermatrix als auch die Tensor-Verdopplung.
Die Implementierungen in C++, Python und Java folgen derselben mathematischen Struktur. Zuerst erweitern sie die ersten wenigen Steine explizit, weil die Front noch wächst und der linke Endpunkt eine Sonderrolle spielt. Danach werden alle erreichbaren kanonischen Frontzustände enumeriert und daraus die stationäre Transfermatrix aufgebaut.
Anschließend erzeugen sie den Zustandsvektor für Länge \(4\) und den Selektor für vollständig gültige Routen. Dann werden die Matrixpotenzen \(A^{2^r}\) sowie die zugehörigen Blocktensoren \(T_r\) gemäß der Verdopplungsformel vorab berechnet.
Zum Schluss wird die Binärdarstellung von \(L-3\) abgearbeitet. Für jedes gesetzte Bit \(r\) wird der gesamte Blockbeitrag aus \(T_r\) zum aktuellen Zustandsvektor addiert, und danach wird dieser Vektor mit \(A^{2^r}\) fortgeschoben. Die drei Anfangsterme \(f(1)^3,f(2)^3,f(3)^3\) kommen separat hinzu. Alle Rechnungen erfolgen modulo \(10^9\).
Sei \(d\) die Anzahl erreichbarer kanonischer Frontzustände. Ist die lokale Regel einmal fixiert, dann ist \(d\) eine kleine Konstante, unabhängig von \(L\). Der wesentliche Aufwand wächst also nur logarithmisch mit \(L\).
Die Matrixpotenzen kosten \(O(d^3\log L)\). Jede Tensortransformation wendet die Matrix in drei Slots an und benötigt \(O(d^4)\) pro Ebene, also insgesamt \(O(d^4\log L)\) für alle Blocktensoren. Die Auswertung der tatsächlich benutzten Blöcke in der Binärzerlegung kostet \(O(d^3\log L)\).
Der Speicherbedarf beträgt \(O(d^3\log L)\) für die gespeicherten Tensoren dritter Ordnung und \(O(d^2\log L)\) für die Matrixpotenzen.
Her \(n\) için \(f(n)\), kurbağanın \(1\). taştan başlayıp \(n\). taşta bittiği, \(1,2,\dots,n\) taşlarının her birini tam bir kez ziyaret ettiği ve her sıçramasının uzunluğu en fazla \(3\) olduğu rotaların sayısı olsun.
Eşdeğer olarak \(f(n)\),
$$G_n=(\{1,\dots,n\},E_n),\qquad \{i,j\}\in E_n \iff 1\le |i-j|\le 3$$
grafında \(1\)'den \(n\)'e giden Hamilton yol sayısıdır.
İstenen büyüklük
$$S(L)=\sum_{n=1}^{L} f(n)^3 \pmod{10^9}$$
olduğundan ve ana örnekte \(L=10^{14}\) olduğundan, değerleri tek tek üretmek pratik değildir. Çözüm bu yüzden sayımı sonlu durumlu bir geçiş modeline indirger ve küp toplamını üçüncü tensör kuvvetinde ikili katlama ile hesaplar.
Ana gözlem yereldir: Taşları soldan sağa işlersek yeni gelen bir taş yalnızca kendisinden önceki üç taşa bağlanabilir. Bu da tüm geçmişin küçük bir sınır durumu ile temsil edilmesini sağlar.
Geçerli bir rota,
$$a_1,a_2,\dots,a_n$$
şeklinde \(\{1,\dots,n\}\)'nin bir permütasyonudur ve
$$a_1=1,\qquad a_n=n,\qquad |a_{t+1}-a_t|\le 3 \text{ her } t \text{ için}$$
koşullarını sağlar.
Ardışık sıçramalar, her düğümü tam bir kez kullanan bir yol oluşturur. Dolayısıyla \(f(n)\), \(G_n\) grafında uçları \(1\) ve \(n\) olan Hamilton yollarını sayar.
Kenarlar yalnızca indeks farkı en fazla \(3\) olan taşlar arasında bulunduğu için, yeterince eski bir taş daha sonra hiçbir yeni kenar alamaz. Durum sıkıştırmasının temeli budur.
\(1,\dots,t\) taşlarının işlendiğini varsayalım. Gelecekteki bir taşla bağlanma ihtimali sadece
$$\max(1,t-2),\max(1,t-1),t$$
taşlarında vardır. Bu yüzden yalnızca bu aktif taşlar hafızada tutulur.
Her aktif taş için iki bilgi saklanır:
$$\text{mevcut derece } \in \{0,1,2\},\qquad \text{ait olduğu bağlı bileşen etiketi.}$$
Bir yolda derece en fazla \(2\) olabilir. Bileşen etiketleri ise aktif taşların kısmi rota içinde zaten birbirine bağlı olup olmadığını gösterir.
Etiket adlarının kendisi önemli değildir; önemli olan bölümlenmenin kendisidir. Bu nedenle etiketler ilk görülme sırasına göre kanonik biçimde yeniden numaralandırılır. Böylece erişilebilir durum sayısı sonlu kalır.
\(t+1\). taş eklendiğinde bu taş sıfır, bir veya iki aktif taşa bağlanabilir.
Yerel kurallar doğrudan yol kurallarıdır:
$$\deg(v)\le 2 \text{ her aktif taş } v \text{ için},$$
ve yeni taş iki aktif taşa bağlanıyorsa bu iki taş farklı bileşenlerde olmalıdır; aksi halde rota tamamlanmadan bir çevrim oluşur.
\(t+1\ge 4\) olduğunda en yaşlı aktif taş sınırdan sonsuza kadar çıkar, çünkü daha sonraki taşlar ona artık yetişemez. O anda derecesi kesinleşmiş olmalıdır:
$$\deg(1)=1 \text{, taş } 1 \text{ sınırdan çıkarken},$$
$$\deg(v)=2 \text{, daha sonra çıkan her taş } v \text{ için}.$$
İlk koşul taş \(1\)'i başlangıç ucu yapar. İkinci koşul ise iç taşların Hamilton yolunda iç düğüm olmasını zorunlu kılar.
Bir ek bağlantı koşulu daha vardır. En yaşlı aktif taş çıkarıldığında onun bağlı bileşeni sınırdan tamamen kayboluyorsa, bu bileşen artık gelecekte geri kalan kısımla birleşemez. Böyle bir geçiş geçersizdir.
İlk küçük uzunluklar özeldir, çünkü sınır henüz sabit boyuta ulaşmamıştır. Doğrudan
$$f(1)=f(2)=f(3)=1$$
elde edilir.
İlk dört taş işlendiğinde sınır boyutu artık her zaman \(3\) olur. Kararlı rejimdeki erişilebilir kanonik sınır durumları
$$q_1,q_2,\dots,q_d$$
olsun.
\(v_n\in (\mathbb Z/10^9\mathbb Z)^d\), uzunluğu \(n\) olan kısmi yapıların bu durumlara göre sayım vektörü olsun. O zaman her \(n\ge 4\) için
$$v_{n+1}=A v_n$$
geçerlidir; burada \(A_{ij}\), \(q_j\) durumundan \(q_i\)'ye giden geçerli yerel genişletme sayısıdır.
Ayrıca bir seçim vektörü tanımlanır:
$$c_i=\begin{cases}1,&\text{eğer } q_i \text{ tek bir bağlı yol ve } n \text{ ucunu temsil ediyorsa},\\ 0,&\text{aksi halde.}\end{cases}$$
Böylece
$$f(n)=c^{\mathsf T}v_n \qquad (n\ge 4)$$
olur.
Herhangi bir durum vektörü \(x\) için
$$\bigl(c^{\mathsf T}x\bigr)^3=\langle c^{\otimes 3},x^{\otimes 3}\rangle$$
yazılabilir; burada \(c^{\otimes 3}=c\otimes c\otimes c\) olur.
Bu yüzden küp blok toplamları üçüncü mertebe tensörlerle ifade edilir. \(r\ge 0\) için
$$\Phi_r(x)=\sum_{m=0}^{2^r-1}\bigl(c^{\mathsf T}A^m x\bigr)^3$$
tanımını yapalım. O zaman bir \(T_r\) tensörü vardır ve
$$\Phi_r(x)=\langle T_r,x^{\otimes 3}\rangle$$
eşitliği sağlanır. Başlangıç durumu doğrudan
$$T_0=c^{\otimes 3}$$
şeklindedir.
Şunu tanımlayalım:
$$A_r=A^{2^r}$$
olsun.
Uzunluğu \(2^{r+1}\) olan bir blok, ardışık iki adet \(2^r\) uzunluklu bloğa ayrılır. Bu nedenle
$$\Phi_{r+1}(x)=\Phi_r(x)+\Phi_r(A_r x)$$
olur.
Buradan tensörler için
$$T_{r+1}=T_r+\mathcal T_{A_r}(T_r)$$
bağıntısı gelir. Buradaki \(\mathcal T_M\), matris \(M\)'yi tensörün üç yuvasının her birine uygulamak demektir. Tanım gereği
$$\langle \mathcal T_M(T),x^{\otimes 3}\rangle=\langle T,(Mx)^{\otimes 3}\rangle$$
sağlanır. Bu, önek toplamların klasik ikili katlama özdeşliğinin tensör karşılığıdır.
\(n=4\) için her taş çifti arasındaki uzaklık en fazla \(3\) olduğu için \(G_4\) tam grafik \(K_4\)'tür.
\(1\)'den \(4\)'e giden rotalarda ortadaki iki yere yalnızca \(2\) ve \(3\) yerleştirilir. Geçerli iki rota
$$1,2,3,4 \qquad \text{ve} \qquad 1,3,2,4$$
olduğundan
$$f(4)=2$$
elde edilir.
Uygulamalar ayrıca şu kontrol değerlerini doğrular:
$$f(6)=14,\qquad f(10)=254,$$
$$S(10)=18230635,$$
ve
$$S(1000)\equiv 225031475 \pmod{10^9}.$$
Bu değerler hem geçiş matrisinin hem de tensör katlamasının doğru kurulduğunu gösterir.
C++, Python ve Java uygulamaları aynı matematiksel iskeleti izler. Önce ilk birkaç taş açıkça genişletilir; çünkü bu evrede sınır boyutu henüz artmaktadır ve sol uç düğümünün derece koşulu özeldir. Daha sonra erişilebilir tüm kanonik sınır durumları çıkarılır ve kararlı geçiş matrisi oluşturulur.
Bundan sonra uzunluk \(4\) için durum vektörü ve tamamlanmış bir rotayı tanıyan seçim vektörü hazırlanır. Ardından \(A^{2^r}\) matris kuvvetleri ve yukarıdaki katlama formülünden gelen \(T_r\) blok tensörleri önceden hesaplanır.
Son adımda \(L-3\)'ün ikili açılımı dolaşılır. Bir bit \(r\) açıksa, önce mevcut durum vektörü için \(T_r\)'nin temsil ettiği bütün blok katkısı eklenir, sonra vektör \(A^{2^r}\) ile ileri taşınır. Başlangıçtaki üç terim \(f(1)^3,f(2)^3,f(3)^3\) ayrıca eklenir. Tüm aritmetik \(10^9\) modunda yapılır.
\(d\), erişilebilir kanonik sınır durumu sayısı olsun. Yerel kural sabit olduğunda \(d\), \(L\)'den bağımsız küçük bir sabittir. Bu yüzden asıl maliyet \(L\)'ye göre logaritmiktir.
Matris kuvvetleri \(O(d^3\log L)\) zaman alır. Her tensör dönüşümü matrisi üç ayrı yuvaya uygular ve seviye başına \(O(d^4)\) maliyetlidir; dolayısıyla tüm blok tensör önhesaplaması \(O(d^4\log L)\) sürer. İkili yürüyüş sırasında seçilen blokların değerlendirilmesi ise \(O(d^3\log L)\) tutar.
Bellek kullanımı, üçüncü mertebe tensörler için \(O(d^3\log L)\), matris kuvvetleri için \(O(d^2\log L)\) düzeyindedir.
Para cada \(n\), sea \(f(n)\) el número de recorridos en los que una rana empieza en la piedra \(1\), termina en la piedra \(n\), visita cada piedra \(1,2,\dots,n\) exactamente una vez y en cada salto avanza una distancia como máximo igual a \(3\).
De forma equivalente, \(f(n)\) cuenta los caminos hamiltonianos de \(1\) a \(n\) en el grafo
$$G_n=(\{1,\dots,n\},E_n),\qquad \{i,j\}\in E_n \iff 1\le |i-j|\le 3.$$
La cantidad pedida es
$$S(L)=\sum_{n=1}^{L} f(n)^3 \pmod{10^9}.$$
Como en el caso principal \(L=10^{14}\), no sirve generar los valores uno por uno. La solución convierte el conteo en un proceso lineal de estados finitos y después suma los cubos mediante lifting binario en la tercera potencia tensorial.
La observación clave es local: si procesamos las piedras de izquierda a derecha, una piedra nueva solo puede conectarse con las tres piedras anteriores. Por eso toda la historia se resume en un pequeño estado de frontera.
Un recorrido válido es una permutación
$$a_1,a_2,\dots,a_n$$
de \(\{1,\dots,n\}\) tal que
$$a_1=1,\qquad a_n=n,\qquad |a_{t+1}-a_t|\le 3 \text{ para todo } t.$$
Los saltos consecutivos forman un camino que usa cada vértice exactamente una vez. Por eso \(f(n)\) es precisamente el número de caminos hamiltonianos entre \(1\) y \(n\) en \(G_n\).
Como las aristas solo unen índices cuya diferencia es a lo sumo \(3\), un vértice suficientemente antiguo ya no podrá recibir aristas nuevas. Ahí nace la compresión por estados.
Supongamos que ya se procesaron las piedras \(1,\dots,t\). Solo las piedras
$$\max(1,t-2),\max(1,t-1),t$$
pueden seguir conectándose con una piedra futura. Por lo tanto solo esas piedras activas deben recordarse.
Para cada piedra activa se guardan dos datos:
$$\text{su grado actual } \in \{0,1,2\},\qquad \text{su etiqueta de componente conexa.}$$
En un camino el grado máximo es \(2\). Las etiquetas de componente indican qué piedras activas ya están unidas por la parte del recorrido construida hasta ese momento.
Los nombres concretos de las etiquetas no importan; solo importa la partición. Por eso se renombran de manera canónica según su primera aparición. Tras esa normalización, el número de estados alcanzables es finito.
Cuando se introduce la piedra \(t+1\), puede conectarse con cero, una o dos piedras activas.
Las restricciones locales son exactamente las restricciones de un camino:
$$\deg(v)\le 2 \text{ para toda piedra activa } v,$$
y si la nueva piedra se conecta con dos piedras activas, esas dos deben pertenecer a componentes distintas; en caso contrario se cerraría un ciclo antes de tiempo.
En cuanto \(t+1\ge 4\), la piedra activa más antigua abandona la frontera para siempre, porque las piedras futuras ya quedan demasiado lejos. En ese momento su grado debe ser definitivo:
$$\deg(1)=1 \text{ cuando sale la piedra } 1,$$
$$\deg(v)=2 \text{ para toda piedra posterior } v \text{ cuando sale.}$$
La primera condición fija a la piedra \(1\) como extremo inicial. La segunda obliga a que toda piedra interior sea un vértice interior del camino hamiltoniano.
Además hay una restricción de conectividad. Si al retirar la piedra activa más antigua desaparece de la frontera toda su componente, esa componente queda sellada y ya no podrá unirse al resto en el futuro. Esa transición es imposible.
Las longitudes pequeñas son excepcionales porque la frontera todavía no tiene tamaño estable. Se obtiene directamente
$$f(1)=f(2)=f(3)=1.$$
Después de procesar las cuatro primeras piedras, la frontera siempre tiene tamaño \(3\). Sean
$$q_1,q_2,\dots,q_d$$
los estados canónicos alcanzables en ese régimen estable.
Sea \(v_n\in (\mathbb Z/10^9\mathbb Z)^d\) el vector columna cuyo componente \(i\)-ésimo cuenta las construcciones parciales de longitud \(n\) que están en el estado \(q_i\). Entonces, para todo \(n\ge 4\),
$$v_{n+1}=A v_n,$$
donde \(A_{ij}\) es el número de extensiones locales válidas que llevan de \(q_j\) a \(q_i\).
Definimos además un vector selector \(c\) por
$$c_i=\begin{cases}1,&\text{si } q_i \text{ representa un único camino conexo con extremo } n,\\ 0,&\text{en otro caso.}\end{cases}$$
Entonces
$$f(n)=c^{\mathsf T}v_n \qquad (n\ge 4).$$
Para cualquier vector de estado \(x\),
$$\bigl(c^{\mathsf T}x\bigr)^3=\langle c^{\otimes 3},x^{\otimes 3}\rangle,$$
donde \(c^{\otimes 3}=c\otimes c\otimes c\).
Por tanto, las sumas por bloques de cubos pueden codificarse con tensores de orden \(3\). Para \(r\ge 0\), definimos
$$\Phi_r(x)=\sum_{m=0}^{2^r-1}\bigl(c^{\mathsf T}A^m x\bigr)^3.$$
Existe un tensor \(T_r\) tal que
$$\Phi_r(x)=\langle T_r,x^{\otimes 3}\rangle.$$
El caso base es
$$T_0=c^{\otimes 3}.$$
Sea
$$A_r=A^{2^r}.$$
Un bloque de longitud \(2^{r+1}\) se parte en dos bloques consecutivos de longitud \(2^r\), así que
$$\Phi_{r+1}(x)=\Phi_r(x)+\Phi_r(A_r x).$$
En consecuencia, los tensores cumplen
$$T_{r+1}=T_r+\mathcal T_{A_r}(T_r),$$
donde \(\mathcal T_M\) significa aplicar la matriz \(M\) en cada una de las tres posiciones tensoriales. Por definición,
$$\langle \mathcal T_M(T),x^{\otimes 3}\rangle=\langle T,(Mx)^{\otimes 3}\rangle.$$
Esta es exactamente la versión tensorial de la identidad de duplicación para sumas prefijas.
Para \(n=4\), cualquier par de piedras está a distancia como máximo \(3\), de modo que \(G_4\) es el grafo completo \(K_4\).
Para contar rutas de \(1\) a \(4\), solo hay que colocar \(2\) y \(3\) en las posiciones intermedias. Las dos rutas válidas son
$$1,2,3,4 \qquad \text{y} \qquad 1,3,2,4,$$
por lo que
$$f(4)=2.$$
Las implementaciones también verifican los puntos de control
$$f(6)=14,\qquad f(10)=254,$$
$$S(10)=18230635,$$
y
$$S(1000)\equiv 225031475 \pmod{10^9}.$$
Estos valores sirven como comprobación fuerte tanto de la matriz de transición como de la suma tensorial por duplicación.
Las implementaciones en C++, Python y Java siguen exactamente esta estructura matemática. Primero expanden explícitamente las primeras pocas piedras, porque la frontera todavía está creciendo y el extremo izquierdo tiene requisitos especiales de grado. Después enumeran todos los estados canónicos alcanzables y construyen la matriz de transición estacionaria.
A continuación forman el vector de estado para la longitud \(4\) y el selector que reconoce una ruta completa. Luego precalculan las potencias \(A^{2^r}\) y los tensores de bloque \(T_r\) usando la fórmula de duplicación.
Por último recorren la expansión binaria de \(L-3\). Cada vez que el bit \(r\) está activo, añaden la contribución completa del bloque representado por \(T_r\) para el vector actual y después avanzan el vector mediante \(A^{2^r}\). Los tres términos iniciales \(f(1)^3,f(2)^3,f(3)^3\) se suman aparte. Toda la aritmética se reduce módulo \(10^9\).
Sea \(d\) el número de estados canónicos de frontera alcanzables. Una vez fijada la regla local, \(d\) es una constante pequeña independiente de \(L\), así que el coste principal crece solo de forma logarítmica con \(L\).
Las potencias de matrices cuestan \(O(d^3\log L)\). Cada transformación tensorial aplica la matriz en tres posiciones y cuesta \(O(d^4)\) por nivel, así que el precálculo completo de tensores cuesta \(O(d^4\log L)\). Evaluar los bloques seleccionados durante el recorrido binario cuesta \(O(d^3\log L)\).
La memoria es \(O(d^3\log L)\) para los tensores de orden \(3\) almacenados y \(O(d^2\log L)\) para las potencias de matrices.
对每个 \(n\)，记 \(f(n)\) 为如下路线的数量：青蛙从第 \(1\) 块石头出发，在第 \(n\) 块石头结束，恰好访问 \(1,2,\dots,n\) 每块石头一次，并且每一步跳跃长度都不超过 \(3\)。
等价地，\(f(n)\) 就是在图
$$G_n=(\{1,\dots,n\},E_n),\qquad \{i,j\}\in E_n \iff 1\le |i-j|\le 3$$
中从 \(1\) 到 \(n\) 的 Hamilton 路径条数。
题目要求计算
$$S(L)=\sum_{n=1}^{L} f(n)^3 \pmod{10^9}.$$
由于主问题中的 \(L=10^{14}\)，显然不能把 \(f(1),f(2),\dots,f(L)\) 逐项算出来再求和。实现采用的办法是：先把路径计数压缩成一个有限状态转移模型，再在三阶张量空间里做二进制倍增，从而直接得到立方前缀和。
整个方法的核心在于“局部性”。如果按石头编号从左到右处理，那么新加入的一块石头只可能与它左边最近的三块石头相连。因此，虽然全局路径很长，真正需要保留的信息却只在一个很小的前沿窗口里。
一条合法路线可以写成一个排列
$$a_1,a_2,\dots,a_n,$$
其中 \(\{a_1,\dots,a_n\}=\{1,\dots,n\}\)，并满足
$$a_1=1,\qquad a_n=n,\qquad |a_{t+1}-a_t|\le 3 \text{ 对所有 } t \text{ 成立}.$$
把相邻跳跃看成无向边，这条路线就是一条恰好经过每个顶点一次的路径。因此问题可以完全等价为：在图 \(G_n\) 中，计算端点固定为 \(1\) 和 \(n\) 的 Hamilton 路径数量。
由于边只在编号差不超过 \(3\) 的顶点之间出现，一个足够靠左的旧顶点以后再也不可能接到新边。正是这一点，使得转移矩阵模型成立。
假设当前已经处理完石头 \(1,\dots,t\)。未来新来的石头只可能和
$$\max(1,t-2),\max(1,t-1),t$$
这几个“仍然可能接受新边”的石头相连，所以状态里只需要保留这些活跃石头的信息。
对每个活跃石头，需要记录两类数据：
$$\text{当前度数 } \in \{0,1,2\},\qquad \text{它所属的连通分量标签。}$$
在一条路径里，任一顶点的度数都不可能超过 \(2\)。而连通分量标签描述的是：在已经构造出的部分路线中，这些活跃石头哪些已经通过已有边连在一起。
分量标签本身的数字没有意义，真正有意义的是分组方式。因此实现会按“首次出现顺序”对标签重新编号，得到规范化状态。经过这种规范化后，可达状态集合就是有限的。
当石头 \(t+1\) 加入时，它可以与当前活跃集合中的零个、一个或两个石头相连。
这些局部规则正好对应于 Hamilton 路径的基本约束：
$$\deg(v)\le 2 \text{ 对每个活跃石头 } v \text{ 都成立},$$
并且如果新石头要同时连向两个活跃石头，那么这两个石头必须来自不同连通分量；否则就会在路径尚未完成之前提前形成一个环。
一旦 \(t+1\ge 4\)，最老的那个活跃石头就必须永久离开前沿，因为后续石头与它的编号差已经大于 \(3\)，再也不能和它连边。这时，它的度数必须已经最终确定：
$$\deg(1)=1 \text{，当石头 } 1 \text{ 离开前沿时},$$
$$\deg(v)=2 \text{，对之后离开的每块石头 } v \text{ 都成立}.$$
第一条保证石头 \(1\) 是整条路线的起点端点。第二条保证所有中间石头最终都成为路径内部顶点。
此外还要满足连通性约束。如果移除最老活跃石头后，它所在的整个连通分量都从前沿中消失了，那么这个分量就被完全封死，未来再也无法与剩余部分合并成一条完整路径。这种转移必须直接丢弃。
最开始几个 \(n\) 是特例，因为这时前沿窗口还没有稳定下来。直接可以得到
$$f(1)=f(2)=f(3)=1.$$
当最前面的四块石头都处理完成后，前沿大小就稳定为 \(3\)。设这个稳定阶段中所有可达的规范化状态为
$$q_1,q_2,\dots,q_d.$$
记 \(v_n\in (\mathbb Z/10^9\mathbb Z)^d\) 为列向量，其中第 \(i\) 项表示长度为 \(n\) 的部分构造目前处于状态 \(q_i\) 的方案数。那么对所有 \(n\ge 4\)，都有
$$v_{n+1}=A v_n,$$
这里 \(A_{ij}\) 表示从状态 \(q_j\) 合法扩展到状态 \(q_i\) 的局部选择数。
再定义一个选择向量 \(c\)：
$$c_i=\begin{cases}1,&\text{若 } q_i \text{ 表示一条连通的完整路径，且末端落在 } n,\\ 0,&\text{否则。}\end{cases}$$
于是
$$f(n)=c^{\mathsf T}v_n \qquad (n\ge 4).$$
对任意状态向量 \(x\)，有
$$\bigl(c^{\mathsf T}x\bigr)^3=\langle c^{\otimes 3},x^{\otimes 3}\rangle,$$
其中 \(c^{\otimes 3}=c\otimes c\otimes c\)。
这说明，按块累加 \(\bigl(c^{\mathsf T}A^m x\bigr)^3\) 时，最自然的对象就是三阶张量。对 \(r\ge 0\)，定义
$$\Phi_r(x)=\sum_{m=0}^{2^r-1}\bigl(c^{\mathsf T}A^m x\bigr)^3.$$
那么一定存在一个三阶张量 \(T_r\)，使得
$$\Phi_r(x)=\langle T_r,x^{\otimes 3}\rangle.$$
基例非常直接：
$$T_0=c^{\otimes 3}.$$
设
$$A_r=A^{2^r}.$$
长度为 \(2^{r+1}\) 的区间可以拆成前后两个长度为 \(2^r\) 的区间，因此
$$\Phi_{r+1}(x)=\Phi_r(x)+\Phi_r(A_r x).$$
于是张量满足递推式
$$T_{r+1}=T_r+\mathcal T_{A_r}(T_r),$$
其中 \(\mathcal T_M\) 表示把矩阵 \(M\) 分别作用到张量的三个指标上。形式化地说，
$$\langle \mathcal T_M(T),x^{\otimes 3}\rangle=\langle T,(Mx)^{\otimes 3}\rangle.$$
这正是普通前缀和倍增公式在三阶张量空间里的对应版本。
取 \(n=4\)。因为任意两块石头之间的距离都不超过 \(3\)，所以 \(G_4\) 就是完全图 \(K_4\)。
若要求路线从 \(1\) 出发并在 \(4\) 结束，那么中间只需要安排石头 \(2\) 和 \(3\) 的顺序。合法路线只有
$$1,2,3,4 \qquad \text{和} \qquad 1,3,2,4,$$
因此
$$f(4)=2.$$
实现还验证了几个关键检查点：
$$f(6)=14,\qquad f(10)=254,$$
$$S(10)=18230635,$$
以及
$$S(1000)\equiv 225031475 \pmod{10^9}.$$
这些数值同时验证了状态转移矩阵和张量倍增求和的正确性。
C++、Python 和 Java 三份实现遵循完全相同的数学结构。首先，它们显式展开最前面的几块石头，因为这时前沿窗口还在增长，而且左端点的度数条件与其他点不同。接着，它们枚举所有可达的规范化前沿状态，并建立稳定阶段的转移矩阵。
然后，程序构造长度 \(4\) 时的状态向量，以及识别“已经形成完整合法路径”的选择向量。接下来预处理所有 \(A^{2^r}\) 以及相应的块张量 \(T_r\)。
最后，对 \(L-3\) 做二进制分解。若第 \(r\) 位为 \(1\)，就把当前状态向量在该整块上的贡献 \(\langle T_r,v^{\otimes 3}\rangle\) 加入答案，再把状态向量更新为 \(A^{2^r}v\)。前三项 \(f(1)^3,f(2)^3,f(3)^3\) 单独加入。全部运算都在模 \(10^9\) 下进行。
设 \(d\) 为可达规范化前沿状态的数量。对于固定的局部规则而言，\(d\) 与 \(L\) 无关，是一个较小常数，因此总复杂度对 \(L\) 主要表现为对数级。
矩阵幂预处理需要 \(O(d^3\log L)\)。每一层的张量变换都要把矩阵作用到三个指标上，代价是 \(O(d^4)\)，所以全部块张量的预处理为 \(O(d^4\log L)\)。在二进制拆分过程中，对被选中的块做求值需要 \(O(d^3\log L)\)。
空间方面，保存三阶张量需要 \(O(d^3\log L)\)，保存矩阵幂需要 \(O(d^2\log L)\)。
Для каждого \(n\) обозначим через \(f(n)\) число маршрутов, в которых лягушка стартует на камне \(1\), заканчивает на камне \(n\), посещает каждый камень \(1,2,\dots,n\) ровно один раз и делает только прыжки длины не более \(3\).
Эквивалентно, \(f(n)\) равно числу гамильтоновых путей из \(1\) в \(n\) в графе
$$G_n=(\{1,\dots,n\},E_n),\qquad \{i,j\}\in E_n \iff 1\le |i-j|\le 3.$$
Требуется вычислить
$$S(L)=\sum_{n=1}^{L} f(n)^3 \pmod{10^9}.$$
Так как в основном случае \(L=10^{14}\), последовательное вычисление всех значений невозможно. Поэтому решение переводит задачу в конечный автомат состояний, а затем считает сумму кубов с помощью двоичного подъема в третьей тензорной степени.
Ключевая идея локальна: если обрабатывать камни слева направо, новый камень может соединяться только с тремя предыдущими. Значит, вся история сжимается до небольшого фронтирного состояния.
Допустимый маршрут задается перестановкой
$$a_1,a_2,\dots,a_n$$
множества \(\{1,\dots,n\}\) с условиями
$$a_1=1,\qquad a_n=n,\qquad |a_{t+1}-a_t|\le 3 \text{ для всех } t.$$
Последовательные прыжки образуют путь, проходящий через каждый вершину ровно один раз. Поэтому \(f(n)\) считает гамильтоновы пути в графе \(G_n\) с фиксированными концами \(1\) и \(n\).
Поскольку ребра существуют только между индексами, отличающимися не более чем на \(3\), достаточно старый камень больше никогда не сможет получить новое ребро. Именно это и позволяет хранить лишь малую границу.
Пусть уже обработаны камни \(1,\dots,t\). Тогда только камни
$$\max(1,t-2),\max(1,t-1),t$$
еще могут соединиться с будущим камнем. Значит, в состоянии достаточно хранить только эти активные камни.
Для каждого активного камня запоминаются две характеристики:
$$\text{его текущая степень } \in \{0,1,2\},\qquad \text{метка его компоненты связности.}$$
В пути степень вершины не может превышать \(2\). Метки компонент говорят, какие активные камни уже связаны между собой через построенную часть маршрута.
Конкретные номера меток несущественны; важна только сама разбивка на компоненты. Поэтому метки перенумеровываются канонически по порядку первого появления. После такой нормализации множество достижимых состояний конечно.
Когда добавляется камень \(t+1\), он может соединиться с нулем, одним или двумя активными камнями.
Локальные ограничения совпадают с ограничениями для пути:
$$\deg(v)\le 2 \text{ для каждого активного камня } v,$$
а если новый камень соединяется сразу с двумя активными камнями, то они должны лежать в разных компонентах, иначе преждевременно образуется цикл.
Как только \(t+1\ge 4\), самый старый активный камень навсегда покидает фронтир, потому что будущие камни уже слишком далеко. В этот момент его степень должна быть окончательной:
$$\deg(1)=1 \text{ при выходе камня } 1,$$
$$\deg(v)=2 \text{ для каждого последующего камня } v \text{ при его выходе}.$$
Первое условие фиксирует камень \(1\) как начальную вершину пути. Второе заставляет каждый внутренний камень стать внутренней вершиной гамильтонова пути.
Есть и дополнительное условие связности. Если после удаления самого старого активного камня вся его компонента исчезает из фронтира, то эта компонента уже отрезана от будущих вершин и никогда не сольется с остальной частью маршрута. Такой переход недопустим.
Первые малые длины особые, потому что размер фронтира еще не стабилизировался. Непосредственно получаем
$$f(1)=f(2)=f(3)=1.$$
После обработки первых четырех камней размер фронтира всегда равен \(3\). Обозначим достижимые канонические фронтирные состояния через
$$q_1,q_2,\dots,q_d.$$
Пусть \(v_n\in (\mathbb Z/10^9\mathbb Z)^d\) — столбец, чей \(i\)-й элемент равен числу частичных конструкций длины \(n\), находящихся в состоянии \(q_i\). Тогда для любого \(n\ge 4\)
$$v_{n+1}=A v_n,$$
где \(A_{ij}\) — число допустимых локальных расширений из состояния \(q_j\) в состояние \(q_i\).
Определим также селектор \(c\):
$$c_i=\begin{cases}1,&\text{если } q_i \text{ представляет один связный путь с концом в } n,\\ 0,&\text{иначе.}\end{cases}$$
Тогда
$$f(n)=c^{\mathsf T}v_n \qquad (n\ge 4).$$
Для любого вектора состояний \(x\) имеем
$$\bigl(c^{\mathsf T}x\bigr)^3=\langle c^{\otimes 3},x^{\otimes 3}\rangle,$$
где \(c^{\otimes 3}=c\otimes c\otimes c\).
Значит, блочные суммы кубов естественно кодируются тензорами третьего порядка. Для \(r\ge 0\) положим
$$\Phi_r(x)=\sum_{m=0}^{2^r-1}\bigl(c^{\mathsf T}A^m x\bigr)^3.$$
Тогда существует тензор \(T_r\), для которого
$$\Phi_r(x)=\langle T_r,x^{\otimes 3}\rangle.$$
Базовый случай:
$$T_0=c^{\otimes 3}.$$
Пусть
$$A_r=A^{2^r}.$$
Блок длины \(2^{r+1}\) распадается на два последовательных блока длины \(2^r\), поэтому
$$\Phi_{r+1}(x)=\Phi_r(x)+\Phi_r(A_r x).$$
Следовательно, тензоры удовлетворяют рекурсии
$$T_{r+1}=T_r+\mathcal T_{A_r}(T_r),$$
где \(\mathcal T_M\) означает применение матрицы \(M\) в каждом из трех тензорных слотов. Формально,
$$\langle \mathcal T_M(T),x^{\otimes 3}\rangle=\langle T,(Mx)^{\otimes 3}\rangle.$$
Это точный тензорный аналог стандартной формулы удвоения для префиксных сумм.
Для \(n=4\) расстояние между любой парой камней не превосходит \(3\), значит \(G_4\) — полный граф \(K_4\).
Чтобы получить маршрут из \(1\) в \(4\), достаточно расставить камни \(2\) и \(3\) посередине. Допустимы ровно два маршрута:
$$1,2,3,4 \qquad \text{и} \qquad 1,3,2,4,$$
поэтому
$$f(4)=2.$$
Реализации также проверяют контрольные значения
$$f(6)=14,\qquad f(10)=254,$$
$$S(10)=18230635,$$
и
$$S(1000)\equiv 225031475 \pmod{10^9}.$$
Эти числа служат сильной проверкой как матрицы переходов, так и тензорного удвоения.
Реализации на C++, Python и Java следуют одной и той же математической схеме. Сначала они явно разворачивают первые несколько камней, потому что фронтир еще растет, а левый конец пути имеет особое требование по степени. Затем перечисляются все достижимые канонические фронтирные состояния и по ним строится стационарная матрица переходов.
После этого формируется вектор состояний для длины \(4\) и селектор, распознающий полностью допустимый маршрут. Затем предвычисляются матричные степени \(A^{2^r}\) и соответствующие им блочные тензоры \(T_r\).
На последнем этапе разбирается двоичная запись числа \(L-3\). Если бит \(r\) установлен, в ответ добавляется вклад всего блока, заданного \(T_r\), для текущего вектора состояний, а затем этот вектор сдвигается вперед умножением на \(A^{2^r}\). Начальные три члена \(f(1)^3,f(2)^3,f(3)^3\) добавляются отдельно. Все вычисления ведутся по модулю \(10^9\).
Пусть \(d\) — число достижимых канонических фронтирных состояний. При фиксированном локальном правиле \(d\) не зависит от \(L\) и остается небольшой константой, поэтому основная зависимость от \(L\) логарифмическая.
Предвычисление матричных степеней стоит \(O(d^3\log L)\). Каждое тензорное преобразование применяет матрицу в трех индексах и занимает \(O(d^4)\) на уровень, так что полный расчет блочных тензоров требует \(O(d^4\log L)\). Вычисление вкладов выбранных блоков в ходе двоичного прохода требует \(O(d^3\log L)\).
Память составляет \(O(d^3\log L)\) для сохраненных тензоров третьего порядка и \(O(d^2\log L)\) для матричных степеней.
لكل \(n\)، نرمز بـ \(f(n)\) إلى عدد المسارات التي تبدأ فيها الضفدعة من الحجر \(1\)، وتنتهي عند الحجر \(n\)، وتزور كل حجر من \(1,2,\dots,n\) مرة واحدة بالضبط، مع شرط أن طول كل قفزة لا يزيد على \(3\).
وبصورة مكافئة، فإن \(f(n)\) هو عدد المسارات الهاملتونية من \(1\) إلى \(n\) في الرسم البياني
$$G_n=(\{1,\dots,n\},E_n),\qquad \{i,j\}\in E_n \iff 1\le |i-j|\le 3.$$
والكمية المطلوبة هي
$$S(L)=\sum_{n=1}^{L} f(n)^3 \pmod{10^9}.$$
بما أن القيمة الأساسية في المسألة هي \(L=10^{14}\)، فلا يمكن حساب \(f(1),f(2),\dots,f(L)\) واحدًا بعد الآخر. لذلك يحول الحل عملية العد إلى نموذج انتقال محدود الحالات، ثم يحسب مجموع المكعبات باستخدام الرفع الثنائي داخل القوة التنسورية الثالثة.
الفكرة الحاسمة محلية تمامًا: إذا عالجنا الأحجار من اليسار إلى اليمين، فإن الحجر الجديد لا يستطيع الاتصال إلا بالأحجار الثلاثة السابقة عليه. ولهذا يمكن ضغط كل التاريخ السابق في حالة حدودية صغيرة.
المسار الصحيح يمكن كتابته على شكل تبديل
$$a_1,a_2,\dots,a_n$$
للمجموعة \(\{1,\dots,n\}\) بحيث تتحقق الشروط التالية لكل \(t\):
$$a_1=1,\qquad a_n=n,\qquad |a_{t+1}-a_t|\le 3.$$
إذا اعتبرنا كل قفزتين متتاليتين كحافة غير موجهة، فإن المسار الناتج يزور كل رأس مرة واحدة فقط. لذلك فإن \(f(n)\) يعد المسارات الهاملتونية ذات الطرفين \(1\) و\(n\) في الرسم \(G_n\).
ولأن الحواف لا تظهر إلا بين رؤوس يفصل بينها فرق لا يتجاوز \(3\)، فإن الحجر القديم بما يكفي لن يستقبل أي حافة جديدة لاحقًا. وهنا بالتحديد يظهر سبب نجاح ضغط الحالة.
لنفترض أننا عالجنا الأحجار \(1,\dots,t\). عندئذ لا يبقى قابلًا للاتصال بحجر مستقبلي إلا الأحجار
$$\max(1,t-2),\max(1,t-1),t.$$
إذن لا نحتاج إلى الاحتفاظ إلا بهذه الأحجار النشطة.
ولكل حجر نشط نخزن درجته الحالية، وهي عنصر من \(\{0,1,2\}\)، كما نخزن وسم المركبة المتصلة التي ينتمي إليها.
في أي مسار بسيط لا يمكن أن تتجاوز درجة أي رأس \(2\). أما أوسمة المركبات فتخبرنا أي الأحجار النشطة أصبحت متصلة ببعضها عبر الجزء الذي بُني حتى الآن من المسار.
أرقام الأوسمة نفسها غير مهمة؛ المهم هو التقسيم فقط. لذلك تعاد تسمية الأوسمة بصورة معيارية حسب أول ظهور لها. بعد هذا التطبيع يصبح عدد الحالات الممكنة محدودًا.
عندما نضيف الحجر \(t+1\)، يمكن وصله بصفر أو بحجر واحد أو بحجرين من الأحجار النشطة الحالية.
القيود المحلية هي نفسها قيود المسار. أولًا يجب أن يبقى
$$\deg(v)\le 2$$
لكل حجر نشط \(v\).
وإذا اتصل الحجر الجديد بحجرين نشطين معًا، فيجب أن يكونا في مركبتين مختلفتين؛ لأن وصلهما وهما في المركبة نفسها سيغلق دورة قبل اكتمال المسار.
ما إن يصبح \(t+1\ge 4\)، حتى يخرج أقدم حجر نشط من الواجهة نهائيًا، لأن الأحجار اللاحقة ستكون بعيدة أكثر من \(3\) عنه. عند تلك اللحظة يجب أن تكون درجته نهائية. بالنسبة إلى الحجر الأول يجب أن يكون
$$\deg(1)=1.$$
أما كل حجر لاحق يغادر الواجهة فيجب أن يحقق
$$\deg(v)=2.$$
الشرط الأول يثبت أن الحجر \(1\) هو طرف البداية. والشرط الثاني يفرض أن كل حجر داخلي يصبح رأسًا داخليًا في المسار الهاملتوني.
وهناك أيضًا شرط اتصال إضافي. فإذا أدى حذف أقدم حجر نشط إلى اختفاء مركبته بالكامل من الواجهة، فإن هذه المركبة تصبح معزولة ولا يمكنها الاندماج مع البقية مستقبلًا. لذا يجب رفض مثل هذا الانتقال.
الأطوال الصغيرة الأولى حالات خاصة لأن حجم الواجهة لم يستقر بعد. نحصل مباشرة على
$$f(1)=f(2)=f(3)=1.$$
بعد معالجة أول أربعة أحجار يصبح حجم الواجهة ثابتًا ويساوي \(3\). ولتكن الحالات المعيارية القابلة للوصول في هذا النظام المستقر هي
$$q_1,q_2,\dots,q_d.$$
ولنرمز بـ \(v_n\in (\mathbb Z/10^9\mathbb Z)^d\) إلى متجه عمودي، مكونه \(i\)-يعد عدد البنى الجزئية بطول \(n\) الموجودة في الحالة \(q_i\). عندئذ لكل \(n\ge 4\) لدينا
$$v_{n+1}=A v_n,$$
حيث إن \(A_{ij}\) هو عدد التوسعات المحلية الصحيحة التي تنقلنا من الحالة \(q_j\) إلى الحالة \(q_i\).
كما نعرف متجه اختيار \(c\) بحيث يكون \(c_i=1\) إذا كانت الحالة \(q_i\) تمثل مسارًا متصلًا واحدًا ينتهي عند \(n\)، ويكون \(c_i=0\) في غير ذلك.
وعندها يصبح
$$f(n)=c^{\mathsf T}v_n \qquad (n\ge 4).$$
لكل متجه حالات \(x\) لدينا
$$\bigl(c^{\mathsf T}x\bigr)^3=\langle c^{\otimes 3},x^{\otimes 3}\rangle,$$
حيث \(c^{\otimes 3}=c\otimes c\otimes c\).
إذًا فإن مجموعات المكعبات على شكل كتل يمكن تمثيلها طبيعيًا بواسطة تنسورات من الرتبة الثالثة. ولأجل \(r\ge 0\) نعرّف
$$\Phi_r(x)=\sum_{m=0}^{2^r-1}\bigl(c^{\mathsf T}A^m x\bigr)^3.$$
عندئذ يوجد تنسور \(T_r\) يحقق
$$\Phi_r(x)=\langle T_r,x^{\otimes 3}\rangle.$$
أما حالة البداية فهي مباشرة:
$$T_0=c^{\otimes 3}.$$
لنضع
$$A_r=A^{2^r}.$$
فالكتلة ذات الطول \(2^{r+1}\) تنقسم إلى كتلتين متتاليتين طول كل منهما \(2^r\)، ولذلك
$$\Phi_{r+1}(x)=\Phi_r(x)+\Phi_r(A_r x).$$
ومن ثم تحقق التنسورات العلاقة
$$T_{r+1}=T_r+\mathcal T_{A_r}(T_r),$$
حيث تعني \(\mathcal T_M\) تطبيق المصفوفة \(M\) على كل واحد من المؤشرات الثلاثة للتنسور. وبالصياغة الرسمية،
$$\langle \mathcal T_M(T),x^{\otimes 3}\rangle=\langle T,(Mx)^{\otimes 3}\rangle.$$
وهذا هو النظير التنسوري تمامًا لصيغة التضاعف المعروفة في المجاميع التراكمية.
عند \(n=4\)، تكون المسافة بين أي حجرين على الأكثر \(3\)، ولذلك يكون \(G_4\) هو الرسم الكامل \(K_4\).
ولكي نعد المسارات من \(1\) إلى \(4\)، لا يبقى إلا ترتيب الحجرين \(2\) و\(3\) في الوسط. والمساران الصحيحان هما
$$1,2,3,4 \qquad \text{and} \qquad 1,3,2,4.$$
ومن ثم
$$f(4)=2.$$
كما تتحقق التطبيقات من قيم فحص مهمة:
$$f(6)=14,\qquad f(10)=254,$$
$$S(10)=18230635,$$
وكذلك
$$S(1000)\equiv 225031475 \pmod{10^9}.$$
وهذه القيم تؤكد صحة كل من مصفوفة الانتقال وآلية جمع المكعبات بالتنسور.
تتبع تطبيقات C++ وPython وJava البنية الرياضية نفسها. في البداية توسع الأحجار القليلة الأولى صراحة، لأن الواجهة ما زالت تكبر ولأن الطرف الأيسر له شرط درجة خاص. بعد ذلك تُعد جميع الحالات المعيارية القابلة للوصول، وتُبنى منها مصفوفة الانتقال في النظام المستقر.
ثم يُنشأ متجه الحالة عند الطول \(4\)، ومعه متجه الاختيار الذي يميز المسار الكامل الصحيح. بعد ذلك تُحسب مسبقًا القوى \(A^{2^r}\) والتنسورات الكتلية \(T_r\) الناتجة من علاقة التضاعف.
وفي الخطوة الأخيرة تُفكك \(L-3\) إلى صورة ثنائية. إذا كانت البتة \(r\) مفعلة، تُضاف مساهمة الكتلة الكاملة التي يمثلها \(T_r\) للحالة الحالية، ثم يُدفع متجه الحالة إلى الأمام بواسطة \(A^{2^r}\). أما الحدود الثلاثة الأولى \(f(1)^3,f(2)^3,f(3)^3\) فتجمع على نحو مستقل. جميع العمليات الحسابية تتم modulo \(10^9\).
ليكن \(d\) هو عدد الحالات الحدودية المعيارية القابلة للوصول. بعد تثبيت القاعدة المحلية يصبح \(d\) ثابتًا صغيرًا مستقلًا عن \(L\)، ولذلك يكون الاعتماد الأساسي على \(L\) لوغاريتميًا.
حساب قوى المصفوفات يكلف \(O(d^3\log L)\). وكل تحويل تنسوري يطبق المصفوفة على ثلاثة مؤشرات، وتكلفته \(O(d^4)\) لكل مستوى، لذا فإن بناء جميع التنسورات الكتلية يكلف \(O(d^4\log L)\). أما تقييم الكتل المختارة أثناء المسح الثنائي فيكلف \(O(d^3\log L)\).
استهلاك الذاكرة هو \(O(d^3\log L)\) للتنسورات المخزنة من الرتبة الثالثة، و\(O(d^2\log L)\) لقوى المصفوفات.