Lucas's Theorem
(math/lucas.hpp)

• View this file on GitHub
• Last update: 2026-06-23 12:24:42+09:00
• Include: #include "math/lucas.hpp"

Overview

Lucas<Mint> computes binomial coefficients modulo a prime even when n and k are much larger than the modulus.

Write the arguments in base p:

n = n0 + n1 p + n2 p^2 + ...
k = k0 + k1 p + k2 p^2 + ...

Lucas’s theorem states

C(n, k) = product C(ni, ki) modulo p.

The class precomputes factorials and inverse factorials for every value below p. Construction therefore costs O(p) time and memory, while each query takes O(log_p n).

LucasTheorem<Mint> is an alias for Lucas<Mint>.

Requirements

Mint must provide the static-modulus interface used by ModInt, and its modulus must be prime.

This implementation is intended for small or moderate primes because it stores 2p modular values. It is not appropriate for moduli such as 998244353 or 1000000007.

Methods

Method	Description	Complexity
Lucas()	Precomputes factorial tables below the modulus.	O(p)
uint32_t prime() const	Returns the modulus.	O(1)
Mint binom(uint64_t n, uint64_t k) const	Returns C(n, k) modulo p; returns zero when k > n.	O(log_p n)
Mint operator()(uint64_t n, uint64_t k) const	Alias for binom.	O(log_p n)

Example

#include "math/lucas.hpp"
#include "math/modint.hpp"
#include <iostream>

int main() {
    using Mint = m1une::math::ModInt<7>;
    m1une::math::Lucas<Mint> lucas;

    std::cout << lucas.binom(1000000000000000000ULL, 123456789ULL) << '\n';
    std::cout << lucas(100, 20) << '\n';
}

Required by

• Math All (math/all.hpp)

Verified with

• verify/math/lucas.test.cpp
• verify/math/math_algorithms.test.cpp

Code

#ifndef M1UNE_MATH_LUCAS_HPP
#define M1UNE_MATH_LUCAS_HPP 1

#include <cassert>
#include <cstdint>
#include <vector>

namespace m1une {
namespace math {

template <class Mint>
struct Lucas {
   private:
    std::vector<Mint> _factorial;
    std::vector<Mint> _inverse_factorial;

    Mint small_binom(uint32_t n, uint32_t k) const {
        if (k > n) return Mint(0);
        return _factorial[n] * _inverse_factorial[k] * _inverse_factorial[n - k];
    }

   public:
    Lucas() {
        const uint32_t prime = Mint::mod();
        assert(2 <= prime);
        _factorial.resize(prime);
        _inverse_factorial.resize(prime);
        _factorial[0] = Mint(1);
        for (uint32_t i = 1; i < prime; i++) {
            _factorial[i] = _factorial[i - 1] * Mint(i);
        }
        _inverse_factorial[prime - 1] = _factorial[prime - 1].inv();
        for (uint32_t i = prime - 1; i > 0; i--) {
            _inverse_factorial[i - 1] = _inverse_factorial[i] * Mint(i);
        }
    }

    uint32_t prime() const {
        return Mint::mod();
    }

    Mint binom(uint64_t n, uint64_t k) const {
        if (k > n) return Mint(0);
        const uint64_t modulus = Mint::mod();
        Mint result = Mint(1);
        while (n > 0 || k > 0) {
            uint32_t n_digit = uint32_t(n % modulus);
            uint32_t k_digit = uint32_t(k % modulus);
            if (k_digit > n_digit) return Mint(0);
            result *= small_binom(n_digit, k_digit);
            n /= modulus;
            k /= modulus;
        }
        return result;
    }

    Mint operator()(uint64_t n, uint64_t k) const {
        return binom(n, k);
    }
};

template <class Mint>
using LucasTheorem = Lucas<Mint>;

}  // namespace math
}  // namespace m1une

#endif  // M1UNE_MATH_LUCAS_HPP

#line 1 "math/lucas.hpp"



#include <cassert>
#include <cstdint>
#include <vector>

namespace m1une {
namespace math {

template <class Mint>
struct Lucas {
   private:
    std::vector<Mint> _factorial;
    std::vector<Mint> _inverse_factorial;

    Mint small_binom(uint32_t n, uint32_t k) const {
        if (k > n) return Mint(0);
        return _factorial[n] * _inverse_factorial[k] * _inverse_factorial[n - k];
    }

   public:
    Lucas() {
        const uint32_t prime = Mint::mod();
        assert(2 <= prime);
        _factorial.resize(prime);
        _inverse_factorial.resize(prime);
        _factorial[0] = Mint(1);
        for (uint32_t i = 1; i < prime; i++) {
            _factorial[i] = _factorial[i - 1] * Mint(i);
        }
        _inverse_factorial[prime - 1] = _factorial[prime - 1].inv();
        for (uint32_t i = prime - 1; i > 0; i--) {
            _inverse_factorial[i - 1] = _inverse_factorial[i] * Mint(i);
        }
    }

    uint32_t prime() const {
        return Mint::mod();
    }

    Mint binom(uint64_t n, uint64_t k) const {
        if (k > n) return Mint(0);
        const uint64_t modulus = Mint::mod();
        Mint result = Mint(1);
        while (n > 0 || k > 0) {
            uint32_t n_digit = uint32_t(n % modulus);
            uint32_t k_digit = uint32_t(k % modulus);
            if (k_digit > n_digit) return Mint(0);
            result *= small_binom(n_digit, k_digit);
            n /= modulus;
            k /= modulus;
        }
        return result;
    }

    Mint operator()(uint64_t n, uint64_t k) const {
        return binom(n, k);
    }
};

template <class Mint>
using LucasTheorem = Lucas<Mint>;

}  // namespace math
}  // namespace m1une

Back to top page