Struct Factorial 

pub struct Factorial { /* private fields */ }

階乗とその乗法逆元、そして二項係数を扱います。

Implementations

impl Factorial

pub fn new(size: usize, modulo: u64) -> Self

1 以上 size 未満の n について、n の階乗 (mod modulo) と、その乗法逆元を O(size) 時間で計算します。参考

逆元を正しく計算するためには

• modulo が素数
• modulo >= size

である必要があります。

Examples

use factorials::Factorial;

let modulo = 1_000_000_000 + 7;
let f = Factorial::new(100, modulo);
for i in 1..100 {
    assert_eq!(f.factorial(i) * f.inversion(i) % modulo, 1);
}

Panics

modulo が size より小さい場合パニックです。

use factorials::Factorial;

let size = 100;
let modulo = 97;
Factorial::new(size, modulo);

pub fn new_checking_modulo_prime(size: usize, modulo: u64) -> Self

modulo が素数でない場合パニックです。素数判定に O(sqrt(modulo)) 時間かかります。

Panics

use factorials::Factorial;

let modulo = 42;
Factorial::new_checking_modulo_prime(10, 42);

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

pub fn inversion(&self, n: usize) -> u64

pub fn binomial(&self, n: usize, k: usize) -> u64

二項係数を返します。

Examples

use factorials::Factorial;

let f = Factorial::new_checking_modulo_prime(5, 107);
assert_eq!(f.binomial(4, 0), 1);
assert_eq!(f.binomial(4, 1), 4);
assert_eq!(f.binomial(4, 2), 6);
assert_eq!(f.binomial(4, 3), 4);
assert_eq!(f.binomial(4, 4), 1);

Panics

以下の少なくともひとつが成り立つ場合パニックです。

• n が構築時の size 以上
• k が構築時の size 以上
• n が k より小さい

use factorials::Factorial;

let f = Factorial::new_checking_modulo_prime(5, 107);
f.binomial(3, 4); // n < k

pub fn binomial_or_zero(&self, n: usize, k: usize) -> u64

binomial とほとんど同じですが n が k より小さいときパニックせずに 0 を返します。

use factorials::Factorial;

let f = Factorial::new_checking_modulo_prime(5, 107);
assert_eq!(f.binomial_or_zero(3, 4), 0);