examples/library_checker_binomial_coefficient_prime_mod.rs

• View this file on GitHub
• Last update: 2024-04-26 00:41:30+09:00
• Problem: https://judge.yosupo.jp/problem/binomial_coefficient_prime_mod

Depends on

• src/data_structure.rs
• src/data_structure/prefix_sum.rs
• src/data_structure/range_set.rs
• セグメント木 (src/data_structure/segment_tree.rs)
• src/data_structure/sorted_set.rs
• Union Find（素集合データ構造） (src/data_structure/union_find.rs)
• src/lib.rs
• src/math.rs
• src/math/binomial.rs
• src/utils.rs
• src/utils/binary_search.rs
• src/utils/compression.rs

Code

// competitive-verifier: PROBLEM https://judge.yosupo.jp/problem/binomial_coefficient_prime_mod

use ac_library::ModInt as mint;
use proconio::input;
use rust_procon_lib::math::binomial::binomial::BinomialCoefficient;

const SIZE: usize = 10_000_000;

fn main() {
    input! {
        t: usize,
        m: u32,
    }

    mint::set_modulus(m);

    let bc = BinomialCoefficient::<mint>::new(SIZE);

    for _ in 0..t {
        input! {
            n: usize,
            k: usize,
        }

        println!("{}", bc.binomial_coefficient(n, k));
    }
}

Test cases

Env	Name	Status	Elapsed	Memory
Rust	example_00	AC	83 ms	119 MB
Rust	example_01	AC	83 ms	119 MB
Rust	large_random_00	AC	1143 ms	135 MB
Rust	large_random_01	AC	1127 ms	135 MB
Rust	large_random_02	AC	1121 ms	135 MB
Rust	med_random_00	AC	947 ms	132 MB
Rust	med_random_01	AC	972 ms	132 MB
Rust	med_random_02	AC	967 ms	133 MB
Rust	mod1000000007_00	AC	1109 ms	135 MB
Rust	mod1000000007_01	AC	1120 ms	135 MB
Rust	mod2_00	AC	887 ms	123 MB
Rust	mod2_01	AC	889 ms	123 MB
Rust	mod3_00	AC	889 ms	123 MB
Rust	mod3_01	AC	891 ms	123 MB
Rust	mod998244353_00	AC	1115 ms	135 MB
Rust	mod998244353_01	AC	1105 ms	135 MB
Rust	mod998244353_maxi_00	AC	1252 ms	134 MB
Rust	small_random_00	AC	891 ms	125 MB
Rust	small_random_01	AC	944 ms	125 MB
Rust	small_random_02	AC	897 ms	125 MB

Back to top page