Lucas Theorem / Large Binomial Mod Prime Ladder

Who This Is For

Use this ladder when ordinary factorial / inverse-factorial binomial code feels familiar, but you still hesitate when a query crosses n >= p.

Warm-Up

• modular inverse under a prime modulus
• factorial / inverse-factorial binomial precompute
• base conversion and digit decomposition

Core

• detect the boundary max_n < p versus n >= p
• apply Lucas theorem digit by digit
• keep one prime-mod binomial helper for the digit layer

Stretch

• special-case parity and other tiny-prime patterns
• explain why composite moduli are outside the first Lucas lane
• compare the lightweight factorial-table route against Lucas on the same judge

Retrieval Layer

• exact starter -> lucas-binomial.cpp
• quick reminder sheet -> Lucas Theorem hot sheet
• compare point -> factorial-binomial-mod.cpp

Repo Anchors

• Binomial Coefficient (Prime Mod)

Exit Criteria

You are ready to move on when you can:

• tell immediately whether one factorial table is enough
• explain Lucas as a base-p digit product instead of a memorized formula
• stop early when one digit forces the answer to zero
• explain why composite-mod binomial problems are a different lane

External Practice

• Library Checker - Binomial Coefficient (Prime Mod)
• Kattis - Odd Binomial Coefficients

Tutorial Link

• Lucas Theorem / Large Binomial Mod Prime