Kortit II

use std::{cmp, collections::HashMap, io};

fn main() {
    let mut t_str = String::new();
    io::stdin().read_line(&mut t_str).unwrap();
    t_str = t_str.trim().to_string();
    let t: usize = t_str.parse().unwrap();

    let mut tests: Vec<[usize; 3]> = Vec::with_capacity(t);

    for test in 0..t {
        let mut test_str = String::new();
        io::stdin().read_line(&mut test_str).unwrap();
        test_str = test_str.trim().to_string();

        tests.push([0, 0, 0]);
        for (i, num) in test_str.split(' ').enumerate() {
            tests[test][i] = num.parse().unwrap();
        }
    }

    let mut cache = HashMap::new();

    for test in tests {
        if test[1]+test[2] > test[0] {
            println!("0");
            continue;
        }
        let evens = test[0]-test[1]-test[2];
        if (evens+test[1] == test[0] || evens+test[2] == test[0]) && (test[1]!=test[2]) {
            println!("0");
            continue;
        }

        let mut slots = vec![false; test[1]+test[2]];
        
        let mut amount= count(&mut cache, &mut slots, 1, cmp::min(test[1], test[2]), cmp::max(test[1], test[2]));
        amount *= factorial(test[0], test[0]-evens);
        amount %= 1000000007;
        amount *= factorial(test[0], 0);
        amount %= 1000000007;
        println!("{}", amount);
    }
}

pub fn factorial(num: usize, div: usize) -> usize {
    let mut result = 1;
    for i in div+1..=num {
        result *= i;
        result %= 1000000007;
    }
    return result;
}

fn compute_order(slots: &Vec<bool>, slot: usize) -> Vec<u8> {
    let mut order = Vec::with_capacity(slots.len());
    for s in 0..slots.len() {
        if slots[s] {
            if slot <= s+1 {
                order.push(2);
            } else {
                order.push(1);
            }
        }
        else if slot <= s+1 {
            order.push(0);
        }
    }
    return order;
}

fn count(cache: &mut HashMap<(Vec<u8>, usize), usize>, slots: &mut Vec<bool>, slot: usize, losses: usize, wins: usize) -> usize {
    if slot == slots.len() {
        if wins > 0 && *slots.last().unwrap() {
            return 1;
        }
        return 0;
    }

    let order = compute_order(slots, slot);

    if cache.contains_key(&(order.clone(), losses)) {
        return *cache.get(&(order, losses)).unwrap();
    }

    let mut amount = 0;

    for s in 0..slots.len() {
        if !slots[s] {
            if losses > 0 && s+1 > slot {
                *slots.get_mut(s).unwrap() = true;
                amount += count(cache, slots, slot+1, losses-1, wins);
                *slots.get_mut(s).unwrap() = false;
            }
            else if wins > 0 && s+1 < slot {
                *slots.get_mut(s).unwrap() = true;
                amount += count(cache, slots, slot+1, losses, wins-1);
                *slots.get_mut(s).unwrap() = false;
            }
        }
    }

    cache.insert((order, losses), amount);

    return amount;
}

Test 1

Group: 1, 2, 3, 4, 5

Verdict: WRONG ANSWER

Test 2

Group: 2, 3, 4, 5

Verdict: WRONG ANSWER

Test 3

Group: 3, 4, 5

Verdict: TIME LIMIT EXCEEDED

Test 4

Group: 4, 5

Verdict: TIME LIMIT EXCEEDED

Test 5

Group: 5

Verdict: TIME LIMIT EXCEEDED

Test 6

Group: 5

Verdict: TIME LIMIT EXCEEDED