guest@itl:~/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
Log in to track progress, save custom versions, and organize into collections.Log In
$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;
}
28 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 (nr)\binom{n}{r} iteratively without mod. Uses symmetry (r→n−rr \to n-r when smaller) to minimize iterations

    • - Returns 1 for (n0)\binom{n}{0}, (nn)\binom{n}{n}, and (00)\binom{0}{0}
    - Returns 0 for r<0r < 0 or r>nr > n
  • nPr(n, r) — computes P(n,r)=n⋅(n−1)⋯(n−r+1)P(n, r) = n \cdot (n-1) \cdots (n-r+1)

  • factorialPrimePower(n, p) — Legendre's formula: times prime pp divides n!n!

    • νp(n!)=∑k=1∞⌊npk⌋\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≤60n \le 60). For large nn with mod, use the Binomial Coefficients template instead

  • factorialPrimePower — trailing zeros of n!n! (use p=5p = 5), divisibility of n!n! by pkp^k

    • Complexity

  • nCr — O(min⁡(r,n−r))O(\min(r, n-r))

  • nPr — O(r)O(r)

  • factorialPrimePower — O(log⁡pn)O(\log_p n)