meta hacker cup winetasting

winetasting.rs

/*
https://www.youtube.com/c/RobertKing/videos
@robertkingnz
problem: https://www.facebook.com/codingcompetitions/hacker-cup/2011/round-1a/problems/C
video: 
*/

use std::collections::HashMap;

pub struct Combination {
    fact: Vec<usize>,
    inv_fact: Vec<usize>,
    modulo: usize,
}

impl Combination {
    pub fn new(max: usize, modulo: usize) -> Self {
        let mut inv = vec![0; max + 1];
        let mut fact = vec![0; max + 1];
        let mut inv_fact = vec![0; max + 1];
        inv[1] = 1;
        for i in 2..(max + 1) {
            inv[i] = inv[modulo % i] * (modulo - modulo / i) % modulo;
        }
        fact[0] = 1;
        inv_fact[0] = 1;
        for i in 0..max {
            fact[i + 1] = fact[i] * (i + 1) % modulo;
        }
        for i in 0..max {
            inv_fact[i + 1] = inv_fact[i] * inv[i + 1] % modulo;
        }
        Self {
            fact,
            inv_fact,
            modulo,
        }
    }

    pub fn get(&self, x: usize, y: usize) -> usize {
        assert!(x >= y);
        self.fact[x] * self.inv_fact[y] % self.modulo * self.inv_fact[x - y] % self.modulo
    }

    pub fn h(&self, n: usize, r: usize) -> usize {
        self.get(n + r - 1, r)
    }
}

const MOD: usize = 1051962371;


fn solve(g: usize, c: usize, combo: &Combination, cache: &mut HashMap<(usize, usize), usize>) -> usize {
    if let Some(&ans) = cache.get(&(g, c)) {
        return ans;
    }
    let mut ans = 1;
    for correct in c..g-1 {
        let mut ways_incorrect = MOD + combo.fact[g - correct] - solve(g - correct, 1, combo, cache);
        ways_incorrect %= MOD;
        ans += combo.get(g, correct) * ways_incorrect % MOD;
        ans %= MOD;
    }
    cache.insert((g, c), ans);
    ans
}

fn main() {
    let (r, w) = (std::io::stdin(), std::io::stdout());
    let mut sc = IO::new(r.lock(), w.lock());
    let combo = Combination::new(100, MOD);
    let mut cache = HashMap::new();
    let t: usize = sc.read();
    for case_num in 1..=t {
        let g: usize = sc.read();
        let c: usize = sc.read();
        let ans = solve(g, c, &combo, &mut cache);
        sc.write(
            format!("Case #{}: {}", case_num, ans)
        );
        sc.write("\n");
    }
}

pub struct IO<R, W: std::io::Write>(R, std::io::BufWriter<W>);

impl<R: std::io::Read, W: std::io::Write> IO<R, W> {
    pub fn new(r: R, w: W) -> IO<R, W> {
        IO(r, std::io::BufWriter::new(w))
    }
    pub fn write<S: ToString>(&mut self, s: S) {
        use std::io::Write;
        self.1.write_all(s.to_string().as_bytes()).unwrap();
    }
    pub fn read<T: std::str::FromStr>(&mut self) -> T {
        use std::io::Read;
        let buf = self
            .0
            .by_ref()
            .bytes()
            .map(|b| b.unwrap())
            .skip_while(|&b| b == b' ' || b == b'\n' || b == b'\r' || b == b'\t')
            .take_while(|&b| b != b' ' && b != b'\n' && b != b'\r' && b != b'\t')
            .collect::<Vec<_>>();
        unsafe { std::str::from_utf8_unchecked(&buf) }
            .parse()
            .ok()
            .expect("Parse error.")
    }
    pub fn usize0(&mut self) -> usize {
        self.read::<usize>() - 1
    }
    pub fn vec<T: std::str::FromStr>(&mut self, n: usize) -> Vec<T> {
        (0..n).map(|_| self.read()).collect()
    }
    pub fn chars(&mut self) -> Vec<char> {
        self.read::<String>().chars().collect()
    }

    pub fn binary_vec(&mut self) -> Vec<u8> {
        self.read::<String>()
            .bytes()
            .map(|b| b - b'0')
            .collect()
    }

    pub fn grid<T, F>(&mut self, r: usize, f: &F) -> Vec<Vec<T>>
        where F: Fn(char) -> T {
        let mut g = Vec::with_capacity(r);
        for _ in 0..r {
            g.push(
                self.chars().into_iter().map(f).collect()
            )
        }
        g
    }
}