パスカルの三角形を使ったnCk mod [備忘録]

AtCoder abc132 youtubeでの解説 より

オーダーは$O(n!)$くらいです

利点

• 一度計算してしまえばあとはO(1)で求められる

• 実装が割と単純

// パスカルの三角形
/*
AtCoder abc 132 解説より
https://www.youtube.com/watch?v=mso8tE1yMl8
*/
/*
    1
   1 1
  1 2 1
 1 3 3 1

aCb はa段目のb番目
*/

// MUsize: 演算字自動でmodをとる構造体
static MOD: usize = 1_000_000_000 + 7;
use std::ops::{AddAssign, SubAssign, MulAssign};
use std::ops::{Add, Sub, Mul};
#[derive(Copy, Clone, Debug)]
struct MUsize {x: usize}
impl MUsize {
    fn new(x: usize) -> MUsize {
        MUsize{x: x%MOD}
    }
}
impl AddAssign for MUsize {
    fn add_assign(&mut self, other: MUsize) {
        let tmp = self.x + other.x;
        *self = MUsize {
            x: if tmp >= MOD {tmp - MOD} else {tmp}
        };
    }
}
impl SubAssign for MUsize {
    fn sub_assign(&mut self, other: MUsize) {
        let tmp = self.x + MOD - other.x;
        *self = MUsize {
            x: if tmp >= MOD {tmp - MOD} else {tmp}
        };
    }
}
impl MulAssign for MUsize {
    fn mul_assign(&mut self, other: MUsize) {
        *self = MUsize {
            x: self.x * other.x % MOD
        };
    }
}
impl Add for MUsize {
    type Output = MUsize;
    fn add(self, other: MUsize) -> MUsize {
        let mut res = MUsize::new(self.x);
        res += other.clone();
        res
    }
}
impl Sub for MUsize {
    type Output = MUsize;
    fn sub(self, other: MUsize) -> MUsize {
        let mut res = MUsize::new(self.x);
        res -= other;
        res
    }
}
impl Mul for MUsize {
    type Output = MUsize;
    fn mul(self, other: MUsize) -> MUsize {
        let mut res = MUsize::new(self.x);
        res *= other;
        res
    }
}

struct C {
    c: Vec<Vec<MUsize>>
}
impl C {
    fn new(max: usize) -> C {
        let mut c = vec![vec![MUsize::new(0); max+2]; max+2];
        c[0][0] = MUsize::new(1);
        for i in 0..max+1 {
            for j in 0..i+1 {
                let tmp = c[i][j];
                c[i+1][j] += tmp;
                c[i+1][j+1] += tmp;
            }
        }
        C {c:c}
    }
}
fn main() {
    let c = C::new(4005);
    assert!(c.c[8][2].x, 28);
    assert!(c.c[8][3].x, 56);
}

困っていること

stack overflow に提出させていただきました。

warning[E0502]: cannot borrow c as immutable because it is also borrowed as mutable