Struct nekolib::math::ModFactorialBinom

pub struct ModFactorialBinom { /* private fields */ }

法 $p$ での二項係数。

Examples

use nekolib::math::ModFactorialBinom;

const MOD: u64 = 998244353;
let mfb = ModFactorialBinom::new(10, MOD);

assert_eq!(mfb.factorial(5), 120);
assert_eq!(mfb.factorial_recip(5), 856826403);
assert_eq!(mfb.recip(3), 332748118);

assert_eq!(mfb.perm(6, 4), 360);
assert_eq!(mfb.binom(7, 3), 35);

use nekolib::math::ModFactorialBinom;

const MOD: u64 = 998244353;
let mfb = ModFactorialBinom::new(10, MOD);

mfb.recip(0);

Implementations

impl ModFactorialBinom

pub fn new(n: usize, p: u64) -> Self

$(0!, 1!, \dots, n!)$ と $(0!^{-1}, 1!^{-1}, \dots, n!^{-1})$ を $p$ を法として計算する。

pub fn factorial(&self, i: usize) -> u64

$i! \bmod p$ を返す。

pub fn factorial_recip(&self, i: usize) -> u64

$i!^{-1} \bmod p$ を返す。

pub fn recip(&self, i: usize) -> u64

$i^{-1} \bmod p$ を返す。

pub fn perm(&self, i: usize, j: usize) -> u64

$i!/(i-j)! \bmod p$ を返す。

pub fn binom(&self, i: usize, j: usize) -> u64

$i!/(j!\cdot (i-j)!) \bmod p$ を返す。