pascal_triangle/lib.rs
1/// 0 以上 `n` 未満の全ての `i`, `j` について二項係数 `i` choose `j` (mod `m`) を求めます。
2///
3/// # Examples
4///
5/// ```
6/// use pascal_triangle::pascal_triangle;
7/// assert_eq!(
8/// pascal_triangle(5, 100000),
9/// vec![
10/// vec![1, 0, 0, 0, 0],
11/// vec![1, 1, 0, 0, 0],
12/// vec![1, 2, 1, 0, 0],
13/// vec![1, 3, 3, 1, 0],
14/// vec![1, 4, 6, 4, 1],
15/// ],
16/// );
17/// ```
18pub fn pascal_triangle(n: usize, m: u64) -> Vec<Vec<u64>> {
19 let mut binom = vec![vec![0; n]; n];
20 binom[0][0] = 1;
21 for i in 1..n {
22 binom[i][0] = 1;
23 for j in 1..n {
24 binom[i][j] = (binom[i - 1][j - 1] + binom[i - 1][j]) % m;
25 }
26 }
27 binom
28}
29
30#[cfg(test)]
31mod tests {
32 use crate::pascal_triangle;
33
34 #[test]
35 fn test() {
36 assert_eq!(
37 pascal_triangle(6, 100000),
38 vec![
39 vec![1, 0, 0, 0, 0, 0],
40 vec![1, 1, 0, 0, 0, 0],
41 vec![1, 2, 1, 0, 0, 0],
42 vec![1, 3, 3, 1, 0, 0],
43 vec![1, 4, 6, 4, 1, 0],
44 vec![1, 5, 10, 10, 5, 1],
45 ],
46 );
47 }
48}