Решение задачи №88 от UniLecs

bin_coeff.rs

mod bin_coeff {
    #![deny(overflowing_literals)]
    
    use ::std::collections::HashMap;
    
    pub type Res = u64;
    pub const BOUND: Res = Res::max_value();
    
    const _MIN_OVERFLOWING_LINE: Res = 67;
    const FIRST_ALWAYS_OVERFLOWING_POS: Res = 33;
    const MAX_SAFE_LINE: [Res; FIRST_ALWAYS_OVERFLOWING_POS as usize - 2] =
        [4801278, 145055, 18579, 4867, 1912, 966, 576, 385,
         281, 217, 177, 149, 129, 115, 104, 96, 90, 85, 81,
         78, 75, 73, 71, 70, 69, 68, 67, 67, 67, 66, 66];
    
    fn overflows(n: Res, k: Res) -> bool {
        n > MAX_SAFE_LINE[(FIRST_ALWAYS_OVERFLOWING_POS - 1).min(k) as usize - 2]
    }
    
    fn triangle_num(n: Res) -> Res {
        if n & 1 == 0 {
            n / 2 * (n + 1)
        } else {
            (n + 1) / 2 * n
        }
    }
    
    pub fn tetrahedral_num(n: Res) -> Res {
        match (n & 1, n % 3) {
            (0, 0) => (n / 3) * ((n + 1)    ) * ((n + 2) / 2),
            (0, 1) => (n / 2) * ((n + 1)    ) * ((n + 2) / 3),
            (0, 2) => (n / 2) * ((n + 1) / 3) * ((n + 2)    ),
            (1, 0) => (n / 3) * ((n + 1) / 2) * ((n + 2)    ),
            (1, 1) => (n    ) * ((n + 1) / 2) * ((n + 2) / 3),
            _      => (n    ) * ((n + 1) / 6) * ((n + 2)    ),
         //^(1, 2)
        }
    }
    
    #[derive(Debug, PartialEq)]
    pub enum BinCoeffError {
        IncorrectIndices,
        ResultOutOfBound,
    }
    
    fn correct(n: Res, k: Res) -> Result<Res, BinCoeffError> {
        use bin_coeff::BinCoeffError;
        Ok(n.checked_sub(k).ok_or(BinCoeffError::IncorrectIndices)?.min(k))
    }
    
    pub struct Memo {
        inner: HashMap<(Res, Res), Res>,
    }
    
    impl Memo {
        pub fn new() -> Self {
            Self { inner: HashMap::new() }
        }
        
        pub fn get(&mut self, n: Res, k: Res) -> Result<Res, BinCoeffError> {
            use ::std::collections::LinkedList;
            use bin_coeff::BinCoeffError::*;
            
            let k = correct(n, k)?;
            
            match (n, k) {
                (0, _) => return Ok(1),
                (_, 0) => return Ok(1),
                (_, 1) => return Ok(n),
                (n, k) if overflows(n, k) => return Err(ResultOutOfBound),
                (_, 2) => return Ok(triangle_num(n - 1)),
                (_, 3) => return Ok(tetrahedral_num(n - 2)),
                _ => (),
            }
            
            let mut tasks = LinkedList::new();
            let table = &mut self.inner;
            tasks.push_front((n, k));
            
            while let Some((n, k)) = tasks.pop_front() {
                match (n, k) {
                    (0, _) => {table.insert((n, k), 1);},
                    (_, 0) => {table.insert((n, k), 1);},
                    (_, 1) => {table.insert((n, k), n);},
                    (_, 2) => {table.insert((n, k), triangle_num(n - 1));},
                    (_, 3) => {table.insert((n, k), tetrahedral_num(n - 2));},
                    _ => {
                        if table.get(&(n, k)).is_none() {
                            tasks.push_front((n, k));
                            let less_n = n - 1;
                            let k1 = k.min(less_n - k);
                            let k2 = (k - 1).min(less_n - (k - 1));
                            match table.get(&(less_n, k1)) {
                                None => tasks.push_front((less_n, k1)),
                                Some(&first) => match table.get(&(less_n, k2)) {
                                    None => tasks.push_front((less_n, k2)),
                                    Some(&second) => {
                                        let sum = first + second;
                                        table.insert((n, k), sum);
                                    },
                                }
                            }
                        }
                    }
                }
            }
            Ok(table[&(n, k)])
        }
    }
}

#[test]
fn do_tests() {
    use bin_coeff::*;
    use bin_coeff::BinCoeffError::*;
    let mut acc = Memo::new();
    
    assert_eq!(acc.get(8, 3), Ok(56));
    assert_eq!(acc.get(234, 3), Ok(2108184));
    assert_eq!(acc.get(67, 18), Ok(9364899127970100));
    assert_eq!(acc.get(333, 9), Ok(124416985140694675));
    
    assert_eq!(acc.get(120, 44), Err(ResultOutOfBound));
    assert_eq!(acc.get(BOUND, BOUND / 2), Err(ResultOutOfBound));
    
    assert_eq!(acc.get(23, 22333), Err(IncorrectIndices));
    assert_eq!(acc.get(1, 10), Err(IncorrectIndices));
}

Playground: https://play.rust-lang.org/?gist=4a9a328a71aee2c9cd82f7fd9c929730&version=stable