結果

問題 No.584 赤、緑、青の色塗り
コンテスト
ユーザー titia
提出日時 2025-02-04 04:34:31
言語 Rust
(1.83.0 + proconio)
結果
WA  
実行時間 -
コード長 2,925 bytes
コンパイル時間 16,559 ms
コンパイル使用メモリ 379,316 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2025-02-04 04:34:53
合計ジャッジ時間 20,215 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 6
other AC * 13 WA * 1
権限があれば一括ダウンロードができます

ソースコード

diff # 

use std::io;

const MOD: u64 = 1_000_000_007;

fn mod_pow(mut base: u64, mut exp: u64, modu: u64) -> u64 {
    let mut result = 1;
    while exp > 0 {
        if exp % 2 == 1 {
            result = result * base % modu;
        }
        base = base * base % modu;
        exp /= 2;
    }
    result
}

fn main() {
    let mut input = String::new();
    io::stdin().read_line(&mut input).unwrap();
    let nums: Vec<u64> = input.trim().split_whitespace().map(|x| x.parse().unwrap()).collect();
    let (n, r, g, b) = (nums[0], nums[1], nums[2], nums[3]);

    let mut pow2 = vec![1u64; 10_001];
    for i in 1..pow2.len() {
        pow2[i] = pow2[i - 1] * 2 % MOD;
    }

    let mut fact = vec![1u64; 2 * 100_000 + 1];
    for i in 1..fact.len() {
        fact[i] = fact[i - 1] * i as u64 % MOD;
    }

    let mut fact_inv = vec![0u64; fact.len()];
    fact_inv[fact.len() - 1] = mod_pow(fact[fact.len() - 1], MOD - 2, MOD);
    for i in (1..fact.len()).rev() {
        fact_inv[i - 1] = fact_inv[i] * i as u64 % MOD;
    }

    fn combi(a: u64, b: u64, fact: &Vec<u64>, fact_inv: &Vec<u64>) -> u64 {
        if b <= a {
            fact[a as usize] * fact_inv[b as usize] % MOD * fact_inv[(a - b) as usize] % MOD
        } else {
            0
        }
    }

    let mut ans: u64 = 0;

    for x in (0..=r.min(g)).rev() {
        for y in (0..=g.min(b)).rev() {
            for z in (0..=b.min(r)).rev() {
                if x * 2 + y * 2 + z * 2 > n {
                    break;
                }

                let r_rest = r as i64 - x as i64 - z as i64;
                let g_rest = g as i64 - x as i64 - y as i64;
                let b_rest = b as i64 - y as i64 - z as i64;

                if r_rest < 0 || g_rest < 0 || b_rest < 0 {
                    continue;
                }

                let r_rest = r_rest as u64;
                let g_rest = g_rest as u64;
                let b_rest = b_rest as u64;
                let need = x + y + z + r_rest + g_rest + b_rest - 1;

                if x * 2 + y * 2 + z * 2 + r_rest + g_rest + b_rest + need > n {
                    break;
                }

                let empty = n - x * 2 - y * 2 - z * 2 - r_rest - g_rest - b_rest - need;

                let ax = combi(x + y + z + r_rest + g_rest + b_rest, x, &fact, &fact_inv)
                    * combi(y + z + r_rest + g_rest + b_rest, y, &fact, &fact_inv) % MOD
                    * combi(z + r_rest + g_rest + b_rest, z, &fact, &fact_inv) % MOD
                    * combi(r_rest + g_rest + b_rest, r_rest, &fact, &fact_inv) % MOD
                    * combi(g_rest + b_rest, g_rest, &fact, &fact_inv) % MOD;

                let ay = pow2[(x + y + z) as usize];

                let az = combi(empty + (x + y + z + r_rest + g_rest + b_rest), empty, &fact, &fact_inv);

                ans = (ans + ax * ay % MOD * az % MOD) % MOD;
            }
        }
    }

    println!("{}", ans);
}
0