1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
/*
 * @uni_kakurenbo
 * https://github.com/uni-kakurenbo/competitive-programming-workspace
 *
 * CC0 1.0  http://creativecommons.org/publicdomain/zero/1.0/deed.ja
 */
/* #language C++ 20 GCC */

#define PROBLEM "https://judge.yosupo.jp/problem/binomial_coefficient_prime_mod"

#include "sneaky/enforce_int128_enable.hpp"

#include <iostream><--- Include file:  not found. Please note: Cppcheck does not need standard library headers to get proper results.
#include <bit><--- Include file:  not found. Please note: Cppcheck does not need standard library headers to get proper results.

#include "snippet/aliases.hpp"
#include "snippet/fast_io.hpp"
#include "snippet/iterations.hpp"
#include "adaptor/io.hpp"
#include "snippet/aliases.hpp"
#include "numeric/binomial_coefficient.hpp"
#include "numeric/modular/binary_reduction.hpp"

signed main() {
    uni::i32 t; input >> t;
    uni::u32 m; input >> m;

    if(std::has_single_bit(m)) {
        uni::binomial_coefficient_prime_power_mod<uni::i32, uni::i32, uni::binary_reduction_32bit> binom(m, 1, 10'000'000);

        REP(t) {
            uni::i32 n, k; input >> n >> k;
            print(binom.comb(n, k));
        }
    }
    else {
        uni::binomial_coefficient_prime_power_mod<uni::i32, uni::i32, uni::montgomery_reduction_32bit> binom(m, 1, 10'000'000);

        REP(t) {
            uni::i32 n, k; input >> n >> k;
            print(binom.comb(n, k));
        }
    }
}