Solver for `Grid2` problem by the principle of inclusion-exclusion

grid_pie.rs

use proconio::input;
use proconio::marker::Usize1;
use ac_library::ModInt1000000007 as Mint;

fn main(){
    input!(
        h: usize, w: usize, n:usize,
        mut walls: [(Usize1, Usize1); n]
    );
    
    walls.push((0, 0));
    walls.push((h - 1, w - 1));
    walls.sort_by(|(_a_h, a_w), (_b_h, b_w)| a_w.cmp(&b_w));
    walls.sort_by(|(a_h, _a_w), (b_h, _b_w)| a_h.cmp(&b_h));

    let mut factorial: Vec<Mint> = Vec::with_capacity(n);
    let mut factorial_inv: Vec<Mint> = Vec::with_capacity(n);
    factorial.push(Mint::new(1));
    factorial_inv.push(Mint::new(1));
    for i in  1..(w + h) {
        factorial.push(factorial[i-1] * Mint::new(i));
        factorial_inv.push(factorial_inv[i-1] * Mint::new(i).inv());
    };
    let combination = |a, b| factorial[a] * factorial_inv[b] * factorial_inv[a - b];

    let n = n + 2;
    let mut dp: Vec<Vec<Mint>> = vec![vec![Mint::new(0); 2]; n];
    dp[0][1] = Mint::new(1);
    for i in 0 .. (n - 1) {
        for m in 0 .. 2 {
            for j in (i + 1) .. n {
                if walls[j].0 >= walls[i].0 && walls[j].1 >= walls[i].1 {
                    let (dx, dy) = (walls[j].0 - walls[i].0, walls[j].1 - walls[i].1);
                    dp[j][m] = dp[j][m] + dp[i][1 - m] * combination(dx + dy, dx);
                }
            }
        }
    }

    let result = dp[n - 1][0] - dp[n - 1][1];
    println!("{}", result); 
}