Let \(p=2m\). We count ordered \(p\)-tuples of frog legs, where each leg starts at node \(1\), ends at node \(n\), and every jump has length \(1\), \(2\), or \(3\). Among the internal nodes \(2,3,\dots,n-1\), at most one node may be missed by every leg. The implementations return the count modulo \(10^9\).
Look only at the internal nodes \(2,\dots,n-1\). For one leg, write a binary word of length \(n-2\): put \(1\) when that internal node is visited and \(0\) when it is skipped.
This converts the path problem into a word problem. Because jumps are only \(1\), \(2\), or \(3\), a leg can skip at most two consecutive internal nodes. Therefore valid legs are exactly the binary words with no substring \(000\).
So the problem is not really about geometric paths anymore. It is about \(p=2m\) synchronized binary words of length \(n-2\), each avoiding three consecutive zeros, and we want the union of their \(1\)-positions to miss at most one internal node.
Process the internal nodes from left to right. After some prefix has been processed, a single leg is determined by the number of consecutive processed internal nodes that were skipped since its last visit. That number can only be \(0\), \(1\), or \(2\).
Call these states \(S_0,S_1,S_2\), where \(S_r\) means “the current trailing run of skipped internal nodes has length \(r\)”. A visited node resets the state to \(S_0\). A skipped node sends \(S_0 \to S_1\) and \(S_1 \to S_2\). The transition \(S_2 \to S_3\) is impossible, because that would require a jump of length at least \(4\).
This is the key compression: every leg has many possible detailed histories, but for the next step only the current zero-run length matters.
Now process all \(p\) legs simultaneously. After a prefix of internal nodes, let
$$F_t(a,b,c)$$
be the number of ordered \(p\)-tuples of partial legs such that exactly \(a\) legs are in state \(S_2\), exactly \(b\) legs are in state \(S_1\), and exactly \(c\) legs are in state \(S_0\), with
$$a+b+c=p.$$
The initial state is obvious: before any internal node is processed, no leg has skipped anything yet, so
$$F_0(0,0,p)=1,$$
and all other triples are zero.
The number of possible triples is
$$D=\#\{(a,b,c)\in \mathbb{Z}_{\ge 0}^3:a+b+c=p\}=\binom{p+2}{2}.$$
Since \(p=2m\), this is quadratic in \(m\). For the actual target \(m=10\), we get \(p=20\) and \(D=231\).
Suppose the old triple is \((A,B,C)\). At the next internal node:
If a leg is in \(S_2\), it must visit the node, otherwise the path would contain three consecutive skips.
If a leg is in \(S_1\), it may either visit the node and reset to \(S_0\), or skip it and move to \(S_2\).
If a leg is in \(S_0\), it may either visit the node and stay effectively in \(S_0\), or skip it and move to \(S_1\).
Therefore, if the new triple is \((i,j,k)\), then \(i\) must be the number of old \(S_1\)-legs that skip, and \(j\) must be the number of old \(S_0\)-legs that skip. The rest visit. In the direct counting basis, the recurrence is
$$F_{t+1}(i,j,k)=\sum \binom{B}{i}\binom{C}{j}F_t(A,B,C),$$
where the sum runs over old triples satisfying
$$k=A+(B-i)+(C-j),\qquad A+B+C=p.$$
This already solves the combinatorics, but the implementations use a slightly different basis because it turns the coefficients into the multinomial form used by the matrix construction.
Define scaled coordinates
$$H_t(a,b,c)=a!\,b!\,c!\,F_t(a,b,c).$$
Write the old triple as \((u,v+i,j+w)\), so that \(u+v+w=k\). After substituting the direct recurrence and cancelling factorials, we obtain
$$H_{t+1}(i,j,k)=\sum_{u+v+w=k}\binom{k}{u}\binom{k-u}{v}\,H_t(u,v+i,j+w).$$
This is exactly the transition rule used by the implementations. The coefficient
$$\binom{k}{u}\binom{k-u}{v}=\frac{k!}{u!\,v!\,w!}$$
is a multinomial count: among the \(k\) legs that do visit the current node, choose how many came from the old \(S_2\), old \(S_1\), and old \(S_0\) groups.
So the dense matrix is indexed only by triples \((a,b,c)\), not by individual legs. That symmetry reduction is what makes the problem tractable.
Let \(g_q(n)\) denote the number of ordered \(p\)-tuples of full legs for which exactly \(q\) internal nodes are missed by every leg. The target of the problem is
$$g_0(n)+g_1(n).$$
Introduce the generating polynomial
$$G_n(y)=\sum_{q\ge 0} g_q(n)(1+y)^q.$$
At one internal node there are two possibilities: either at least one leg visits it, contributing a factor \(1\), or every leg skips it, contributing a factor \(1+y\).
Let \(T\) be the total transition matrix from Step 5, and let \(Z\) be the submatrix corresponding to the special case “every leg skips the current node”. That special case is deterministic:
$$ (0,a,p-a)\longrightarrow (a,p-a,0). $$
Hence the weighted one-node transfer is
$$M(y)=T+yZ,$$
because \(T\) already includes the all-skip case once, and the extra \(yZ\) changes its weight from \(1\) to \(1+y\).
Let \(e_0\) be the basis vector of the initial triple \((0,0,p)\). After the \(n-2\) internal nodes are processed, we get
$$V_{n-2}(y)=M(y)^{n-2}e_0.$$
There is still a final jump to node \(n\). A leg finishing in state \(S_0\), \(S_1\), or \(S_2\) must use a final jump of length \(1\), \(2\), or \(3\), respectively, so every terminal automaton state has exactly one legal completion. In the factorial-scaled basis, the corresponding closure row is obtained from the row indexed by \((0,0,p)\) in the total transition matrix. Denote this row by \(L\).
Therefore
$$G_n(y)=L\,M(y)^{n-2}e_0.$$
Now evaluate at \(y=-1\). Since \((1-1)^q\) vanishes for every \(q\ge 1\), we get
$$G_n(-1)=g_0(n).$$
Also,
$$\left.\frac{d}{dy}(1+y)^q\right|_{y=-1}=\begin{cases}1,&q=1,\\0,&q\neq 1,\end{cases}$$
so
$$G_n'(-1)=g_1(n).$$
Hence the required count is
$$\boxed{g_0(n)+g_1(n)=G_n(-1)+G_n'(-1)\pmod{10^9}.}$$
Here \(p=2\) and the internal nodes are \(2\) and \(3\). A single leg can be one of four paths:
\(1\to4\), \(1\to2\to4\), \(1\to3\to4\), or \(1\to2\to3\to4\).
So there are \(4^2=16\) ordered pairs of legs. The only invalid pair is the pair in which both legs jump directly \(1\to4\), because then both internal nodes are missed and we have \(q=2\).
Therefore
$$g_0(4)=9,\qquad g_1(4)=6,\qquad g_2(4)=1,$$
and the desired value is
$$g_0(4)+g_1(4)=9+6=15.$$
This matches the small checkpoint used by the implementations.
The C++, Python, and Java implementations all follow the same mathematics. They enumerate all triples \((a,b,c)\) with \(a+b+c=2m\), precompute the needed binomial coefficients, build the dense total-transition matrix and the all-skip submatrix, and work entirely modulo \(10^9\).
The hard part is the huge exponent \(n-2\), so the implementation does not iterate over vertices one by one. Instead it evaluates \(M(-1)^{n-2}\) and its derivative at \(y=-1\) by binary matrix exponentiation. If \(U(y)\) and \(V(y)\) are matrix-valued factors, the derivative is updated by the product rule
$$\frac{d}{dy}(UV)=U'V+UV'.$$
After exponentiation, the implementation applies the terminal closure row, extracts \(G_n(-1)\) and \(G_n'(-1)\), adds them, and reduces the result modulo \(10^9\). The Python version delegates to the same compiled algorithm, so all three language implementations compute the identical transfer-matrix formula.
The state-space dimension is
$$D=\binom{2m+2}{2}=O(m^2).$$
Dense matrix multiplication dominates the runtime. Binary exponentiation needs \(O(\log n)\) matrix products, so the overall complexity is
$$O(D^3\log n)$$
time and
$$O(D^2)$$
memory. The preliminary binomial table is only \(O(m^2)\) and is negligible compared with the matrix work.
Setze \(p=2m\). Gesucht ist die Anzahl geordneter \(p\)-Tupel von Teilwegen, bei denen jeder Teilweg bei Knoten \(1\) startet, bei Knoten \(n\) endet und nur Sprünge der Länge \(1\), \(2\) oder \(3\) benutzt. Unter den inneren Knoten \(2,3,\dots,n-1\) darf höchstens ein Knoten von allen Teilwegen gemeinsam ausgelassen werden. Das Ergebnis wird modulo \(10^9\) ausgegeben.
Betrachte nur die inneren Knoten \(2,\dots,n-1\). Für einen einzelnen Teilweg schreiben wir ein Binärwort der Länge \(n-2\): \(1\), wenn der betreffende innere Knoten besucht wird, und \(0\), wenn er übersprungen wird.
Damit wird aus dem Wegproblem ein Wortproblem. Da nur Sprünge der Länge \(1\), \(2\) oder \(3\) erlaubt sind, können niemals drei aufeinanderfolgende innere Knoten ausgelassen werden. Zulässige Teilwege sind also genau die Binärwörter ohne Teilwort \(000\).
Wir zählen somit \(p=2m\) synchronisierte Binärwörter der Länge \(n-2\), die jeweils keine drei Nullen hintereinander enthalten, und deren Vereinigungsmenge an Eins-Positionen höchstens einen inneren Knoten auslässt.
Wir verarbeiten die inneren Knoten von links nach rechts. Nach einem bereits bearbeiteten Präfix genügt für einen Teilweg die Information, wie lang die aktuelle Endfolge ausgelassener innerer Knoten seit dem letzten Besuch ist. Diese Länge kann nur \(0\), \(1\) oder \(2\) sein.
Bezeichne diese Zustände mit \(S_0,S_1,S_2\). Ein besuchter Knoten setzt den Zustand auf \(S_0\) zurück. Ein ausgelassener Knoten bewirkt \(S_0 \to S_1\) und \(S_1 \to S_2\). Ein weiterer Auslassungsschritt aus \(S_2\) wäre unmöglich, denn er würde einen Sprung der Länge mindestens \(4\) erzwingen.
Genau diese Zustandskompression macht die spätere Matrixmethode möglich.
Nun verarbeiten wir alle \(p\) Teilwege gleichzeitig. Nach \(t\) bearbeiteten inneren Knoten sei
$$F_t(a,b,c)$$
die Anzahl der geordneten \(p\)-Tupel partieller Wege mit genau \(a\) Teilwegen in \(S_2\), genau \(b\) Teilwegen in \(S_1\) und genau \(c\) Teilwegen in \(S_0\), also
$$a+b+c=p.$$
Am Anfang wurde noch kein innerer Knoten betrachtet, also stehen alle Teilwege in \(S_0\):
$$F_0(0,0,p)=1.$$
Die Anzahl möglicher Zustände ist
$$D=\#\{(a,b,c)\in \mathbb{Z}_{\ge 0}^3:a+b+c=p\}=\binom{p+2}{2}.$$
Für den Zielwert \(m=10\) erhält man \(p=20\) und damit \(D=231\).
Sei \((A,B,C)\) das alte Tripel. Beim nächsten inneren Knoten gilt:
Teilwege in \(S_2\) müssen den Knoten besuchen.
Teilwege in \(S_1\) dürfen entweder besuchen und nach \(S_0\) zurückkehren oder auslassen und nach \(S_2\) wechseln.
Teilwege in \(S_0\) dürfen entweder besuchen oder auslassen und nach \(S_1\) wechseln.
Wenn das neue Tripel \((i,j,k)\) ist, dann ist \(i\) die Zahl der alten \(S_1\)-Wege, die auslassen, und \(j\) die Zahl der alten \(S_0\)-Wege, die auslassen. In der direkten Zählbasis ergibt sich
$$F_{t+1}(i,j,k)=\sum \binom{B}{i}\binom{C}{j}F_t(A,B,C),$$
wobei
$$k=A+(B-i)+(C-j),\qquad A+B+C=p.$$
Diese Rekursion ist mathematisch korrekt, aber die Implementierungen verwenden eine skalierte Basis, weil daraus genau die multinomialen Matrixeinträge entstehen.
Definiere
$$H_t(a,b,c)=a!\,b!\,c!\,F_t(a,b,c).$$
Schreibt man das alte Tripel als \((u,v+i,j+w)\) mit \(u+v+w=k\), dann vereinfacht sich die Rekursion zu
$$H_{t+1}(i,j,k)=\sum_{u+v+w=k}\binom{k}{u}\binom{k-u}{v}\,H_t(u,v+i,j+w).$$
Genau diese Formel wird in der Matrix verwendet. Der Faktor
$$\binom{k}{u}\binom{k-u}{v}=\frac{k!}{u!\,v!\,w!}$$
ist ein Multinomialkoeffizient und zählt, wie sich die \(k\) besuchenden Teilwege aus den drei alten Zustandsgruppen zusammensetzen.
Sei \(g_q(n)\) die Anzahl geordneter \(p\)-Tupel vollständiger Wege, bei denen genau \(q\) innere Knoten von allen Teilwegen gemeinsam ausgelassen werden. Gesucht ist
$$g_0(n)+g_1(n).$$
Dazu führen wir das Polynom
$$G_n(y)=\sum_{q\ge 0} g_q(n)(1+y)^q$$
ein. Ein innerer Knoten trägt den Faktor \(1\), wenn mindestens ein Teilweg ihn besucht, und den Faktor \(1+y\), wenn ihn alle Teilwege auslassen.
Sei \(T\) die gesamte Übergangsmatrix aus Schritt 5 und \(Z\) die Teilmatrix für den Spezialfall „alle lassen den aktuellen Knoten aus“. Dieser Spezialfall ist deterministisch:
$$ (0,a,p-a)\longrightarrow (a,p-a,0). $$
Darum lautet der gewichtete Ein-Schritt-Übergang
$$M(y)=T+yZ,$$
denn \(T\) enthält den Fall „alle auslassen“ bereits einmal mit Gewicht \(1\), und der Zusatz \(yZ\) hebt dieses Gewicht auf \(1+y\) an.
Sei \(e_0\) der Basisvektor des Anfangszustands \((0,0,p)\). Nach den \(n-2\) inneren Knoten gilt
$$V_{n-2}(y)=M(y)^{n-2}e_0.$$
Danach fehlt nur noch der letzte Sprung zu Knoten \(n\). Ein Teilweg in \(S_0\), \(S_1\) oder \(S_2\) muss dann mit einem Schluss-Sprung der Länge \(1\), \(2\) bzw. \(3\) enden; die Vervollständigung ist also eindeutig. In der skalierten Basis erhält man den Abschlussvektor aus der zu \((0,0,p)\) gehörenden Zeile der Gesamtmatrix. Bezeichne diese Zeile mit \(L\).
Dann ist
$$G_n(y)=L\,M(y)^{n-2}e_0.$$
Setzt man \(y=-1\), so bleibt nur der Fall ohne vollständig ausgelassene innere Knoten übrig:
$$G_n(-1)=g_0(n).$$
Außerdem gilt
$$\left.\frac{d}{dy}(1+y)^q\right|_{y=-1}=\begin{cases}1,&q=1,\\0,&q\neq 1,\end{cases}$$
also
$$G_n'(-1)=g_1(n).$$
Damit folgt die Endformel
$$\boxed{g_0(n)+g_1(n)=G_n(-1)+G_n'(-1)\pmod{10^9}.}$$
Hier ist \(p=2\) und die inneren Knoten sind \(2\) und \(3\). Ein einzelner Teilweg kann genau einer der vier Wege
\(1\to4\), \(1\to2\to4\), \(1\to3\to4\) oder \(1\to2\to3\to4\)
sein. Also gibt es \(4^2=16\) geordnete Paare von Teilwegen.
Ungültig ist nur das Paar, in dem beide Teilwege direkt \(1\to4\) springen. Dann bleiben nämlich beide inneren Knoten unbesucht, also \(q=2\).
Somit
$$g_0(4)=9,\qquad g_1(4)=6,\qquad g_2(4)=1,$$
und daher
$$g_0(4)+g_1(4)=15.$$
Die C++-, Python- und Java-Implementierungen verwenden dieselbe Mathematik. Sie erzeugen alle Tripel \((a,b,c)\) mit \(a+b+c=2m\), berechnen die benötigten Binomialkoeffizienten vor, bauen die dichte Gesamtmatrix und die Teilmatrix für vollständig ausgelassene Knoten auf und rechnen vollständig modulo \(10^9\).
Da \(n\) riesig ist, werden die \(n-2\) inneren Knoten nicht einzeln simuliert. Stattdessen berechnet die Implementierung \(M(-1)^{n-2}\) und gleichzeitig die Ableitung nach \(y\) per binärer Matrixpotenzierung. Für matrixwertige Faktoren \(U(y)\) und \(V(y)\) wird dabei konsequent die Produktregel
$$\frac{d}{dy}(UV)=U'V+UV'$$
verwendet. Anschließend wird der Abschlussvektor angewandt, \(G_n(-1)\) und \(G_n'(-1)\) werden addiert, und das Ergebnis wird modulo \(10^9\) reduziert. Die Python-Version delegiert auf denselben kompilierten Kern, daher rechnen alle drei Sprachen dieselbe Transfer-Matrix-Formel aus.
Die Zustandsdimension ist
$$D=\binom{2m+2}{2}=O(m^2).$$
Dominant sind dichte Matrixmultiplikationen. Durch binäre Exponentiation erhält man insgesamt
$$O(D^3\log n)$$
Zeit und
$$O(D^2)$$
Speicher. Die vorberechnete Binomialtabelle kostet nur \(O(m^2)\) und fällt gegenüber den Matrixprodukten kaum ins Gewicht.
\(p=2m\) olsun. Her biri \(1\) düğümünden başlayıp \(n\) düğümünde biten ve yalnızca \(1\), \(2\) veya \(3\) uzunluklu sıçramalar kullanan sıralı \(p\)-li yol kümelerini sayıyoruz. İç düğümler \(2,3,\dots,n-1\) arasında en fazla bir düğüm bütün kollar tarafından birlikte hiç ziyaret edilmemiş olabilir. Sonuç \(10^9\) modunda verilir.
Sadece iç düğümlere \(2,\dots,n-1\) bakalım. Tek bir kol için, ilgili iç düğüm ziyaret ediliyorsa \(1\), atlanıyorsa \(0\) yazıp uzunluğu \(n-2\) olan bir ikili dizi oluşturabiliriz.
Böylece yol problemi bir kelime problemine dönüşür. Sıçrama uzunlukları yalnızca \(1\), \(2\) ve \(3\) olduğundan, bir kol art arda üç iç düğümü atlayamaz. Dolayısıyla geçerli kollar tam olarak içinde \(000\) alt dizisi bulunmayan ikili dizilerdir.
Artık problem, uzunluğu \(n-2\) olan ve her biri üç ardışık sıfır içermeyen \(p=2m\) adet eşzamanlı ikili diziyi saymaktır; bu dizilerin \(1\) konumlarının birleşimi en fazla bir iç düğümü dışarıda bırakmalıdır.
İç düğümleri soldan sağa işleyelim. İşlenmiş bir önekten sonra, bir kolu belirlemek için yalnızca son ziyaretten beri art arda kaç işlenmiş iç düğümün atlandığını bilmek yeterlidir. Bu sayı yalnızca \(0\), \(1\) veya \(2\) olabilir.
Bu durumlara \(S_0,S_1,S_2\) diyelim. Düğüm ziyaret edilirse durum \(S_0\)'a sıfırlanır. Düğüm atlanırsa \(S_0 \to S_1\) ve \(S_1 \to S_2\) olur. \(S_2\)'den bir kez daha atlamak imkansızdır; bu, en az \(4\) uzunlukta bir sıçrama gerektirirdi.
Önemli sıkıştırma burada ortaya çıkar: ayrıntılı geçmişe gerek yoktur, bir sonraki adım için yalnızca mevcut sıfır-koşusu uzunluğu gerekir.
Şimdi tüm \(p\) kolu aynı anda işleyelim. \(t\) iç düğüm işlendiğinde
$$F_t(a,b,c)$$
ifadesi, tam olarak \(a\) kolu \(S_2\)'de, tam olarak \(b\) kolu \(S_1\)'de ve tam olarak \(c\) kolu \(S_0\)'da olan sıralı kısmi yol \(p\)-lilerinin sayısı olsun. Elbette
$$a+b+c=p.$$
Başlangıçta hiç iç düğüm işlenmediği için bütün kollar \(S_0\)'dadır:
$$F_0(0,0,p)=1.$$
Olası durum sayısı
$$D=\#\{(a,b,c)\in \mathbb{Z}_{\ge 0}^3:a+b+c=p\}=\binom{p+2}{2}$$
olur. Hedef parametre \(m=10\) için \(p=20\) ve \(D=231\) elde edilir.
Eski durum \((A,B,C)\) olsun. Bir sonraki iç düğümde şu kurallar geçerlidir:
\(S_2\)'deki kollar düğümü ziyaret etmek zorundadır.
\(S_1\)'deki kollar ya ziyaret edip \(S_0\)'a döner ya da atlayıp \(S_2\)'ye geçer.
\(S_0\)'daki kollar ya ziyaret eder ya da atlayıp \(S_1\)'e geçer.
Yeni üçlü \((i,j,k)\) ise, \(i\) eski \(S_1\) kollarından atlayanların, \(j\) ise eski \(S_0\) kollarından atlayanların sayısıdır. Doğrudan sayım tabanında bağıntı
$$F_{t+1}(i,j,k)=\sum \binom{B}{i}\binom{C}{j}F_t(A,B,C)$$
şeklindedir; burada
$$k=A+(B-i)+(C-j),\qquad A+B+C=p.$$
Bu bağıntı doğrudur; ancak uygulamalar katsayıları multinom biçimine dönüştüren ölçekli bir taban kullanır.
Şunu tanımlayalım:
$$H_t(a,b,c)=a!\,b!\,c!\,F_t(a,b,c).$$
Eski üçlüyü \((u,v+i,j+w)\) biçiminde yazarsak ve \(u+v+w=k\) olursa, bağıntı
$$H_{t+1}(i,j,k)=\sum_{u+v+w=k}\binom{k}{u}\binom{k-u}{v}\,H_t(u,v+i,j+w)$$
haline gelir. Kodun kurduğu yoğun matris tam olarak budur. Buradaki
$$\binom{k}{u}\binom{k-u}{v}=\frac{k!}{u!\,v!\,w!}$$
katsayısı, düğümü ziyaret eden \(k\) kolun eski üç durum sınıfından nasıl geldiğini sayan multinom katsayısıdır.
\(g_q(n)\), tam olarak \(q\) iç düğümün bütün kollar tarafından birlikte atlandığı sıralı tam yol \(p\)-lilerinin sayısı olsun. Aradığımız büyüklük
$$g_0(n)+g_1(n)$$
olur. Bunun için
$$G_n(y)=\sum_{q\ge 0} g_q(n)(1+y)^q$$
üreteç polinomunu tanımlıyoruz. Bir iç düğüm en az bir kol tarafından ziyaret ediliyorsa çarpan \(1\), bütün kollar tarafından atlanıyorsa çarpan \(1+y\) getirir.
\(T\) toplam geçiş matrisi, \(Z\) ise “herkes atlıyor” alt matrisi olsun. Bu özel durum deterministiktir:
$$ (0,a,p-a)\longrightarrow (a,p-a,0). $$
Bu nedenle ağırlıklı tek-adım geçişi
$$M(y)=T+yZ$$
şeklindedir; çünkü \(T\) içinde bu tümden atlama durumu zaten bir kez \(1\) ağırlığıyla vardır ve ek \(yZ\) terimi ağırlığı \(1+y\)'ye yükseltir.
\((0,0,p)\) başlangıç durumunun taban vektörüne \(e_0\) diyelim. \(n-2\) iç düğüm işlendiğinde
$$V_{n-2}(y)=M(y)^{n-2}e_0$$
elde edilir. Ardından \(n\) düğümüne son sıçrama kalır. \(S_0\), \(S_1\), \(S_2\) durumunda biten bir kol sırasıyla \(1\), \(2\), \(3\) uzunluklu son sıçramayı yapmak zorundadır; yani her terminal durumun tamamlama biçimi tektir. Faktöriyel ölçekli tabanda kapanış satırı, toplam geçiş matrisinde \((0,0,p)\) satırından elde edilir. Bu satıra \(L\) diyelim.
Dolayısıyla
$$G_n(y)=L\,M(y)^{n-2}e_0$$
olur. \(y=-1\) için yalnızca hiç ortak atlama olmayan durum kalır:
$$G_n(-1)=g_0(n).$$
Ayrıca
$$\left.\frac{d}{dy}(1+y)^q\right|_{y=-1}=\begin{cases}1,&q=1,\\0,&q\neq 1,\end{cases}$$
olduğundan
$$G_n'(-1)=g_1(n).$$
Sonuç olarak
$$\boxed{g_0(n)+g_1(n)=G_n(-1)+G_n'(-1)\pmod{10^9}.}$$
Burada \(p=2\) ve iç düğümler \(2\) ile \(3\)'tür. Tek bir kol için dört olası yol vardır:
\(1\to4\), \(1\to2\to4\), \(1\to3\to4\), \(1\to2\to3\to4\).
Bu yüzden sıralı yol çiftlerinin sayısı \(4^2=16\)'dır. Geçersiz olan tek çift, iki kolun da doğrudan \(1\to4\) sıçraması yaptığı çifttir; çünkü o zaman iki iç düğüm de birlikte atlanır ve \(q=2\) olur.
Dolayısıyla
$$g_0(4)=9,\qquad g_1(4)=6,\qquad g_2(4)=1,$$
ve aranan değer
$$g_0(4)+g_1(4)=15$$
olur.
C++, Python ve Java uygulamaları aynı matematiksel yapıyı izler. \(a+b+c=2m\) koşulunu sağlayan bütün üçlüleri üretir, gerekli binom katsayılarını önceden hesaplar, toplam geçiş matrisini ve “herkesin atladığı düğüm” alt matrisini kurar ve her şeyi \(10^9\) modunda yürütür.
\(n\) çok büyük olduğu için iç düğümler tek tek işlenmez. Bunun yerine, ikili matris üs alma ile \(M(-1)^{n-2}\) ve aynı anda türevi hesaplanır. Matris değerli çarpanlar için güncelleme kuralı
$$\frac{d}{dy}(UV)=U'V+UV'$$
ürün türevi kuralıdır. Son aşamada kapanış satırı uygulanır, \(G_n(-1)\) ve \(G_n'(-1)\) toplanır ve sonuç \(10^9\) moduna göre indirgenir. Python sürümü aynı derlenmiş algoritmayı çağırdığı için üç dil de özdeş transfer-matris hesabını yapar.
Durum uzayı boyutu
$$D=\binom{2m+2}{2}=O(m^2)$$
olur. Baskın maliyet yoğun matris çarpımıdır. İkili üs alma nedeniyle toplam süre
$$O(D^3\log n)$$
ve bellek kullanımı
$$O(D^2)$$
mertebesindedir. Binom tablosunun ön hesabı sadece \(O(m^2)\) olduğundan asıl maliyet matris işlemlerinden gelir.
Sea \(p=2m\). Debemos contar \(p\)-tuplas ordenadas de trayectos de la rana, donde cada trayecto empieza en el nodo \(1\), termina en el nodo \(n\) y usa saltos de longitud \(1\), \(2\) o \(3\). Entre los nodos internos \(2,3,\dots,n-1\), como mucho uno puede quedar sin ser visitado por ningún trayecto. El resultado se devuelve módulo \(10^9\).
Miremos solo los nodos internos \(2,\dots,n-1\). Para un trayecto individual escribimos una palabra binaria de longitud \(n-2\): ponemos \(1\) si ese nodo interno es visitado y \(0\) si se salta.
Así el problema de caminos se convierte en un problema sobre palabras. Como los saltos permitidos son solo \(1\), \(2\) y \(3\), un trayecto nunca puede omitir tres nodos internos consecutivos. Por tanto, los trayectos válidos son exactamente las palabras binarias que no contienen el bloque \(000\).
En consecuencia, contamos \(p=2m\) palabras binarias sincronizadas, cada una sin tres ceros consecutivos, y queremos que la unión de sus posiciones con \(1\) deje fuera como mucho un nodo interno.
Procesamos los nodos internos de izquierda a derecha. Tras procesar un prefijo, para un trayecto basta saber cuántos nodos internos procesados consecutivos han sido omitidos desde la última visita. Ese número solo puede ser \(0\), \(1\) o \(2\).
Llamemos \(S_0,S_1,S_2\) a esos estados. Visitar el nodo actual reinicia el estado a \(S_0\). Omitirlo produce \(S_0 \to S_1\) y \(S_1 \to S_2\). La transición \(S_2 \to S_3\) es imposible, porque correspondería a un salto de longitud al menos \(4\).
La historia detallada de un trayecto ya no importa: para continuar solo hace falta la longitud actual de esa racha final de omisiones.
Ahora procesamos los \(p\) trayectos a la vez. Después de \(t\) nodos internos, definimos
$$F_t(a,b,c)$$
como el número de \(p\)-tuplas ordenadas de trayectos parciales con exactamente \(a\) trayectos en \(S_2\), exactamente \(b\) en \(S_1\) y exactamente \(c\) en \(S_0\), de modo que
$$a+b+c=p.$$
El estado inicial es
$$F_0(0,0,p)=1,$$
porque al principio ningún trayecto ha omitido todavía ningún nodo interno.
El número de triples posibles es
$$D=\#\{(a,b,c)\in \mathbb{Z}_{\ge 0}^3:a+b+c=p\}=\binom{p+2}{2}.$$
Para el objetivo real \(m=10\) tenemos \(p=20\) y por tanto \(D=231\).
Supongamos que el triple antiguo es \((A,B,C)\). En el siguiente nodo interno:
Los trayectos en \(S_2\) están forzados a visitar el nodo.
Los trayectos en \(S_1\) pueden visitarlo y volver a \(S_0\), o saltarlo y pasar a \(S_2\).
Los trayectos en \(S_0\) pueden visitarlo o saltarlo y pasar a \(S_1\).
Si el nuevo triple es \((i,j,k)\), entonces \(i\) es el número de trayectos antiguos en \(S_1\) que saltan el nodo y \(j\) es el número de trayectos antiguos en \(S_0\) que lo saltan. En la base directa de conteo obtenemos
$$F_{t+1}(i,j,k)=\sum \binom{B}{i}\binom{C}{j}F_t(A,B,C),$$
con
$$k=A+(B-i)+(C-j),\qquad A+B+C=p.$$
Esta es la recurrencia fundamental, aunque la implementación usa una base reescalada para convertir los coeficientes en la forma multinomial que se ve en la matriz.
Definimos
$$H_t(a,b,c)=a!\,b!\,c!\,F_t(a,b,c).$$
Si escribimos el triple antiguo como \((u,v+i,j+w)\) con \(u+v+w=k\), la recurrencia pasa a ser
$$H_{t+1}(i,j,k)=\sum_{u+v+w=k}\binom{k}{u}\binom{k-u}{v}\,H_t(u,v+i,j+w).$$
Esta es exactamente la regla usada por la matriz. El coeficiente
$$\binom{k}{u}\binom{k-u}{v}=\frac{k!}{u!\,v!\,w!}$$
es un coeficiente multinomial que cuenta cómo se reparten los \(k\) trayectos que sí visitan el nodo actual entre los tres grupos antiguos.
Sea \(g_q(n)\) el número de \(p\)-tuplas ordenadas de trayectos completos en las que exactamente \(q\) nodos internos son omitidos por todos los trayectos. La cantidad pedida es
$$g_0(n)+g_1(n).$$
Introducimos el polinomio generador
$$G_n(y)=\sum_{q\ge 0} g_q(n)(1+y)^q.$$
En cada nodo interno hay dos casos: si al menos un trayecto lo visita, el factor es \(1\); si todos lo omiten, el factor es \(1+y\).
Sea \(T\) la matriz de transición total y \(Z\) la submatriz del caso especial “todos omiten el nodo actual”. Ese caso es determinista:
$$ (0,a,p-a)\longrightarrow (a,p-a,0). $$
Por tanto, la transición ponderada en un nodo es
$$M(y)=T+yZ,$$
porque \(T\) ya contiene el caso de omisión global con peso \(1\), y el término extra \(yZ\) cambia ese peso a \(1+y\).
Sea \(e_0\) el vector base del estado inicial \((0,0,p)\). Después de procesar los \(n-2\) nodos internos tenemos
$$V_{n-2}(y)=M(y)^{n-2}e_0.$$
Luego todavía falta el salto final al nodo \(n\). Un trayecto que termina en \(S_0\), \(S_1\) o \(S_2\) debe cerrar con un salto de longitud \(1\), \(2\) o \(3\), respectivamente, así que cada estado terminal tiene una única completación válida. En la base escalada, la fila de cierre se obtiene de la fila indexada por \((0,0,p)\) en la matriz total. Denotémosla por \(L\).
Entonces
$$G_n(y)=L\,M(y)^{n-2}e_0.$$
Al evaluar en \(y=-1\), solo sobrevive el caso \(q=0\):
$$G_n(-1)=g_0(n).$$
Además,
$$\left.\frac{d}{dy}(1+y)^q\right|_{y=-1}=\begin{cases}1,&q=1,\\0,&q\neq 1,\end{cases}$$
de modo que
$$G_n'(-1)=g_1(n).$$
Concluimos que
$$\boxed{g_0(n)+g_1(n)=G_n(-1)+G_n'(-1)\pmod{10^9}.}$$
Aquí \(p=2\) y los nodos internos son \(2\) y \(3\). Un trayecto individual puede ser
\(1\to4\), \(1\to2\to4\), \(1\to3\to4\) o \(1\to2\to3\to4\).
Hay por tanto \(4^2=16\) pares ordenados de trayectos. El único par inválido es aquel en el que ambos trayectos saltan directamente \(1\to4\), porque entonces los dos nodos internos quedan omitidos y \(q=2\).
Así,
$$g_0(4)=9,\qquad g_1(4)=6,\qquad g_2(4)=1,$$
y por ello
$$g_0(4)+g_1(4)=15.$$
Las implementaciones en C++, Python y Java siguen exactamente la misma matemática. Enumeran todos los triples \((a,b,c)\) con \(a+b+c=2m\), precalculan los coeficientes binomiales necesarios, construyen la matriz densa de transición total y la submatriz correspondiente a los nodos omitidos por todos, y trabajan siempre módulo \(10^9\).
El valor de \(n\) es enorme, así que no se avanza nodo por nodo. En su lugar se calcula \(M(-1)^{n-2}\) y, al mismo tiempo, su derivada con respecto a \(y\) mediante exponenciación binaria de matrices. Para factores matriciales \(U(y)\) y \(V(y)\), la actualización usa la regla del producto
$$\frac{d}{dy}(UV)=U'V+UV'.$$
Al final se aplica la fila de cierre, se obtienen \(G_n(-1)\) y \(G_n'(-1)\), se suman y se reduce el resultado módulo \(10^9\). La versión en Python delega en el mismo núcleo compilado, así que las tres implementaciones calculan la misma fórmula de matriz de transferencia.
La dimensión del espacio de estados es
$$D=\binom{2m+2}{2}=O(m^2).$$
El coste dominante es la multiplicación de matrices densas. Con exponenciación binaria, el coste total es
$$O(D^3\log n)$$
en tiempo y
$$O(D^2)$$
en memoria. La tabla inicial de binomiales solo cuesta \(O(m^2)\), así que es secundaria frente al trabajo matricial.
设 \(p=2m\)。我们要统计 有序 的 \(p\) 条路径序列：每条路径都从节点 \(1\) 出发，到节点 \(n\) 结束，并且每一步只能跳 \(1\)、\(2\) 或 \(3\) 个单位。在内部节点 \(2,3,\dots,n-1\) 中，至多只有一个节点可以被所有路径同时漏掉。结果按 \(10^9\) 取模。
只看内部节点 \(2,\dots,n-1\)。对一条路径来说，如果某个内部节点被访问，就写成 \(1\)；如果被跳过，就写成 \(0\)。于是每条路径对应一个长度为 \(n-2\) 的二进制串。
这样一来，原题就变成了字符串问题。因为允许的跳长只有 \(1,2,3\)，所以一条路径不可能连续跳过三个内部节点。换句话说，合法路径恰好对应那些不含子串 \(000\) 的二进制串。
因此我们要数的是 \(p=2m\) 个同步的二进制串，它们都避免出现三个连续的零，并且这些串中所有 \(1\) 的并集最多漏掉一个内部节点。
从左到右处理内部节点。处理完一个前缀后，对于某一条路径，接下来真正需要记住的信息只有一件事：自从上一次访问以来，最近已经连续跳过了多少个内部节点。这个数只能是 \(0\)、\(1\) 或 \(2\)。
记这三个状态为 \(S_0,S_1,S_2\)。如果当前节点被访问，状态就重置为 \(S_0\)。如果当前节点被跳过，则 \(S_0 \to S_1\)，\(S_1 \to S_2\)。而 \(S_2 \to S_3\) 不可能发生，因为那意味着需要长度至少为 \(4\) 的跳跃。
这一步是核心压缩：路径的详细历史不再重要，后续转移只依赖当前“连续漏点长度”。
现在同时处理这 \(p\) 条路径。设处理了前 \(t\) 个内部节点之后，
$$F_t(a,b,c)$$
表示有序 \(p\) 路径组的数量，其中恰有 \(a\) 条路径处于 \(S_2\)，恰有 \(b\) 条路径处于 \(S_1\)，恰有 \(c\) 条路径处于 \(S_0\)，并满足
$$a+b+c=p.$$
初始时还没有处理任何内部节点，所以所有路径都在 \(S_0\)：
$$F_0(0,0,p)=1.$$
可行三元组的总数为
$$D=\#\{(a,b,c)\in \mathbb{Z}_{\ge 0}^3:a+b+c=p\}=\binom{p+2}{2}.$$
在目标参数 \(m=10\) 下，\(p=20\)，因此 \(D=231\)。
设旧状态是 \((A,B,C)\)。面对下一个内部节点时：
处于 \(S_2\) 的路径必须访问该节点。
处于 \(S_1\) 的路径可以访问并回到 \(S_0\)，也可以跳过并进入 \(S_2\)。
处于 \(S_0\) 的路径可以访问，也可以跳过并进入 \(S_1\)。
如果新状态是 \((i,j,k)\)，那么 \(i\) 必须是旧 \(S_1\) 中选择跳过的条数，\(j\) 必须是旧 \(S_0\) 中选择跳过的条数。于是直接计数递推为
$$F_{t+1}(i,j,k)=\sum \binom{B}{i}\binom{C}{j}F_t(A,B,C),$$
其中
$$k=A+(B-i)+(C-j),\qquad A+B+C=p.$$
这已经给出了正确的组合递推，但实现中还要做一次基底变换，把系数改写成更适合矩阵构造的多项式形式。
定义
$$H_t(a,b,c)=a!\,b!\,c!\,F_t(a,b,c).$$
把旧三元组写成 \((u,v+i,j+w)\)，并令 \(u+v+w=k\)，则递推化为
$$H_{t+1}(i,j,k)=\sum_{u+v+w=k}\binom{k}{u}\binom{k-u}{v}\,H_t(u,v+i,j+w).$$
这正是程序中矩阵条目的来源。系数
$$\binom{k}{u}\binom{k-u}{v}=\frac{k!}{u!\,v!\,w!}$$
是一个多项式系数，它表示“当前这个节点被访问的 \(k\) 条路径”分别来自旧的三类状态的哪一部分。
设 \(g_q(n)\) 表示恰好有 \(q\) 个内部节点被所有路径同时漏掉的有序 \(p\) 路径组数量。题目要求的是
$$g_0(n)+g_1(n).$$
引入生成多项式
$$G_n(y)=\sum_{q\ge 0} g_q(n)(1+y)^q.$$
对每个内部节点而言，如果至少有一条路径访问它，贡献因子就是 \(1\)；如果所有路径都跳过它，贡献因子就是 \(1+y\)。
记 \(T\) 为总转移矩阵，记 \(Z\) 为“所有路径都跳过当前节点”的子矩阵。这个特殊转移是确定性的：
$$ (0,a,p-a)\longrightarrow (a,p-a,0). $$
因此单点加权转移写成
$$M(y)=T+yZ,$$
因为 \(T\) 中已经把“全跳过”这一种情况计入了一次，而额外的 \(yZ\) 正好把它的权重从 \(1\) 改成 \(1+y\)。
设 \(e_0\) 是初始状态 \((0,0,p)\) 的基向量。处理完 \(n-2\) 个内部节点以后，得到
$$V_{n-2}(y)=M(y)^{n-2}e_0.$$
接下来还剩最后一步到节点 \(n\)。如果某条路径结束于 \(S_0\)、\(S_1\)、\(S_2\)，那么它最后一跳的长度分别只能是 \(1\)、\(2\)、\(3\)，所以每个终态都有唯一的合法收尾方式。在阶乘缩放后的基底中，这个终结行向量来自总转移矩阵中标号为 \((0,0,p)\) 的那一行，记作 \(L\)。
于是
$$G_n(y)=L\,M(y)^{n-2}e_0.$$
当 \(y=-1\) 时，只有 \(q=0\) 的项保留下来：
$$G_n(-1)=g_0(n).$$
另一方面，
$$\left.\frac{d}{dy}(1+y)^q\right|_{y=-1}=\begin{cases}1,&q=1,\\0,&q\neq 1,\end{cases}$$
所以
$$G_n'(-1)=g_1(n).$$
因此答案为
$$\boxed{g_0(n)+g_1(n)=G_n(-1)+G_n'(-1)\pmod{10^9}.}$$
此时 \(p=2\)，内部节点是 \(2\) 和 \(3\)。单条路径共有四种可能：
\(1\to4\)，\(1\to2\to4\)，\(1\to3\to4\)，\(1\to2\to3\to4\)。
所以有序路径对一共有 \(4^2=16\) 个。唯一无效的情况是两条路径都直接走 \(1\to4\)，因为这样两个内部节点都会被同时漏掉，也就是 \(q=2\)。
因此
$$g_0(4)=9,\qquad g_1(4)=6,\qquad g_2(4)=1,$$
从而
$$g_0(4)+g_1(4)=15.$$
C++、Python 和 Java 实现都遵循完全相同的数学结构。它们枚举所有满足 \(a+b+c=2m\) 的三元组，预先计算需要的二项式系数，构造总转移矩阵与“全跳过”子矩阵，并且始终在模 \(10^9\) 下运算。
由于 \(n\) 极大，程序不会逐点推进，而是使用矩阵二分快速幂同时计算 \(M(-1)^{n-2}\) 及其关于 \(y\) 的导数。对于矩阵值函数 \(U(y)\) 和 \(V(y)\)，更新依赖乘积法则
$$\frac{d}{dy}(UV)=U'V+UV'.$$
最后再应用终结行向量，得到 \(G_n(-1)\) 与 \(G_n'(-1)\)，两者相加后按 \(10^9\) 取模。Python 版本只是调用同一套编译后的核心算法，因此三种语言实现计算的是同一条转移矩阵公式。
状态空间维度为
$$D=\binom{2m+2}{2}=O(m^2).$$
主成本是稠密矩阵乘法。结合二分快速幂，总时间复杂度为
$$O(D^3\log n),$$
空间复杂度为
$$O(D^2).$$
预处理二项式表只需要 \(O(m^2)\)，相对于矩阵运算可以忽略。
Пусть \(p=2m\). Нужно посчитать упорядоченные \(p\)-наборы путей лягушки, где каждый путь начинается в вершине \(1\), заканчивается в вершине \(n\) и использует прыжки длины \(1\), \(2\) или \(3\). Среди внутренних вершин \(2,3,\dots,n-1\) не более одной может оказаться непосещённой всеми путями одновременно. Ответ берётся по модулю \(10^9\).
Рассмотрим только внутренние вершины \(2,\dots,n-1\). Для одного пути запишем двоичное слово длины \(n-2\): ставим \(1\), если соответствующая внутренняя вершина посещена, и \(0\), если она перепрыгнута.
Тогда задача о путях превращается в задачу о словах. Поскольку разрешены только прыжки длины \(1\), \(2\) и \(3\), один путь не может пропустить три внутренние вершины подряд. Значит, допустимые пути в точности соответствуют двоичным словам без подслова \(000\).
Итак, мы считаем \(p=2m\) синхронных двоичных слов длины \(n-2\), каждое из которых избегает трёх подряд идущих нулей, и хотим, чтобы объединение их единичных позиций пропускало не более одной внутренней вершины.
Будем обрабатывать внутренние вершины слева направо. После обработки некоторого префикса для одного пути достаточно знать только длину текущей конечной серии пропущенных внутренних вершин после последнего посещения. Это число может быть только \(0\), \(1\) или \(2\).
Обозначим эти состояния через \(S_0,S_1,S_2\). Посещение текущей вершины сбрасывает состояние в \(S_0\). Пропуск переводит \(S_0 \to S_1\) и \(S_1 \to S_2\). Переход \(S_2 \to S_3\) невозможен, потому что он потребовал бы прыжок длины как минимум \(4\).
Это и есть нужное сжатие: подробная история пути больше не важна, для следующего шага нужна только текущая длина хвоста из пропусков.
Теперь рассматриваем все \(p\) путей одновременно. После обработки \(t\) внутренних вершин пусть
$$F_t(a,b,c)$$
обозначает число упорядоченных \(p\)-наборов частичных путей, в которых ровно \(a\) путей находятся в состоянии \(S_2\), ровно \(b\) путей в состоянии \(S_1\), и ровно \(c\) путей в состоянии \(S_0\), так что
$$a+b+c=p.$$
Начальное состояние очевидно:
$$F_0(0,0,p)=1,$$
поскольку до обработки первой внутренней вершины ни один путь ещё ничего не пропускал.
Число возможных троек равно
$$D=\#\{(a,b,c)\in \mathbb{Z}_{\ge 0}^3:a+b+c=p\}=\binom{p+2}{2}.$$
Для целевого случая \(m=10\) получаем \(p=20\) и, следовательно, \(D=231\).
Пусть старая тройка равна \((A,B,C)\). На следующей внутренней вершине:
Пути в состоянии \(S_2\) обязаны посетить вершину.
Пути в состоянии \(S_1\) могут либо посетить вершину и вернуться в \(S_0\), либо пропустить её и перейти в \(S_2\).
Пути в состоянии \(S_0\) могут либо посетить вершину, либо пропустить её и перейти в \(S_1\).
Если новая тройка равна \((i,j,k)\), то \(i\) есть число старых путей из \(S_1\), которые пропускают текущую вершину, а \(j\) есть число старых путей из \(S_0\), которые её пропускают. В прямом базисе счёта имеем рекурсию
$$F_{t+1}(i,j,k)=\sum \binom{B}{i}\binom{C}{j}F_t(A,B,C),$$
где
$$k=A+(B-i)+(C-j),\qquad A+B+C=p.$$
Это уже точная комбинаторика, но в реализации используется немного другой базис, потому что он превращает коэффициенты в удобную мультиномиальную форму.
Определим
$$H_t(a,b,c)=a!\,b!\,c!\,F_t(a,b,c).$$
Если записать старую тройку в виде \((u,v+i,j+w)\) при \(u+v+w=k\), то рекурсия превращается в
$$H_{t+1}(i,j,k)=\sum_{u+v+w=k}\binom{k}{u}\binom{k-u}{v}\,H_t(u,v+i,j+w).$$
Именно эта формула и реализована матрицей. Коэффициент
$$\binom{k}{u}\binom{k-u}{v}=\frac{k!}{u!\,v!\,w!}$$
является мультиномиальным коэффициентом и считает, как \(k\) путей, посетивших текущую вершину, распределяются между тремя старыми группами состояний.
Пусть \(g_q(n)\) обозначает число упорядоченных \(p\)-наборов полных путей, в которых ровно \(q\) внутренних вершин пропущены всеми путями сразу. Искомая величина равна
$$g_0(n)+g_1(n).$$
Введём производящий многочлен
$$G_n(y)=\sum_{q\ge 0} g_q(n)(1+y)^q.$$
Если хотя бы один путь посещает текущую внутреннюю вершину, вклад равен \(1\). Если её пропускают все пути, вклад равен \(1+y\).
Обозначим через \(T\) полную матрицу перехода, а через \(Z\) подматрицу специального случая “текущую вершину пропустили все”. Этот случай детерминирован:
$$ (0,a,p-a)\longrightarrow (a,p-a,0). $$
Значит, взвешенный одношаговый переход имеет вид
$$M(y)=T+yZ,$$
поскольку матрица \(T\) уже содержит случай общего пропуска один раз с весом \(1\), а добавка \(yZ\) меняет этот вес на \(1+y\).
Пусть \(e_0\) — базисный вектор начальной тройки \((0,0,p)\). После обработки \(n-2\) внутренних вершин получаем
$$V_{n-2}(y)=M(y)^{n-2}e_0.$$
После этого остаётся последний прыжок в вершину \(n\). Путь, заканчивающийся в состоянии \(S_0\), \(S_1\) или \(S_2\), обязан завершиться прыжком длины \(1\), \(2\) или \(3\) соответственно, так что каждое терминальное состояние имеет ровно одно допустимое завершение. В факториально масштабированном базисе строка закрытия получается из строки полной матрицы, соответствующей \((0,0,p)\). Обозначим её через \(L\).
Тогда
$$G_n(y)=L\,M(y)^{n-2}e_0.$$
Подстановка \(y=-1\) оставляет только случаи без общих пропусков:
$$G_n(-1)=g_0(n).$$
Кроме того,
$$\left.\frac{d}{dy}(1+y)^q\right|_{y=-1}=\begin{cases}1,&q=1,\\0,&q\neq 1,\end{cases}$$
поэтому
$$G_n'(-1)=g_1(n).$$
Итак, окончательная формула равна
$$\boxed{g_0(n)+g_1(n)=G_n(-1)+G_n'(-1)\pmod{10^9}.}$$
Здесь \(p=2\), а внутренние вершины — это \(2\) и \(3\). Один путь может быть одним из четырёх:
\(1\to4\), \(1\to2\to4\), \(1\to3\to4\), \(1\to2\to3\to4\).
Следовательно, существует \(4^2=16\) упорядоченных пар путей. Недопустима только одна пара: когда оба пути прыгают напрямую \(1\to4\). Тогда обе внутренние вершины оказываются пропущенными, то есть \(q=2\).
Поэтому
$$g_0(4)=9,\qquad g_1(4)=6,\qquad g_2(4)=1,$$
и потому
$$g_0(4)+g_1(4)=15.$$
Реализации на C++, Python и Java используют одну и ту же математику. Они перечисляют все тройки \((a,b,c)\) с условием \(a+b+c=2m\), заранее вычисляют нужные биномиальные коэффициенты, строят плотную полную матрицу перехода и подматрицу общего пропуска и выполняют все вычисления по модулю \(10^9\).
Так как \(n\) огромно, внутренние вершины не обрабатываются по одной. Вместо этого реализация вычисляет \(M(-1)^{n-2}\) и одновременно его производную по \(y\) с помощью бинарного возведения матриц в степень. Для матричных множителей \(U(y)\) и \(V(y)\) используется правило произведения
$$\frac{d}{dy}(UV)=U'V+UV'.$$
После этого применяется строка закрытия, извлекаются \(G_n(-1)\) и \(G_n'(-1)\), они складываются, и результат редуцируется по модулю \(10^9\). Версия на Python делегирует ту же скомпилированную сердцевину, так что все три языка считают одну и ту же формулу матрицы переходов.
Размерность пространства состояний равна
$$D=\binom{2m+2}{2}=O(m^2).$$
Основная стоимость — умножение плотных матриц. С бинарным возведением в степень общее время равно
$$O(D^3\log n),$$
а память —
$$O(D^2).$$
Предварительная таблица биномиальных коэффициентов требует только \(O(m^2)\) и по сравнению с матричной частью мала.
ليكن \(p=2m\). نريد عدَّ مجموعات مرتبة من \(p\) مسارات، حيث يبدأ كل مسار من العقدة \(1\)، وينتهي عند العقدة \(n\)، ويستعمل قفزات بطول \(1\) أو \(2\) أو \(3\) فقط. وبين العقد الداخلية \(2,3,\dots,n-1\) يجوز أن توجد عقدة واحدة على الأكثر لا يزورها أي مسار من هذه المسارات. الناتج يؤخذ بترديد \(10^9\).
ننظر فقط إلى العقد الداخلية \(2,\dots,n-1\). لكل مسار منفرد نكتب سلسلة ثنائية طولها \(n-2\): نضع \(1\) إذا زار المسار تلك العقدة الداخلية، ونضع \(0\) إذا قفز فوقها.
بهذا تتحول المسألة من مسارات هندسية إلى مسألة على سلاسل ثنائية. وبما أن أطوال القفز الممكنة هي فقط \(1\) و\(2\) و\(3\)، فلا يمكن لمسار واحد أن يتجاوز ثلاث عقد داخلية متتالية. لذلك فالمسارات الصحيحة تقابل تمامًا السلاسل الثنائية التي لا تحتوي على القطعة \(000\).
إذن نحن نعد \(p=2m\) سلاسل ثنائية متزامنة، كل واحدة منها تخلو من ثلاثة أصفار متتالية، ونشترط أن اتحاد مواضع الـ \(1\) فيها يترك عقدة داخلية واحدة على الأكثر غير مزارة.
نعالج العقد الداخلية من اليسار إلى اليمين. بعد معالجة بادئة ما، فإن المعلومة الوحيدة اللازمة عن مسار واحد هي عدد العقد الداخلية المعالجة المتتالية التي تم تجاوزها منذ آخر زيارة. هذا العدد لا يمكن أن يكون إلا \(0\) أو \(1\) أو \(2\).
لنسمِّ هذه الحالات \(S_0,S_1,S_2\). زيارة العقدة الحالية تعيد الحالة إلى \(S_0\). أمّا تجاوزها فيعطي \(S_0 \to S_1\) و\(S_1 \to S_2\). والانتقال \(S_2 \to S_3\) غير ممكن، لأنه يتطلب قفزة طولها على الأقل \(4\).
هذه هي نقطة الضغط الأساسية: لا نحتاج إلى التاريخ الكامل للمسار، بل فقط إلى طول سلسلة التجاوزات المتتالية الحالية.
الآن نعالج جميع المسارات \(p\) معًا. بعد معالجة \(t\) عقد داخلية، ليكن
$$F_t(a,b,c)$$
هو عدد المجموعات المرتبة من المسارات الجزئية التي يكون فيها بالضبط \(a\) مسارات في الحالة \(S_2\)، و\(b\) مسارات في الحالة \(S_1\)، و\(c\) مسارات في الحالة \(S_0\)، بحيث
$$a+b+c=p.$$
الحالة الابتدائية واضحة:
$$F_0(0,0,p)=1,$$
لأننا قبل معالجة أي عقدة داخلية لم نتجاوز شيئًا بعد.
وعدد الثلاثيات الممكنة هو
$$D=\#\{(a,b,c)\in \mathbb{Z}_{\ge 0}^3:a+b+c=p\}=\binom{p+2}{2}.$$
وللحالة الهدف \(m=10\) نحصل على \(p=20\) وبالتالي \(D=231\).
افترض أن الحالة القديمة هي \((A,B,C)\). عند العقدة الداخلية التالية:
المسارات الموجودة في \(S_2\) مجبرة على زيارة العقدة.
المسارات الموجودة في \(S_1\) يمكنها إما الزيارة والعودة إلى \(S_0\)، أو التجاوز والانتقال إلى \(S_2\).
المسارات الموجودة في \(S_0\) يمكنها إما الزيارة، أو التجاوز والانتقال إلى \(S_1\).
إذا كانت الحالة الجديدة هي \((i,j,k)\)، فإن \(i\) هو عدد المسارات القديمة في \(S_1\) التي تجاوزت العقدة، و\(j\) هو عدد المسارات القديمة في \(S_0\) التي تجاوزتها. في أساس العد المباشر تصبح العلاقة
$$F_{t+1}(i,j,k)=\sum \binom{B}{i}\binom{C}{j}F_t(A,B,C),$$
مع الشرط
$$k=A+(B-i)+(C-j),\qquad A+B+C=p.$$
هذه هي العلاقة الصحيحة، لكن التطبيق يستخدم أساسًا مُعاد القياس لأن ذلك يحول المعاملات إلى الشكل متعدد الحدود الظاهر في المصفوفة.
نعرّف
$$H_t(a,b,c)=a!\,b!\,c!\,F_t(a,b,c).$$
إذا كتبنا الثلاثية القديمة على الصورة \((u,v+i,j+w)\) حيث \(u+v+w=k\)، فإن العلاقة تصبح
$$H_{t+1}(i,j,k)=\sum_{u+v+w=k}\binom{k}{u}\binom{k-u}{v}\,H_t(u,v+i,j+w).$$
وهذه بالضبط هي القاعدة التي تبني بها التطبيقات المصفوفة. أما المعامل
$$\binom{k}{u}\binom{k-u}{v}=\frac{k!}{u!\,v!\,w!}$$
فهو معامل متعدد حدود يَعُدُّ كيف تتوزع المسارات \(k\) التي تزور العقدة الحالية بين المجموعات الثلاث القديمة.
ليكن \(g_q(n)\) هو عدد المجموعات المرتبة من المسارات الكاملة التي يُتجاوز فيها بالضبط \(q\) عقد داخلية بواسطة جميع المسارات معًا. المطلوب هو
$$g_0(n)+g_1(n).$$
نُدخل كثير الحدود المولد
$$G_n(y)=\sum_{q\ge 0} g_q(n)(1+y)^q.$$
إذا زارت عقدة داخلية واحدة على الأقل من المسارات، فالعامل المرافق لها هو \(1\). وإذا تجاوزتها جميع المسارات، فالعامل هو \(1+y\).
لنرمز بـ \(T\) إلى مصفوفة الانتقال الكلية، وبـ \(Z\) إلى المصفوفة الجزئية للحالة الخاصة “الجميع يتجاوز العقدة الحالية”. هذه الحالة حتمية:
$$ (0,a,p-a)\longrightarrow (a,p-a,0). $$
إذن الانتقال الموزون لعقدة واحدة هو
$$M(y)=T+yZ,$$
لأن \(T\) يحتوي أصلًا على حالة التجاوز الجماعي مرة واحدة بوزن \(1\)، والحد الإضافي \(yZ\) يرفع الوزن إلى \(1+y\).
ليكن \(e_0\) متجه الأساس للحالة الابتدائية \((0,0,p)\). بعد معالجة \(n-2\) عقدة داخلية نحصل على
$$V_{n-2}(y)=M(y)^{n-2}e_0.$$
بعد ذلك يبقى فقط القفز النهائي إلى العقدة \(n\). إذا انتهى مسار ما في الحالة \(S_0\) أو \(S_1\) أو \(S_2\)، فإن القفزة الأخيرة يجب أن يكون طولها \(1\) أو \(2\) أو \(3\) على الترتيب، ولذلك فلكل حالة نهائية طريقة وحيدة صحيحة للإكمال. في الأساس المضروب بالعوامل، نحصل على سطر الإغلاق من السطر الموافق للحالة \((0,0,p)\) داخل مصفوفة الانتقال الكلية. ولنرمز إلى هذا السطر بـ \(L\).
وعندئذ
$$G_n(y)=L\,M(y)^{n-2}e_0.$$
وعندما نضع \(y=-1\)، لا يبقى إلا الحد الموافق لـ \(q=0\):
$$G_n(-1)=g_0(n).$$
كذلك لدينا
$$\left.\frac{d}{dy}(1+y)^q\right|_{y=-1}=\begin{cases}1,&q=1,\\0,&q\neq 1,\end{cases}$$
ومن ثم
$$G_n'(-1)=g_1(n).$$
إذن الجواب النهائي هو
$$\boxed{g_0(n)+g_1(n)=G_n(-1)+G_n'(-1)\pmod{10^9}.}$$
هنا \(p=2\)، والعقد الداخلية هي \(2\) و\(3\). للمسار الواحد أربع إمكانات:
\(1\to4\)، \(1\to2\to4\)، \(1\to3\to4\)، \(1\to2\to3\to4\).
إذًا يوجد \(4^2=16\) زوجًا مرتبًا من المسارات. والحالة الوحيدة غير الصالحة هي أن يقفز المساران مباشرة \(1\to4\)، لأن العقدتين الداخليتين كلتيهما ستبقيان غير مزارتين، أي \(q=2\).
ومن ثم
$$g_0(4)=9,\qquad g_1(4)=6,\qquad g_2(4)=1,$$
وبالتالي
$$g_0(4)+g_1(4)=15.$$
تتبع تطبيقات C++ وPython وJava البنية الرياضية نفسها. فهي تعدِّد جميع الثلاثيات \((a,b,c)\) التي تحقق \(a+b+c=2m\)، وتحسب معاملات ذي الحدين المطلوبة مسبقًا، وتبني مصفوفة الانتقال الكلية والمصفوفة الجزئية الخاصة بحالة التجاوز الجماعي، وتعمل كلها بترديد \(10^9\).
ولأن \(n\) كبير جدًا، فلا تتم محاكاة العقد الداخلية واحدةً واحدة. بدلًا من ذلك، تحسب التطبيقات \(M(-1)^{n-2}\) ومشتقته بالنسبة إلى \(y\) في الوقت نفسه باستعمال الأس الثنائي للمصفوفات. إذا كان لدينا عاملان مصفوحيان \(U(y)\) و\(V(y)\)، فإن التحديث يعتمد على قاعدة مشتقة الجداء
$$\frac{d}{dy}(UV)=U'V+UV'.$$
ثم يُطبَّق سطر الإغلاق النهائي، ويُستخرج \(G_n(-1)\) و\(G_n'(-1)\)، وتُجمع القيمتان ويُختزل الناتج بترديد \(10^9\). أما نسخة Python فهي مجرد غلاف رقيق فوق الخوارزمية المترجمة نفسها، لذلك فالتطبيقات الثلاثة تحسب الصيغة نفسها تمامًا.
بُعد فضاء الحالات هو
$$D=\binom{2m+2}{2}=O(m^2).$$
والكلفة المسيطرة هي ضرب المصفوفات الكثيفة. ومع استعمال الأس الثنائي نحصل على زمن كلي
$$O(D^3\log n)$$
وذاكرة
$$O(D^2).$$
أما جدول معاملات ذي الحدين فيُحسب في \(O(m^2)\) فقط، لذا فتكلفته مهملة مقارنة بعمل المصفوفات.