CP-Base

⌘K

online

guest@cp-base:~/home/combinatorics$

templates/combinatorics-counting.cpp

compilable

$cat templates/combinatorics-counting

Combinatorics Counting

Non-modular nCr, nPr, and Legendre's formula for prime power in factorials.

[Combinatorics]|

Jul 9, 2026

|explanatory_notes.md|

#nCr#nPr#factorial#legendre#combinatorics

$cat source_code/

cpp

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

ll nCr(ll n, ll r) {
    if (r < 0 || r > n) return 0;
    if (r == 0 || r == n) return 1;
    if (n - r < r) r = n - r;
    ll res = 1;
    for (ll i = 0; i < r; i++) {
        res *= (n - i);
        res /= (i + 1);
    }
    return res;
}

ll nPr(ll n, ll r) {
    if (r < 0 || r > n) return 0;
    ll res = 1;
    for (ll i = 0; i < r; i++)
        res *= (n - i);
    return res;
}

ll factorialPrimePower(ll n, ll p) {
    ll cnt = 0;
    for (ll pk = p; pk <= n; pk *= p)
        cnt += n / pk;
    return cnt;
}

30 linesutf-8

$cat explanation_notes.md

notes_viewer --renderedmarkdown (math enabled)

Combinatorics Counting

Non-modular combinatorial functions for small values.

Functions

nCr(n, r) — computes

\binom{n}{r}

iteratively without mod. Uses symmetry (

r \to n-r

when smaller) to minimize iterations

- Returns 1 for

\binom{n}{0}

\binom{n}{n}

, and

\binom{0}{0}

- Returns 0 for

r < 0

r > n

nPr(n, r) — computes

P(n, r) = n \cdot (n-1) \cdots (n-r+1)

factorialPrimePower(n, p) — Legendre's formula: times prime

p

divides

n!

\nu_p(n!) = \sum_{k=1}^{\infty} \left\lfloor \frac{n}{p^k} \right\rfloor

When to Use

nCr/nPr — when result fits in ll (roughly

n \le 60

). For large

n

with mod, use the Binomial Coefficients template instead

factorialPrimePower — trailing zeros of

n!

(use

p = 5

), divisibility of

n!

p^k

Complexity

nCr —

O(\min(r, n-r))

nPr —

O(r)

factorialPrimePower —

O(\log_p n)