The provided C++ solution encodes the following walk-counting problem on a path graph. Consider the vertices \(0,1,\dots,n\) in a line. The walk starts at vertex \(0\), each move changes the position by exactly \(1\), and the boundary condition is \(0 \le x \le n\). The last vertex \(n\) is auxiliary: it may be visited arbitrarily often and is not tracked. For every tracked vertex \(0 \le i \lt n\), the walk must visit \(i\) exactly \(k+i\) times.
Let \(W(n,k)\) denote the number of valid walks that satisfy all those visit constraints and end at any endpoint \(e \in \{0,1,\dots,n\}\). The program computes
$$\Bigl(W(500,1)+W(500,10)+W(500,100)+W(500,1000)+W(500,10000)\Bigr)\bmod 987898789.$$
The checkpoints hard-coded in the file are
$$W(3,2)=17,\qquad W(6,1)=1320,\qquad W(6,5)=16793280.$$
For a fixed endpoint \(e\), define for each edge \(i\) between \(i-1\) and \(i\) (\(1 \le i \le n\)):
$$R_i=\#\{\text{crossings } i-1 \to i\},\qquad L_i=\#\{\text{crossings } i \to i-1\}.$$
Because the walk starts to the left of every edge, the net balance across edge \(i\) is determined by whether the endpoint lies to the right of that edge:
$$R_i-L_i=\mathbf{1}_{e \ge i}.$$
This is the key observation: once the endpoint is fixed, the imbalance on every edge is fixed as well.
Write
$$t_i=k+i\qquad (0 \le i \lt n)$$
for the required visit count of tracked vertex \(i\).
At vertex \(0\), the walk starts with one visit already counted, and every later visit must come from edge \(1\). Therefore
$$1+L_1=t_0=k,$$
so
$$R_1=L_1+\mathbf{1}_{e \ge 1}=k-\mathbf{1}_{e=0}.$$
For an interior tracked vertex \(i\) with \(1 \le i \lt n\), every visit to \(i\) comes either from the left through edge \(i\) or from the right through edge \(i+1\). Hence
$$t_i=R_i+L_{i+1}=k+i.$$
Using \(R_{i+1}=L_{i+1}+\mathbf{1}_{e \ge i+1}\), we get
$$R_{i+1}=k+i-R_i+\mathbf{1}_{e>i}.$$
This is exactly the recurrence implemented in solve_endpoint. So for a fixed endpoint,
all right-crossing counts \(R_1,R_2,\dots,R_n\) are forced.
Now cut the path between \(i-1\) and \(i\), where \(1 \le i \lt n\). From the viewpoint of vertex \(i-1\), everything on the right side \(\{i,i+1,\dots,n\}\) is an excursion block: once the walk crosses from \(i-1\) to \(i\), it wanders inside the suffix and later either returns to \(i-1\) or, on the final excursion, ends on the right side.
Across this cut, the walk makes \(R_i\) left-to-right excursions in total. The first such excursion is forced by the existence of the suffix activity. After that, the remaining \(R_i-1\) excursions can be attached to any subset of the \(t_{i-1}=k+i-1\) visits to vertex \(i-1\). Therefore the number of choices contributed by this cut is
$$\binom{k+i-1}{R_i-1}.$$
There is no extra factor for the last edge \(n\), because the suffix \(\{n\}\) is trivial: once the walk reaches the auxiliary vertex, the only local behavior is an immediate return or the final stop.
The choices coming from different cuts are nested but independent once the crossing numbers are fixed. Therefore, for a fixed endpoint \(e\), the total number of valid walks is
$$\boxed{W(n,k;e)=\prod_{i=1}^{n-1}\binom{k+i-1}{R_i-1}.}$$
Finally we sum over all possible endpoints:
$$\boxed{W(n,k)=\sum_{e=0}^{n} W(n,k;e).}$$
Here the tracked visit counts are \(t_0=2\), \(t_1=3\), \(t_2=4\).
If \(e=0\), then \(R_1=1\), \(R_2=2\), and
$$W(3,2;0)=\binom{2}{0}\binom{3}{1}=3.$$
If \(e=1\), then \(R_1=2\), \(R_2=1\), and
$$W(3,2;1)=\binom{2}{1}\binom{3}{0}=2.$$
If \(e=2\), then \(R_1=2\), \(R_2=2\), and
$$W(3,2;2)=\binom{2}{1}\binom{3}{1}=6.$$
If \(e=3\), the same crossing numbers occur, so
$$W(3,2;3)=6.$$
Thus
$$W(3,2)=3+2+6+6=17,$$
which matches the checkpoint used by the code.
The values \(\binom{r}{c}\) become enormous, so the implementation never constructs them exactly. It builds the needed rows of Pascal's triangle modulo
$$M=987898789.$$
For the target computation, the required rows are \(k,k+1,\dots,k+n-2\) for
\(k \in \{1,10,100,1000,10000\}\). The helper build_needed_binomials walks through Pascal's
triangle once, stores only the rows that will actually be queried later, and then every endpoint
evaluation becomes a product lookup modulo \(M\).
build_needed_binomials precomputes Pascal rows modulo \(987898789\). Then
solve_endpoint fixes an endpoint \(e\), reconstructs the forced sequence of right-crossing
counts \(R_i\), and multiplies the corresponding binomial factors. The wrapper solve sums
those counts over all \(e=0,\dots,n\). Finally solve_target evaluates
\(W(500,k)\) for the five required \(k\)-values and adds the results modulo \(987898789\).
The brute-force routine is only a checkpoint mechanism for tiny instances. It recursively explores all admissible walks for \(n \le 6\), memoizes states, and confirms that the closed-form combinatorial count matches explicit enumeration.
Let
$$M=\max(K)+n-2,$$
where \(K=\{1,10,100,1000,10000\}\). Building Pascal rows up to \(M\) costs \(O(M^2)\) modular additions. After that, each endpoint evaluation is \(O(n)\), so one call to \(W(n,k)\) is \(O(n^2)\) because it sums over \(n+1\) endpoints. Therefore the full target computation runs in
$$O(M^2 + |K|n^2)$$
time. Memory usage is the total size of the stored Pascal rows, which is far smaller than storing the full triangle because only the queried rows are retained.
Die bereitgestellte C++-Losung entspricht dem folgenden Zahlproblem auf einem Pfadgraphen. Betrachte die Knoten \(0,1,\dots,n\) auf einer Linie. Der Weg startet in \(0\), jeder Schritt andert die Position um genau \(1\), und es gilt stets \(0 \le x \le n\). Der letzte Knoten \(n\) ist ein Hilfsknoten: Er darf beliebig oft besucht werden und wird nicht mitgezahlt. Fur jeden gezahlten Knoten \(0 \le i \lt n\) muss der Weg den Knoten \(i\) genau \(k+i\)-mal besuchen.
Bezeichne mit \(W(n,k)\) die Anzahl aller solchen Wege mit beliebigem Endpunkt \(e \in \{0,1,\dots,n\}\). Das Programm berechnet
$$\Bigl(W(500,1)+W(500,10)+W(500,100)+W(500,1000)+W(500,10000)\Bigr)\bmod 987898789.$$
Die im Code eingebauten Kontrollwerte sind
$$W(3,2)=17,\qquad W(6,1)=1320,\qquad W(6,5)=16793280.$$
Fixiere einen Endpunkt \(e\). Fur jede Kante \(i\) zwischen \(i-1\) und \(i\) (\(1 \le i \le n\)) definieren wir
$$R_i=\#(i-1 \to i),\qquad L_i=\#(i \to i-1).$$
Da der Weg links von jeder Kante startet, ist die Bilanz uber Kante \(i\) einfach
$$R_i-L_i=\mathbf{1}_{e \ge i}.$$
Setze
$$t_i=k+i \qquad (0 \le i \lt n)$$
fur die geforderte Besuchszahl von Knoten \(i\).
Am Startknoten \(0\) ist ein Besuch bereits vorhanden, also
$$1+L_1=t_0=k,$$
und damit
$$R_1=k-\mathbf{1}_{e=0}.$$
Fur jeden inneren gezahlten Knoten \(i\) mit \(1 \le i \lt n\) gilt
$$t_i=R_i+L_{i+1}=k+i,$$
also
$$R_{i+1}=k+i-R_i+\mathbf{1}_{e>i}.$$
Genau diese Rekursion verwendet solve_endpoint. Ist \(e\) gegeben, dann sind alle
Rechtsubergange \(R_i\) eindeutig bestimmt.
Schneidet man den Pfad zwischen \(i-1\) und \(i\) mit \(1 \le i \lt n\), dann erscheint aus Sicht von Knoten \(i-1\) die rechte Seite \(\{i,i+1,\dots,n\}\) als ein Ausflug-Block. Jedes Mal, wenn der Weg von \(i-1\) nach \(i\) geht, startet ein solcher Ausflug in den rechten Suffix.
Insgesamt gibt es uber diesen Schnitt \(R_i\) Rechtsubergange. Der erste davon ist erzwungen; die verbleibenden \(R_i-1\) Ausfluge konnen an beliebige Teilmengen der \(t_{i-1}=k+i-1\) Besuche von Knoten \(i-1\) angehangt werden. Deshalb liefert dieser Schnitt genau
$$\binom{k+i-1}{R_i-1}$$
Moglichkeiten. Fur die letzte Kante \(n\) gibt es keinen zusatzlichen Faktor, weil der Suffix \(\{n\}\) trivial ist: Dort ist die lokale Bewegung nur unmittelbare Ruckkehr oder Endstopp.
Damit folgt fur festen Endpunkt \(e\)
$$\boxed{W(n,k;e)=\prod_{i=1}^{n-1}\binom{k+i-1}{R_i-1}.}$$
Uber alle Endpunkte summiert ergibt sich
$$\boxed{W(n,k)=\sum_{e=0}^{n} W(n,k;e).}$$
Hier sind \(t_0=2\), \(t_1=3\), \(t_2=4\).
Fur \(e=0\): \(R_1=1\), \(R_2=2\), also
$$W(3,2;0)=\binom{2}{0}\binom{3}{1}=3.$$
Fur \(e=1\): \(R_1=2\), \(R_2=1\), also
$$W(3,2;1)=\binom{2}{1}\binom{3}{0}=2.$$
Fur \(e=2\): \(R_1=2\), \(R_2=2\), also
$$W(3,2;2)=\binom{2}{1}\binom{3}{1}=6.$$
Fur \(e=3\) ergibt sich dieselbe Zahl \(6\). Insgesamt also
$$W(3,2)=3+2+6+6=17.$$
Direkte Binomialwerte wurden riesig. Darum baut der Code nur die benotigten Zeilen des Pascal-Dreiecks
modulo \(987898789\) auf. Fur jedes geforderte \(k\) werden nur die Zeilen
\(k,k+1,\dots,k+n-2\) benotigt. build_needed_binomials lauft einmal durch das
Pascal-Dreieck, speichert nur die spater abgefragten Zeilen und macht daraus schnelle Lookup-Tabellen.
build_needed_binomials erzeugt die Pascal-Zeilen modulo \(987898789\).
solve_endpoint fixiert einen Endpunkt, rekonstruiert die erzwungenen
Rechtsubergangszahlen \(R_i\) und multipliziert die passenden Binomialfaktoren.
solve summiert uber alle Endpunkte, und solve_target addiert die funf
geforderten Werte \(W(500,k)\) modulo \(987898789\). Die Brute-Force-Routine dient nur der
Verifikation kleiner Checkpoints.
Mit \(M=\max(K)+n-2\) kostet der Aufbau der Pascal-Zeilen \(O(M^2)\) modulare Additionen. Danach benotigt eine Endpunkt-Auswertung \(O(n)\), also ein voller Aufruf \(W(n,k)\) wegen der Summe uber \(n+1\) Endpunkte \(O(n^2)\). Insgesamt ergibt sich
$$O(M^2 + |K|n^2)$$
Zeit. Der Speicher ist die Gesamtlange der gespeicherten Pascal-Zeilen und damit deutlich kleiner als ein vollstandiges Dreieck.
Verilen C++ cozumu, bir yol grafiği uzerindeki su sayma problemine karsilik geliyor. Dogru uzerinde \(0,1,\dots,n\) dugumleri olsun. Yuruyus \(0\) dugumunde baslar, her adim konumu tam \(1\) degistirir ve her zaman \(0 \le x \le n\) siniri icinde kalinir. Son dugum olan \(n\) yardimci dugumdur: istendigi kadar ziyaret edilebilir ve sayima dahil edilmez. Takip edilen her dugum icin \(0 \le i \lt n\), yuruyusun \(i\) dugumunu tam olarak \(k+i\) kez ziyaret etmesi gerekir.
Bu kosullari saglayan ve \(e \in \{0,1,\dots,n\}\) son noktasinda bitebilen tum yuruyuslerin sayisina \(W(n,k)\) diyelim. Program su degeri hesaplar:
$$\Bigl(W(500,1)+W(500,10)+W(500,100)+W(500,1000)+W(500,10000)\Bigr)\bmod 987898789.$$
Kod icindeki kontrol degerleri de sunlardir:
$$W(3,2)=17,\qquad W(6,1)=1320,\qquad W(6,5)=16793280.$$
Son nokta \(e\) sabit olsun. \(i-1\) ile \(i\) arasindaki her kenar icin (\(1 \le i \le n\))
$$R_i=\#(i-1 \to i),\qquad L_i=\#(i \to i-1)$$
olsun.
Yuruyus her kenarin solundan basladigi icin, kenar \(i\) uzerindeki net fark yalnizca son noktanin bu kenarin saginda olup olmamasina baglidir:
$$R_i-L_i=\mathbf{1}_{e \ge i}.$$
Yani son nokta sabitlenince her kenarin dengesizligi de sabitlenir.
Takip edilen dugumlerin hedef ziyaret sayisini
$$t_i=k+i \qquad (0 \le i \lt n)$$
olarak yazalim.
Dugum \(0\)'da baslangicta zaten bir ziyaret sayilmis durumdadir. Sonraki her ek ziyaret kenar \(1\) uzerinden geri donerek gelir. Dolayisiyla
$$1+L_1=t_0=k,$$
buradan da
$$R_1=k-\mathbf{1}_{e=0}$$
elde edilir.
\(1 \le i \lt n\) icin ic dugum \(i\)'deki her ziyaret ya soldan kenar \(i\) ile ya da sagdan kenar \(i+1\) ile gelir. Bu nedenle
$$t_i=R_i+L_{i+1}=k+i.$$
Ayrica \(R_{i+1}=L_{i+1}+\mathbf{1}_{e \ge i+1}\) oldugundan
$$R_{i+1}=k+i-R_i+\mathbf{1}_{e>i}.$$
Koddaki solve_endpoint fonksiyonu tam olarak bu recurrence'i uygular. Yani \(e\) belli
oldugunda tum sag-gecis sayilari \(R_1,R_2,\dots,R_n\) mecburen belirlenmis olur.
\(1 \le i \lt n\) icin yolu \(i-1\) ile \(i\) arasindan kestigimizi dusunun. O zaman \(\{i,i+1,\dots,n\}\) sag kismi, \(i-1\) dugumunden bakildiginda bir gezi blogu gibi gorunur: yuruyus \(i-1\)'den \(i\)'ye gectigi anda bu sag suffix icine girer, orada dolasir, sonra ya geri doner ya da son kez sagda biter.
Bu kesit uzerinden toplam \(R_i\) tane sola-sag gecis vardir. Ilk gecis zaten zorunludur. Geri kalan \(R_i-1\) geziler ise \(i-1\) dugumunun toplam \(t_{i-1}=k+i-1\) ziyaretinin herhangi bir altkumesine baglanabilir. Bu yuzden bu kesitin katkisi tam olarak
$$\binom{k+i-1}{R_i-1}$$
olur. Son kenar \(n\) icin ayri bir faktor gelmez; cunku \(\{n\}\) suffix'i triviyaldir. Yardimci dugume gidildiginde yerel davranis sadece hemen geri donmek veya son kez orada durmaktir.
Buna gore sabit bir \(e\) son noktasi icin gecerli yuruyus sayisi
$$\boxed{W(n,k;e)=\prod_{i=1}^{n-1}\binom{k+i-1}{R_i-1}.}$$
Tum olasi son noktalar uzerinden toplayinca
$$\boxed{W(n,k)=\sum_{e=0}^{n} W(n,k;e).}$$
Bu durumda hedef ziyaretler \(t_0=2\), \(t_1=3\), \(t_2=4\) olur.
\(e=0\) icin \(R_1=1\), \(R_2=2\):
$$W(3,2;0)=\binom{2}{0}\binom{3}{1}=3.$$
\(e=1\) icin \(R_1=2\), \(R_2=1\):
$$W(3,2;1)=\binom{2}{1}\binom{3}{0}=2.$$
\(e=2\) icin \(R_1=2\), \(R_2=2\):
$$W(3,2;2)=\binom{2}{1}\binom{3}{1}=6.$$
\(e=3\) icin de ayni gecisler geldiginden
$$W(3,2;3)=6.$$
Sonuc olarak
$$W(3,2)=3+2+6+6=17$$
elde edilir; bu da kodun checkpoint'i ile bire bir aynidir.
\(\binom{r}{c}\) degerleri cok hizli buyudugu icin kod bunlari tam sayi olarak kurmaz. Bunun yerine gerekli Pascal ucgeni satirlarini
$$M=987898789$$
moduna gore once hesaplar. Hedef problem icin gereken satirlar, her
\(k \in \{1,10,100,1000,10000\}\) icin \(k,k+1,\dots,k+n-2\) araligidir.
build_needed_binomials Pascal ucgeninden bir kez gecer, yalnizca daha sonra kullanilacak
satirlari saklar ve boylece sonraki endpoint hesaplari sadece carpim ve dizi erisimi haline gelir.
build_needed_binomials gerekli Pascal satirlarini modulo \(987898789\) hazirlar.
solve_endpoint sabit bir \(e\) son noktasi icin zorunlu \(R_i\) dizisini uretir ve
ilgili binom faktorlerini carpar. solve tum son noktalari toplar.
solve_target ise istenen bes \(k\) degeri icin \(W(500,k)\) hesaplayip sonucu mod alir.
Brute-force parcasi yalnizca cok kucuk testlerde dogrulama icin kullanilir.
\(M=\max(K)+n-2\) olsun. Pascal satirlarini kurmak \(O(M^2)\) moduler toplama gerektirir. Bundan sonra tek bir endpoint hesabi \(O(n)\), dolayisiyla tum endpoint'leri toplayan bir \(W(n,k)\) hesabi \(O(n^2)\) olur. Tum hedef calisma su karmasikliktadir:
$$O(M^2 + |K|n^2).$$
Bellek kullanimi, saklanan Pascal satirlarinin toplam uzunlugudur; yani tum ucgeni saklamaktan cok daha kucuktur.
La solucion C++ proporcionada codifica el siguiente problema de conteo de recorridos sobre un grafo camino. Consideremos los vertices \(0,1,\dots,n\) colocados en linea recta. El recorrido empieza en el vertice \(0\), cada paso cambia la posicion exactamente en \(1\), y siempre se mantiene la restriccion \(0 \le x \le n\). El ultimo vertice \(n\) es auxiliar: puede visitarse arbitrariamente muchas veces y no se contabiliza. Para cada vertice rastreado \(0 \le i \lt n\), el recorrido debe visitar \(i\) exactamente \(k+i\) veces.
Sea \(W(n,k)\) el numero de recorridos validos que satisfacen esas condiciones y terminan en cualquier endpoint \(e \in \{0,1,\dots,n\}\). El programa calcula
$$\Bigl(W(500,1)+W(500,10)+W(500,100)+W(500,1000)+W(500,10000)\Bigr)\bmod 987898789.$$
Los valores de control codificados en el archivo son
$$W(3,2)=17,\qquad W(6,1)=1320,\qquad W(6,5)=16793280.$$
Fijemos un endpoint \(e\). Para cada arista \(i\) entre \(i-1\) e \(i\) (\(1 \le i \le n\)), definimos
$$R_i=\#\{\text{cruces } i-1 \to i\},\qquad L_i=\#\{\text{cruces } i \to i-1\}.$$
Como el recorrido empieza a la izquierda de toda arista, el balance neto sobre la arista \(i\) queda determinado por si el endpoint final esta a la derecha de esa arista:
$$R_i-L_i=\mathbf{1}_{e \ge i}.$$
Esta es la observacion estructural esencial: una vez fijado el endpoint, el desequilibrio de cada arista ya no es libre.
Escribamos
$$t_i=k+i\qquad (0 \le i \lt n)$$
para el numero de visitas exigido al vertice rastreado \(i\).
En el vertice \(0\), la caminata ya arranca con una visita contada, y toda visita posterior a \(0\) debe llegar por la arista \(1\). Por tanto
$$1+L_1=t_0=k,\qquad R_1=k-\mathbf{1}_{e=0},$$
Para un vertice interior \(i\) con \(1 \le i \lt n\), cada visita a \(i\) llega o bien desde la izquierda atravesando la arista \(i\), o bien desde la derecha atravesando la arista \(i+1\). En consecuencia,
$$t_i=R_i+L_{i+1}=k+i,\qquad R_{i+1}=k+i-R_i+\mathbf{1}_{e>i}.$$
Asi, una vez fijado \(e\), toda la secuencia de cruces \(R_1,R_2,\dots,R_n\) queda determinada de
manera recursiva. Esto coincide exactamente con la logica de solve_endpoint.
Cortemos ahora el camino entre \(i-1\) e \(i\), con \(1 \le i \lt n\). Desde el punto de vista del vertice \(i-1\), todo lo que queda a la derecha, \(\{i,i+1,\dots,n\}\), funciona como un bloque de excursion: cuando el recorrido cruza de \(i-1\) a \(i\), entra en ese sufijo, deambula dentro de el y luego o bien regresa a \(i-1\) o bien, en la excursion final, termina en el lado derecho.
A traves de ese corte hay en total \(R_i\) excursiones hacia la derecha. La primera de ellas es forzosa. Despues, las \(R_i-1\) excursiones restantes pueden adjuntarse a cualquier subconjunto de las \(t_{i-1}=k+i-1\) visitas al vertice \(i-1\). Por tanto, el numero de elecciones que aporta ese corte es
$$\binom{k+i-1}{R_i-1}.$$
No aparece ningun factor extra para la ultima arista \(n\), porque el sufijo \(\{n\}\) es trivial: al alcanzar el vertice auxiliar, el comportamiento local solo puede ser regresar de inmediato o detenerse alli por ultima vez.
Una vez fijados los numeros de cruces, las elecciones producidas por cortes distintos son independientes dentro de esta descomposicion anidada. Por ello, para un endpoint fijo \(e\), obtenemos
$$W(n,k;e)=\prod_{i=1}^{n-1}\binom{k+i-1}{R_i-1},\qquad W(n,k)=\sum_{e=0}^{n}W(n,k;e).$$
Aqui las visitas exigidas son \(t_0=2\), \(t_1=3\), \(t_2=4\).
Si \(e=0\), entonces \(R_1=1\), \(R_2=2\), y
$$W(3,2;0)=\binom{2}{0}\binom{3}{1}=3.$$
Si \(e=1\), entonces \(R_1=2\), \(R_2=1\), y
$$W(3,2;1)=\binom{2}{1}\binom{3}{0}=2.$$
Si \(e=2\), entonces \(R_1=2\), \(R_2=2\), y
$$W(3,2;2)=\binom{2}{1}\binom{3}{1}=6.$$
Si \(e=3\), aparecen los mismos cruces, asi que
$$W(3,2;3)=6.$$
Por tanto,
$$W(3,2)=3+2+6+6=17,$$
que coincide exactamente con el checkpoint del codigo.
Los valores \(\binom{r}{c}\) crecen muy deprisa, asi que la implementacion no los construye como enteros exactos. En su lugar, genera solo las filas necesarias del triangulo de Pascal modulo
$$M=987898789.$$
Para el calculo objetivo, las filas necesarias son \(k,k+1,\dots,k+n-2\) para
\(k \in \{1,10,100,1000,10000\}\). La funcion build_needed_binomials recorre el triangulo
una sola vez, guarda unicamente las filas que realmente seran consultadas despues, y con ello cada
evaluacion de endpoint se reduce a productos y accesos a tabla modulo \(M\).
build_needed_binomials precomputa las filas de Pascal modulo \(987898789\). Luego
solve_endpoint fija un endpoint \(e\), reconstruye la secuencia forzada de cruces hacia la
derecha \(R_i\) y multiplica los factores binomiales correspondientes. El envoltorio solve
suma esas cantidades sobre todos los endpoints \(e=0,\dots,n\). Finalmente,
solve_target evalua \(W(500,k)\) para los cinco valores pedidos de \(k\) y suma los
resultados modulo \(987898789\).
La rutina bruta solo sirve como mecanismo de verificacion para casos muy pequenos. Explora recursivamente todos los recorridos admisibles para \(n \le 6\), memoiza estados, y confirma que la formula combinatoria cerrada coincide con la enumeracion explicita.
Sea
$$M=\max(K)+n-2,$$
donde \(K=\{1,10,100,1000,10000\}\). Construir las filas de Pascal hasta \(M\) cuesta \(O(M^2)\) sumas modulares. Despues, cada evaluacion de endpoint cuesta \(O(n)\), asi que una llamada completa a \(W(n,k)\) cuesta \(O(n^2)\) porque suma sobre \(n+1\) endpoints. En consecuencia, el calculo total corre en
$$O(M^2 + |K|n^2).$$
El uso de memoria es el tamano total de las filas almacenadas, mucho menor que guardar todo el triangulo completo, porque solo se retienen las filas realmente necesarias.
给定一条路径图，其顶点为 \(0,1,\dots,n\)。行走从顶点 \(0\) 开始，每一步只能向左或向右移动 一个单位，并且始终满足 \(0 \le x \le n\)。最后一个顶点 \(n\) 是辅助顶点，它可以被任意次访问， 但不计入受约束的访问次数。对于每个被跟踪的顶点 \(0 \le i \lt n\)，要求整条路径恰好访问 \(i\) 顶点 \(k+i\) 次。
记满足这些访问条件并且最终停在某个 \(e \in \{0,1,\dots,n\}\) 的合法路径条数为 \(W(n,k)\)。 程序要求计算
$$\Bigl(W(500,1)+W(500,10)+W(500,100)+W(500,1000)+W(500,10000)\Bigr)\bmod 987898789.$$
代码中给出的校验值为
$$W(3,2)=17,\qquad W(6,1)=1320,\qquad W(6,5)=16793280.$$
先固定终点 \(e\)。对于边 \(i\)（连接 \(i-1\) 与 \(i\)，其中 \(1 \le i \le n\)），定义
$$R_i=\#\{\text{从 } i-1 \text{ 到 } i \text{ 的穿越}\},\qquad L_i=\#\{\text{从 } i \text{ 到 } i-1 \text{ 的穿越}\}.$$
由于整条路径对每条边来说都是从左侧出发的，所以边 \(i\) 上的净穿越差只由终点是否落在这条边右侧决定：
$$R_i-L_i=\mathbf{1}_{e \ge i}.$$
这一步很关键：一旦终点固定，每条边的净流量就不再有自由度。
记被跟踪顶点 \(i\) 的目标访问次数为
$$t_i=k+i\qquad (0 \le i \lt n).$$
对顶点 \(0\) 而言，路径一开始就在这里，因此已经自带一次访问；以后每次再回到 \(0\)，都必须通过 边 \(1\) 从右侧返回。所以
$$1+L_1=t_0=k,\qquad R_1=k-\mathbf{1}_{e=0},$$
对于内部被跟踪顶点 \(i\)（\(1 \le i \lt n\)），每次访问 \(i\) 要么来自左侧穿过边 \(i\)，要么来自 右侧穿过边 \(i+1\)。因此
$$t_i=R_i+L_{i+1}=k+i,\qquad R_{i+1}=k+i-R_i+\mathbf{1}_{e>i}.$$
这正是 solve_endpoint 中实现的递推。换句话说，只要终点 \(e\) 已知，全部
\(R_1,R_2,\dots,R_n\) 都会被唯一确定。
现在把路径在 \(i-1\mid i\) 这个切口处切开，其中 \(1 \le i \lt n\)。从顶点 \(i-1\) 的角度看， 右边整段后缀 \(\{i,i+1,\dots,n\}\) 可以视为一个“右侧游程块”：一旦路径从 \(i-1\) 穿到 \(i\)， 它就进入右侧后缀，在其中活动，之后要么返回 \(i-1\)，要么在最后一次游程中停在右侧结束。
在这个切口上，总共有 \(R_i\) 次从左到右的游程。第一趟向右进入是被问题结构强制的。之后剩余的 \(R_i-1\) 趟游程，可以附着在顶点 \(i-1\) 的 \(t_{i-1}=k+i-1\) 次访问中的任意若干次上。因此这个切口贡献的组合数正好是
$$\binom{k+i-1}{R_i-1}.$$
最后一条边 \(n\) 不会再额外产生一个因子，因为后缀 \(\{n\}\) 已经是平凡的：一旦到达辅助顶点， 局部行为只有“立刻返回”或者“最后停下”两种。
当所有穿越次数都固定后，不同切口所带来的选择在这套嵌套分解下彼此独立。因此，对固定终点 \(e\)， 合法路径总数为
$$W(n,k;e)=\prod_{i=1}^{n-1}\binom{k+i-1}{R_i-1},\qquad W(n,k)=\sum_{e=0}^{n}W(n,k;e).$$
此时要求的访问次数是 \(t_0=2\), \(t_1=3\), \(t_2=4\)。
若 \(e=0\)，则 \(R_1=1\), \(R_2=2\)，因此
$$W(3,2;0)=\binom{2}{0}\binom{3}{1}=3.$$
若 \(e=1\)，则 \(R_1=2\), \(R_2=1\)，因此
$$W(3,2;1)=\binom{2}{1}\binom{3}{0}=2.$$
若 \(e=2\)，则 \(R_1=2\), \(R_2=2\)，因此
$$W(3,2;2)=\binom{2}{1}\binom{3}{1}=6.$$
若 \(e=3\)，穿越次数相同，所以
$$W(3,2;3)=6.$$
于是
$$W(3,2)=3+2+6+6=17,$$
与程序中的 checkpoint 完全一致。
\(\binom{r}{c}\) 的实际数值会非常巨大，所以实现并不直接构造精确整数，而是只在模
$$M=987898789$$
下生成需要的 Pascal 三角形行。对于目标计算，需要的行恰好是
\(k,k+1,\dots,k+n-2\)，其中 \(k \in \{1,10,100,1000,10000\}\)。
build_needed_binomials 只遍历一次 Pascal 三角形，并且只保存以后真的会被查询到的那些
行。这样每个终点的计算就只剩下查表与取模乘法。
build_needed_binomials 先在模 \(987898789\) 下预计算所需的 Pascal 三角形行。
然后 solve_endpoint 固定终点 \(e\)，重建被强制出来的右向穿越序列 \(R_i\)，并把对应的
二项式系数依次相乘。外层的 solve 会把所有 \(e=0,\dots,n\) 的结果相加。
最后 solve_target 计算五个指定 \(k\) 值下的 \(W(500,k)\)，并取模求和。
暴力搜索函数只用于很小规模的交叉校验。它对 \(n \le 6\) 的情形显式枚举所有可行路径，利用记忆化 缓存状态，并验证闭式组合计数与显式枚举完全一致。
设
$$M=\max(K)+n-2,$$
其中 \(K=\{1,10,100,1000,10000\}\)。构造到第 \(M\) 行的 Pascal 预处理需要 \(O(M^2)\) 次模加法。 在此之后，每个终点计算花费 \(O(n)\)，因此一次完整的 \(W(n,k)\) 调用需要 \(O(n^2)\)，因为它要 对 \(n+1\) 个终点求和。所以总目标计算复杂度为
$$O(M^2 + |K|n^2).$$
内存使用量等于保存下来的 Pascal 行总长度。由于只保留真正会访问的行，因此远小于保存整个三角形。
Предоставленное решение на C++ кодирует следующую задачу подсчета маршрутов на графе-пути. Рассмотрим вершины \(0,1,\dots,n\), расположенные на одной линии. Маршрут начинается в вершине \(0\), каждый шаг меняет положение ровно на \(1\), и всегда выполняется ограничение \(0 \le x \le n\). Последняя вершина \(n\) является вспомогательной: ее можно посещать сколько угодно раз, и она не входит в систему обязательных подсчетов. Для каждой отслеживаемой вершины \(0 \le i \lt n\) требуется, чтобы маршрут посетил вершину \(i\) ровно \(k+i\) раз.
Обозначим через \(W(n,k)\) число допустимых маршрутов, удовлетворяющих этим условиям и заканчивающихся в любой вершине \(e \in \{0,1,\dots,n\}\). Программа вычисляет
$$\Bigl(W(500,1)+W(500,10)+W(500,100)+W(500,1000)+W(500,10000)\Bigr)\bmod 987898789.$$
Проверочные значения, зашитые в код, таковы:
$$W(3,2)=17,\qquad W(6,1)=1320,\qquad W(6,5)=16793280.$$
Для фиксированного конца \(e\) на каждом ребре \(i\) между \(i-1\) и \(i\) (\(1 \le i \le n\)) введем
$$R_i=\#\{\text{переходов } i-1 \to i\},\qquad L_i=\#\{\text{переходов } i \to i-1\}.$$
Поскольку маршрут стартует слева от любого ребра, чистый баланс на ребре \(i\) определяется только тем, находится ли конечная точка правее этого ребра:
$$R_i-L_i=\mathbf{1}_{e \ge i}.$$
Это главный структурный факт: после фиксации конца \(e\) дисбаланс на каждом ребре уже не является свободным параметром.
Положим
$$t_i=k+i\qquad (0 \le i \lt n)$$
для требуемого числа посещений отслеживаемой вершины \(i\).
В вершине \(0\) маршрут уже начинается, то есть одна посещенная точка есть сразу. Любое следующее посещение \(0\) должно прийти через ребро \(1\). Поэтому
$$1+L_1=t_0=k,\qquad R_1=k-\mathbf{1}_{e=0},$$
Для внутренней отслеживаемой вершины \(i\), где \(1 \le i \lt n\), каждое посещение приходит либо слева через ребро \(i\), либо справа через ребро \(i+1\). Значит,
$$t_i=R_i+L_{i+1}=k+i,\qquad R_{i+1}=k+i-R_i+\mathbf{1}_{e>i}.$$
Именно эта рекурсия реализована в solve_endpoint. Следовательно, после фиксации \(e\)
вся последовательность \(R_1,R_2,\dots,R_n\) определяется однозначно.
Разрежем путь между \(i-1\) и \(i\), где \(1 \le i \lt n\). С точки зрения вершины \(i-1\) вся правая часть \(\{i,i+1,\dots,n\}\) ведет себя как блок экскурсии: как только маршрут переходит из \(i-1\) в \(i\), он уходит в правый суффикс, движется внутри него, а потом либо возвращается назад в \(i-1\), либо в последней экскурсии заканчивается справа.
Через этот разрез совершается всего \(R_i\) выходов слева направо. Первый такой выход обязателен. Оставшиеся \(R_i-1\) экскурсии можно прикрепить к произвольному подмножеству из \(t_{i-1}=k+i-1\) посещений вершины \(i-1\). Поэтому вклад данного разреза равен
$$\binom{k+i-1}{R_i-1}.$$
Для последнего ребра \(n\) дополнительный множитель не возникает, потому что суффикс \(\{n\}\) тривиален: достигнув вспомогательной вершины, маршрут может либо сразу вернуться, либо завершиться там.
Когда числа пересечений уже зафиксированы, выборы, возникающие на разных разрезах, становятся независимыми внутри этой вложенной декомпозиции. Поэтому для фиксированного конца \(e\) получаем
$$W(n,k;e)=\prod_{i=1}^{n-1}\binom{k+i-1}{R_i-1},\qquad W(n,k)=\sum_{e=0}^{n}W(n,k;e).$$
Здесь требуемые числа посещений равны \(t_0=2\), \(t_1=3\), \(t_2=4\).
Если \(e=0\), то \(R_1=1\), \(R_2=2\), и
$$W(3,2;0)=\binom{2}{0}\binom{3}{1}=3.$$
Если \(e=1\), то \(R_1=2\), \(R_2=1\), и
$$W(3,2;1)=\binom{2}{1}\binom{3}{0}=2.$$
Если \(e=2\), то \(R_1=2\), \(R_2=2\), и
$$W(3,2;2)=\binom{2}{1}\binom{3}{1}=6.$$
Если \(e=3\), получаются те же пересечения, значит
$$W(3,2;3)=6.$$
Итак,
$$W(3,2)=3+2+6+6=17,$$
что в точности совпадает с контрольным значением из программы.
Значения \(\binom{r}{c}\) быстро становятся огромными, поэтому реализация не строит их как точные целые числа. Вместо этого она формирует только нужные строки треугольника Паскаля по модулю
$$M=987898789.$$
Для целевого вычисления требуются строки \(k,k+1,\dots,k+n-2\) для
\(k \in \{1,10,100,1000,10000\}\). Функция build_needed_binomials один раз проходит по
треугольнику Паскаля, сохраняет только те строки, которые потом действительно будут запрошены, и
после этого каждая проверка конечной вершины сводится к перемножению табличных значений по модулю
\(M\).
build_needed_binomials заранее вычисляет нужные строки Паскаля по модулю \(987898789\).
Затем solve_endpoint фиксирует конец \(e\), восстанавливает вынужденную последовательность
правых пересечений \(R_i\) и перемножает соответствующие биномиальные множители. Обертка
solve суммирует результат по всем \(e=0,\dots,n\). Наконец, solve_target
вычисляет \(W(500,k)\) для пяти требуемых значений \(k\) и складывает их по модулю \(987898789\).
Полный перебор нужен только как механизм проверки на очень маленьких примерах. Он рекурсивно перечисляет все допустимые маршруты при \(n \le 6\), кэширует состояния и подтверждает, что замкнутая комбинаторная формула дает тот же результат, что и явное перечисление.
Пусть
$$M=\max(K)+n-2,$$
где \(K=\{1,10,100,1000,10000\}\). Построение строк Паскаля до уровня \(M\) требует \(O(M^2)\) модульных сложений. После этого одна проверка конечной вершины занимает \(O(n)\), а полный вызов \(W(n,k)\) стоит \(O(n^2)\), поскольку суммируется по \(n+1\) возможным концам. Следовательно, итоговое вычисление имеет сложность
$$O(M^2 + |K|n^2).$$
Память равна суммарной длине сохраненных строк Паскаля. Это намного меньше, чем хранить весь треугольник целиком, поскольку удерживаются только реально нужные строки.
يمثل الحل C++ المعطى المسألة التالية الخاصة بعدّ المسارات على مخطط مسار. لننظر إلى العقد \(0,1,\dots,n\) على خط مستقيم. يبدأ المسار من العقدة \(0\)، وكل خطوة تغير الموضع بمقدار \(1\) تماما، مع بقاء الشرط \(0 \le x \le n\) محققا دائما. العقدة الاخيرة \(n\) عقدة مساعدة: يمكن زيارتها عددا غير محدود من المرات، لكنها لا تدخل ضمن عدادات الزيارات المطلوبة. اما كل عقدة متتبعة \(0 \le i \lt n\) فيجب ان تُزار بالضبط \(k+i\) مرة.
لنرمز بعدد المسارات الصالحة التي تحقق هذه الشروط وتنتهي عند نقطة \(e \in \{0,1,\dots,n\}\) بالرمز \(W(n,k)\). البرنامج يحسب
$$\Bigl(W(500,1)+W(500,10)+W(500,100)+W(500,1000)+W(500,10000)\Bigr)\bmod 987898789.$$
وقيم التحقق المضمنة في الملف هي
$$W(3,2)=17,\qquad W(6,1)=1320,\qquad W(6,5)=16793280.$$
بعد تثبيت نقطة النهاية \(e\)، نعرف على كل حافة \(i\) بين \(i-1\) و\(i\) حيث \(1 \le i \le n\)
$$R_i=\#\{\text{عبورات } i-1 \to i\},\qquad L_i=\#\{\text{عبورات } i \to i-1\}.$$
وبما ان المسار يبدأ إلى يسار كل حافة، فإن الصافي عبر الحافة \(i\) يتحدد فقط بحسب ما إذا كانت نقطة النهاية تقع إلى يمين تلك الحافة:
$$R_i-L_i=\mathbf{1}_{e \ge i}.$$
هذه هي الملاحظة البنيوية الاساسية: بعد تثبيت \(e\)، لا يبقى اختلال كل حافة متغيرا حرا.
لنكتب
$$t_i=k+i\qquad (0 \le i \lt n)$$
لعدد الزيارات المطلوبة للعقدة المتتبعة \(i\).
في العقدة \(0\)، توجد زيارة واحدة محسوبة مسبقا لأن المسار يبدأ هناك، وكل زيارة لاحقة إلى \(0\) يجب أن تأتي عبر الحافة \(1\). لذلك
$$1+L_1=t_0=k,\qquad R_1=k-\mathbf{1}_{e=0},$$
ولكل عقدة داخلية متتبعة \(i\) حيث \(1 \le i \lt n\)، فإن كل زيارة إلى \(i\) تصل إما من اليسار عبر الحافة \(i\)، أو من اليمين عبر الحافة \(i+1\). ومن ثم
$$t_i=R_i+L_{i+1}=k+i,\qquad R_{i+1}=k+i-R_i+\mathbf{1}_{e>i}.$$
وهذه بالضبط هي العلاقة التراجعية التي تطبقها الدالة solve_endpoint. أي أنه بمجرد
معرفة \(e\)، تصبح جميع القيم \(R_1,R_2,\dots,R_n\) محددة على نحو وحيد.
لنقطع المسار بين \(i-1\) و\(i\)، حيث \(1 \le i \lt n\). من وجهة نظر العقدة \(i-1\)، فإن الجزء الواقع إلى اليمين \(\{i,i+1,\dots,n\}\) يتصرف كأنه كتلة رحلة: فعندما يعبر المسار من \(i-1\) إلى \(i\)، يدخل هذا الذيل الأيمن، ويتحرك داخله، ثم إما يعود لاحقا إلى \(i-1\)، أو ينتهي في الرحلة الاخيرة على الجهة اليمنى.
عبر هذا القطع، يوجد في المجموع \(R_i\) رحلة من اليسار إلى اليمين. الرحلة الاولى مفروضة. بعد ذلك، يمكن إسناد الرحلات الباقية وعددها \(R_i-1\) إلى اي مجموعة جزئية من زيارات العقدة \(i-1\) وعددها \(t_{i-1}=k+i-1\). ومن هنا يكون عدد الخيارات الناتج عن هذا القطع هو
$$\binom{k+i-1}{R_i-1}.$$
ولا يظهر عامل إضافي عند الحافة الاخيرة \(n\)، لأن الذيل \(\{n\}\) تافه: فما إن يصل المسار إلى العقدة المساعدة، حتى لا يبقى محليا إلا احتمال الرجوع مباشرة أو التوقف النهائي هناك.
بعد تثبيت أعداد العبور، تصبح الخيارات القادمة من القطوع المختلفة مستقلة داخل هذا التفكيك المتداخل. لذلك نحصل، عند نقطة نهاية ثابتة \(e\)، على
$$W(n,k;e)=\prod_{i=1}^{n-1}\binom{k+i-1}{R_i-1},\qquad W(n,k)=\sum_{e=0}^{n}W(n,k;e).$$
في هذه الحالة تكون الزيارات المطلوبة هي \(t_0=2\)، \(t_1=3\)، \(t_2=4\).
إذا كان \(e=0\)، فإن \(R_1=1\)، \(R_2=2\)، وبالتالي
$$W(3,2;0)=\binom{2}{0}\binom{3}{1}=3.$$
إذا كان \(e=1\)، فإن \(R_1=2\)، \(R_2=1\)، وبالتالي
$$W(3,2;1)=\binom{2}{1}\binom{3}{0}=2.$$
إذا كان \(e=2\)، فإن \(R_1=2\)، \(R_2=2\)، وبالتالي
$$W(3,2;2)=\binom{2}{1}\binom{3}{1}=6.$$
إذا كان \(e=3\)، نحصل على القيم نفسها، ومن ثم
$$W(3,2;3)=6.$$
إذن
$$W(3,2)=3+2+6+6=17,$$
وهو ما يطابق تماما قيمة التحقق الموجودة في الكود.
القيم \(\binom{r}{c}\) تكبر بسرعة كبيرة، لذلك لا تبنيها الخوارزمية كأعداد صحيحة كاملة. بدلا من ذلك، تولد فقط صفوف مثلث باسكال اللازمة بترديد
$$M=987898789.$$
وبالنسبة إلى الحساب الهدف، فإن الصفوف المطلوبة هي \(k,k+1,\dots,k+n-2\) لكل
\(k \in \{1,10,100,1000,10000\}\). تقوم الدالة build_needed_binomials بالمرور على
مثلث باسكال مرة واحدة، وتحفظ فقط الصفوف التي سيجري الاستعلام عنها لاحقا، وبذلك يصبح حساب كل
نقطة نهاية مجرد ضربات معيارية مع قراءات من جدول.
تقوم build_needed_binomials بتهيئة صفوف باسكال المطلوبة بترديد \(987898789\). ثم تقوم
solve_endpoint بتثبيت نقطة نهاية \(e\)، وإعادة بناء السلسلة المفروضة من عبورات اليمين
\(R_i\)، وضرب معاملات ثنائية الحدين الموافقة. بعد ذلك تجمع solve النتائج على جميع
النهايات \(e=0,\dots,n\). وأخيرا تحسب solve_target القيم الخمس
\(W(500,k)\) المطلوبة وتجمعها بترديد \(987898789\).
أما الجزء الشامل فيستعمل فقط كآلية تحقق للحالات الصغيرة جدا. فهو يستكشف جميع المسارات المسموح بها صراحة عندما \(n \le 6\)، ويستخدم الحفظ، ثم يؤكد أن الصيغة التوافقية المغلقة تطابق العد الصريح تماما.
لنضع
$$M=\max(K)+n-2,$$
حيث \(K=\{1,10,100,1000,10000\}\). إن بناء صفوف باسكال حتى المستوى \(M\) يكلف \(O(M^2)\) من عمليات الجمع المعيارية. وبعد ذلك، فإن تقييم نقطة نهاية واحدة يكلف \(O(n)\)، ولذلك فإن استدعاء واحدا كاملا لـ \(W(n,k)\) يكلف \(O(n^2)\) لأنه يجمع على \(n+1\) نقطة نهاية. ومن ثم فإن الحساب الهدف كله يعمل بزمن
$$O(M^2 + |K|n^2).$$
أما الذاكرة فتساوي الحجم الكلي لصفوف باسكال المخزنة، وهي أقل بكثير من تخزين المثلث كاملا، لأن التنفيذ يحتفظ فقط بالصفوف التي يحتاجها فعلا.