1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

use super::binomial_coefficient::BCTDP;
use crate::factorial::Factoriable;
use crate::modint::ModInt;

use cargo_snippet::snippet;

/// `n P k` を `O(k)` で
///
/// 内部はfallingをラップしているだけ
#[snippet("permutation", include = "binomial_coefficient")]
pub fn permutation<T: Factoriable>(n: T, k: usize) -> T {
    n.falling(k)
}

#[test]
fn permutation_test() {
    assert_eq!(permutation(10usize, 3), 10 * 9 * 8);
    assert_eq!(permutation(ModInt::new(6, 10), 4).get(), 6 * 5 * 4 * 3 % 10);
}

#[snippet("permutation", include = "binomial_coefficient")]
pub fn permutation_with_table(table: &BCTDP, n: usize, k: usize) -> ModInt {
    if k > n {
        ModInt::new(0, table.get_mod())
    } else {
        table.factorial(n) * table.factorial_inverse(n - k)
    }
}

#[test]
fn with_table_test() {
    let tbl = BCTDP::new(10, 1000000007);
    assert_eq!(permutation_with_table(&tbl, 4, 2).get(), 12);
    assert_eq!(permutation_with_table(&tbl, 10, 4).get(), 10 * 9 * 8 * 7);
    assert_eq!(permutation_with_table(&tbl, 1, 2).get(), 0);
}