Detailed mathematical approach

Problem Summary

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.$

Mathematical Approach

1. Fix the Endpoint and Count Edge Crossings

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.

2. Visit Equations Force a Simple Recurrence

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.

3. Why a Binomial Coefficient Appears

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.

4. Product Formula for a Fixed Endpoint

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).}$

5. Worked Checkpoint: \(W(3,2)=17\)

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.

6. Modular Binomials via Pascal's Triangle

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\).

How the Code Works

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.

Complexity Analysis

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.

Further Reading

1. Problem page: https://projecteuler.net/problem=992
2. Binomial coefficients and Pascal's triangle: Wikipedia - Binomial coefficient
3. A standard reference for path decompositions and combinatorial identities is Graham, Knuth, Patashnik, Concrete Mathematics, 2nd ed., Addison-Wesley.