1404. A Row of Pascal When the Modulus Is Not Prime

Print the n-th row of Pascal's triangle, every entry reduced modulo m. The row has n + 1 entries, C(n, 0) through C(n, n).

`m` is not guaranteed to be prime. That single sentence is the whole problem.

n = 4, m = 1000000000 -> 1 4 6 4 1 n = 0, m = 2 -> 1 n = 10, m = 12 -> 1 10 9 0 6 0 6 0 9 10 1

## What most people try first

Factorials and a modular inverse, the method of problems 1326 and 1401: C(n, k) = n! * inv(k!) * inv((n-k)!) mod m. It is the natural reflex and it is wrong here. Fermat's little theorem needs m prime. Extended Euclid is more general but needs gcd(k!, m) = 1, and with m = 12 and k = 2 the denominator 2 shares the factor 2 with m, so 2 has no inverse modulo 12 at all: there is no x with 2x = 1 mod 12, because 2x is always even. The method does not merely lose precision, the quantity it asks for does not exist.

Problem 233 prints a row of Pascal's triangle without any modulus, which is a different problem: there the values themselves are the output and the limit on n is tiny for that reason.

## Addition needs no inverse

Pascal's recurrence is C(i, j) = C(i-1, j-1) + C(i-1, j), with C(i, 0) and C(i, i) both 1. Addition is well defined modulo any m whatsoever, prime or not, so build the triangle row by row and reduce as you go:

row = [1 mod m] for i = 1 .. n: next[0] = next[i] = 1 mod m for j = 1 .. i-1: next[j] = (row[j-1] + row[j]) mod m row = next

Only the previous row is ever needed, so two arrays of n + 1 entries suffice rather than the whole triangle.

## Why it is correct

The recurrence is an identity over the integers, and reduction modulo m is a ring homomorphism: if C(i, j) = C(i-1, j-1) + C(i-1, j) holds over the integers then the same equation holds between their residues. So carrying the residues forward computes exactly the residues of the true binomials, by induction on i, with the base case C(0, 0) = 1. No division appears anywhere, so no inverse is needed and no primality is assumed.

The 1 mod m rather than a bare 1 matters only for m = 1, which the constraints exclude, but writing it costs nothing and the habit is worth keeping.

## Overflow

This is the one problem in this group with no overflow trap, and it is worth knowing why rather than guessing. Every entry is already reduced, so it is at most m - 1, at most 999999999. The only arithmetic is the sum of two such entries, at most 1999999998, and a signed 32-bit integer holds up to 2147483647. So 2 * 10^9 fits, the sum fits, and a 32-bit build answers this problem correctly. Had the step been a multiplication of two entries instead, the product would be near 10^18 and 32 bits would fail immediately. In JavaScript the sum is far below 2^53, so a plain Number is exact and BigInt is unnecessary.

## Cost

O(n^2) additions and O(n) memory.

Constraints - `0 ≤ n ≤ 2000` - `2 ≤ m ≤ 1000000000` - `m` is not necessarily prime