Lucas
(src/math/lucas.hpp)

• View this file on GitHub
• Last update: 2024-11-09 02:03:28+09:00
• Include: #include "src/math/lucas.hpp"

Lucas

• 二項係数 $_n C _k \pmod{p}$

などを計算するアルゴリズムです．

$p$ が素数でさえあれば $n > p$ の場合でも正しく計算できることが特徴です．

コンストラクタ

Lucas<mint> binom

• mint の法 $p$ における $0!$ ~ $(p - 1)!$ および $(0!)^{-1}$ ~ $((p - 1)!)^{-1}$ のテーブルを構築します．

制約

• $p$ は素数

計算量

• $O(p)$

operator ()

mint binom(ll n, ll k)

$_n C _k \pmod{p}$ を計算します．

$n < 0$ または $n < k$ または $k < 0$ の場合は $0$ を返します．

計算量

• $O(\log_p n)$

Depends on

• template (src/template/template.hpp)

Verified with

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

Code

#pragma once
#include "../template/template.hpp"
template <typename mint>
struct Lucas {
    Lucas()
        : mod(mint::mod()), fact(mint::mod()), ifact(mint::mod()) {
        fact[0] = 1;
        for(int i = 1; i < mod; ++i) fact[i] = fact[i - 1] * i;
        ifact[mod - 1] = fact[mod - 1].inv();
        for(int i = mod - 1; i >= 1; --i) ifact[i - 1] = ifact[i] * i;
    }
    mint operator()(long long n, long long k) const {
        if(n < 0 or n < k or k < 0) return 0;
        mint res = 1;
        while(n > 0) {
            const long long n0 = n % mod, k0 = k % mod;
            if(n0 < k0) return 0;
            res *= fact[n0] * ifact[k0] * ifact[n0 - k0];
            n /= mod;
            k /= mod;
        }
        return res;
    }

   private:
    int mod;
    vector<mint> fact, ifact;
};

#line 2 "src/template/template.hpp"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<long long, long long>;
#define rep(i, a, b) for(long long i = (a); i < (b); ++i)
#define rrep(i, a, b) for(long long i = (a); i >= (b); --i)
constexpr long long inf = 4e18;
struct SetupIO {
    SetupIO() {
        ios::sync_with_stdio(0);
        cin.tie(0);
        cout << fixed << setprecision(30);
    }
} setup_io;
#line 3 "src/math/lucas.hpp"
template <typename mint>
struct Lucas {
    Lucas()
        : mod(mint::mod()), fact(mint::mod()), ifact(mint::mod()) {
        fact[0] = 1;
        for(int i = 1; i < mod; ++i) fact[i] = fact[i - 1] * i;
        ifact[mod - 1] = fact[mod - 1].inv();
        for(int i = mod - 1; i >= 1; --i) ifact[i - 1] = ifact[i] * i;
    }
    mint operator()(long long n, long long k) const {
        if(n < 0 or n < k or k < 0) return 0;
        mint res = 1;
        while(n > 0) {
            const long long n0 = n % mod, k0 = k % mod;
            if(n0 < k0) return 0;
            res *= fact[n0] * ifact[k0] * ifact[n0 - k0];
            n /= mod;
            k /= mod;
        }
        return res;
    }

   private:
    int mod;
    vector<mint> fact, ifact;
};

Back to top page