Problem Analysis
The problem asks how many monotone lattice paths exist from the top-left corner to the bottom-right corner of an n x n grid, where each step can only move right or down. The crucial observation is that the geometry of the grid is irrelevant to the count: any valid path consists of exactly 2n unit steps, of which n must go right and n must go down. A path is fully determined by the order in which we interleave these two kinds of moves. Counting paths therefore reduces to counting the ways to choose which n of the 2n positions in the move sequence are "right" moves (the remaining n are automatically "down" moves). That count is precisely the binomial coefficient C(2n, n) = (2n)! / (n! * n!), known here as the central binomial coefficient. For n = 20 the answer is C(40, 20) = 137,846,528,820, which fits in a signed 64-bit integer; for the extra test case n = 200 the answer is a 120-digit number, which forces us to use arbitrary-precision ("big integer") arithmetic.
This reframing - from "simulate or enumerate paths" to "evaluate one closed-form expression" - is what makes the problem trivial. There is no need for dynamic programming over the grid, no recursion, no path-counting table. The remaining concern is purely arithmetic: how to compute the central binomial coefficient without producing absurdly large intermediate values. Computing (2n)! and (n!)^2 separately works but creates enormous factorials. A better route is the incremental product form C(2n, n) = product over i from 1 to n of (n + i) / i, which interleaves multiplication and division to keep partial values small. Either way the cost is O(n) arithmetic operations on integers whose size grows as O(n log n) bits, giving an overall bit-complexity of about O(n^2 log n) - entirely negligible for the sizes here.
Solution Approach
Central Binomial Coefficient (Python and C)
Both the Python and C solutions compute the same quantity, the central binomial coefficient C(2n, n), and differ only in how they manage arbitrary-precision arithmetic.
Python (p0015_s0.py): I wrote the answer in a single line,
math.factorial(2 * lattice_size) // math.factorial(lattice_size) ** 2.
Python integers are
arbitrary-precision
by default, so there is no overflow to worry about and no custom arithmetic to implement. I used
floor division (//) rather than true division (/) because the
binomial coefficient
is always an exact integer and I want to avoid floating-point rounding entirely.
math.factorial is implemented in C inside the interpreter, so even for n = 200 this is
effectively instantaneous. This is the simplest correct solution available in the language.
C (p0015_s0.c): C has no native big integers, so I implemented a minimal
arbitrary-precision
integer type and used the product form rather than factorials. The BigInt struct
stores the number as an array of base-10^9 "limbs" in
little-endian
order (index 0 holds the least significant chunk). I chose base 10^9 because a limb fits inside a
32-bit value, yet I store each limb in a 64-bit unsigned long long, leaving ample
headroom for the intermediate product limb * multiplier + carry in a multiply step
- the multiplier is at most 2n = 400, far below the 64-bit overflow threshold.
The solve function initialises the result to 1 with bi_set, then loops
i from 1 to n, calling bi_mul_ll(&result, n + i) followed by
bi_div_ll(&result, i). The ordering is deliberate: the running value after step k
equals C(n + k, k), which is always an integer, so each division by i is exact and never discards a
remainder. bi_mul_ll propagates a carry upward through the limbs (natural for
little-endian
storage), and bi_div_ll sweeps from the top limb downward, carrying a remainder into
lower limbs - the standard
long division
direction. Finally bi_to_str prints the most significant limb with no leading zeros
and every subsequent limb as exactly nine zero-padded decimal digits, which reconstructs the full
decimal number directly from the base-10^9 representation.