結果

問題 No.3394 Big Binom
コンテスト
ユーザー asmin
提出日時 2025-12-02 13:34:21
言語 C++17(gcc12)
(gcc 12.3.0 + boost 1.89.0)
結果
AC  
実行時間 1,224 ms / 2,000 ms
コード長 5,544 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 4,717 ms
コンパイル使用メモリ 215,768 KB
実行使用メモリ 7,848 KB
最終ジャッジ日時 2025-12-14 20:02:58
合計ジャッジ時間 14,291 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 22
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

template <uint32_t mod_, bool fast = false>
struct MontgomeryModInt {
private:
    using mint = MontgomeryModInt;
    using i32 = int32_t;
    using i64 = int64_t;
    using u32 = uint32_t;
    using u64 = uint64_t;

    static constexpr u32 get_r() {
        u32 ret = mod_;
        for (i32 i = 0; i < 4; i++) ret *= 2 - mod_ * ret;
        return ret;
    }

    static constexpr u32 r = get_r();

    static constexpr u32 n2 = -u64(mod_) % mod_;

    static_assert(r * mod_ == 1, "invalid, r * mod != 1");
    static_assert(mod_ < (1 << 30), "invalid, mod >= 2 ^ 30");
    static_assert((mod_ & 1) == 1, "invalid, mod % 2 == 0");

    u32 x;

    public:
    MontgomeryModInt() : x{} {}

    MontgomeryModInt(const i64 &a): x(reduce(u64(fast ? a : (a % mod() + mod())) * n2)) {}

    static constexpr u32 reduce(const u64 &b) {
        return u32(b >> 32) + mod() - u32((u64(u32(b) * r) * mod()) >> 32);
    }

    mint &operator+=(const mint &p) {
        if (i32(x += p.x - 2 * mod()) < 0) x += 2 * mod();
        return *this;
    }

    mint &operator-=(const mint &p) {
        if (i32(x -= p.x) < 0) x += 2 * mod();
        return *this;
    }

    mint &operator*=(const mint &p) {
        x = reduce(u64(x) * p.x);
        return *this;
    }

    mint &operator/=(const mint &p) {
        *this *= p.inv();
        return *this;
    }

    mint operator-() const { return mint() - *this; }

    mint operator+(const mint &p) const { return mint(*this) += p; }

    mint operator-(const mint &p) const { return mint(*this) -= p; }

    mint operator*(const mint &p) const { return mint(*this) *= p; }

    mint operator/(const mint &p) const { return mint(*this) /= p; }

    bool operator==(const mint &p) const {
        return (x >= mod() ? x - mod() : x) == (p.x >= mod() ? p.x - mod() : p.x);
    }

    bool operator!=(const mint &p) const {
        return (x >= mod() ? x - mod() : x) != (p.x >= mod() ? p.x - mod() : p.x);
    }

    u32 val() const {
        u32 ret = reduce(x);
        return ret >= mod() ? ret - mod() : ret;
    }

    mint pow(u64 n) const {
        mint ret(1), mul(*this);
        while (n > 0) {
            if (n & 1) ret *= mul;
            mul *= mul;
            n >>= 1;
        }
        return ret;
    }

    mint inv() const { return pow(mod() - 2); }

    friend ostream &operator<<(ostream &os, const mint &p) {
        return os << p.val();
    }

    friend istream &operator>>(istream &is, mint &a) {
        i64 t;
        is >> t;
        a = mint(t);
        return is;
    }

    static constexpr u32 mod() { return mod_; }

    static constexpr bool isNTT(){
        int p = mod() - 1;
        int cnt = 0;
        while(!(p & 1)){
            p >>= 1;
            ++cnt;
        }
        if(cnt >= 23) return true;
        else return false;
    }
};

template<class T_VAL, class T_MOD>
constexpr T_VAL mod_pow(T_VAL a, T_VAL n, T_MOD m) {
    T_VAL res = 1;
    while (n > 0) {
        if (n % 2 == 1) res = res * a % m;
        a = a * a % m;
        n >>= 1;
    }
    return res;
}

constexpr int calc_primitive_root(long long m){
    if(m == 1) return -1;
    if(m == 2) return 1;
    if(m == 998244353) return 3;
    if(m == 167772161) return 3;
    if(m == 469762049) return 3;
    if(m == 754974721) return 11;
    if(m == 645922817) return 3;
    if(m == 897581057) return 3;
    long long divs[20] = {};
    divs[0] = 2;
    long long cnt = 1;
    long long x = (m - 1) / 2;
    while(x % 2 == 0) x /= 2;
    for(long long i = 3; i * i <= x; i += 2){
        if(x % i == 0){
            divs[cnt++] = i;
            while(x % i == 0) x /= i;
        }
    }
    if(x > 1) divs[cnt++] = x;
    for(long long g = 2; ; g++){
        bool ok = true;
        for(int i = 0; i < cnt; i++){
            if(mod_pow(g, (m - 1) / divs[i], m) == 1){
                ok = false;
                break;
            }
        }
        if (ok) return g;
    }
}

template <uint32_t mod>
using modint = MontgomeryModInt<mod>;
using mint = modint<998244353>;



void solve(){
    int N, K; cin >> N >> K;
    if(N < 998244353){
        vector<mint> f1(10);
        f1[0] = 1;
        f1[1] = 808258749;
        f1[2] = 117153405;
        f1[3] = 761699708;
        f1[4] = 573994984;
        f1[5] = 62402409;
        f1[6] = 511621808;
        f1[7] = 242726978;
        f1[8] = 887890124;
        f1[9] = 875880304;
        mint ans1 = 1;
        mint ans2 = 1;
        mint ans3 = 1;
        auto f = [&](int m) -> mint {
            mint res = 1;
            for(int i = 0; i < 10; ++i){
                if(i * 100000000 <= m && m < (i + 1) * 100000000){
                    res = f1[i];
                    for(int j = i * 100000000 + 1; j <= m; ++j){
                        res *= j;
                    }
                }
            }
            return res;
        };
        ans1 = f(N);
        ans2 = f(K);
        ans3 = f(N - K);
        cout << ans1 / (ans2 * ans3) << "\n";
    }else{
        if(max(K, N - K) < 998244353){
            cout << 0 << "\n";
        }else{
            K = min(K, N - K);
            N -= 998244353;
            mint ans = 1;
            for(int i = 1; i <= K; ++i){
                ans *= (N - i + 1);
                ans /= i;
            }
            cout << ans << "\n";
        }
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout << setprecision(10) << fixed;

    int T;
    T = 1;
    //cin >> T;
    for(;T--;) solve();
}
0