#1137598 (Rust) No.3394 Big Binom

• 問題: No.3394 Big Binom
• ユーザー: urectanc
• 提出日時: 2025-12-01 21:23:02
• 言語: Rust (1.83.0 + proconio)
• 結果: AC
• 実行時間: 22 ms / 2,000 ms
• コード長: 21,138 bytes
• コンパイル時間: 11,699 ms
• コンパイル使用メモリ: 396,632 KB
• 実行使用メモリ: 7,720 KB
• 最終ジャッジ日時: 2025-12-01 21:23:23
• 合計ジャッジ時間: 13,153 ms
• ジャッジサーバーID （参考情報）: judge2 / judge5

ファイルパターン	結果
sample	AC * 4
other	AC * 21

ソースコード

use modint::ModInt998244353;
use proconio::input;

type Mint = ModInt998244353;

const B: usize = 1_000_000;

fn main() {
    // precalc();

    input! { n: u32, k: u32 }
    let m = Mint::modulus();

    let (n1, n0) = (n / m, n % m);
    let (k1, k0) = (k / m, k % m);
    let ans = binom(n0, k0) * binom(n1, k1);
    println!("{ans}");
}

fn binom(n: u32, k: u32) -> Mint {
    if n < k {
        return 0.into();
    }
    fact(n) / fact(k) / fact(n - k)
}

fn fact(n: u32) -> Mint {
    assert!(n < Mint::modulus());
    let q = n as usize / B;
    let offset = (q * B) as u32;
    let mut fact = Mint::raw(TABLE[q]);
    for i in offset + 1..=n {
        fact *= i;
    }
    fact
}

#[allow(unused)]
fn precalc() {
    let mut table = vec![1];
    let mut fact = Mint::raw(1);
    for i in 1..Mint::modulus() as usize {
        fact *= i;
        if i % B == 0 {
            table.push(fact.val());
        }
    }

    println!("const TABLE: [u32; {}] = [", table.len());
    for chunk in table.chunks(8) {
        for x in chunk {
            print!("{x}, ");
        }
        println!();
    }
    println!("];");
}

#[allow(unused)]
mod modint {
    use std::ops::{Add, AddAssign, Div, DivAssign, Mul, MulAssign, Sub, SubAssign};

    const fn gcd_inv(a: i64, b: i64) -> (i64, i64) {
        let a = a.rem_euclid(b);
        if a == 0 {
            return (b, 0);
        }

        // invariant: u.0 = u.1 * a (mod b)
        // invariant: v.0 = v.1 * a (mod b)
        let mut u = (b, 0);
        let mut v = (a, 1);
        while v.0 != 0 {
            let q = u.0.div_euclid(v.0);
            u.0 -= q * v.0;
            u.1 -= q * v.1;
            (u, v) = (v, u);
        }

        if u.1 < 0 {
            u.1 += b.div_euclid(u.0);
        }

        u
    }

    pub trait Modulus: 'static + Clone + Copy {
        const MOD: u32;
    }

    macro_rules! define_modulus {
        ( $( ($name:ident, $modulus:expr) ),* $(,)? ) => { $(
            #[derive(Clone, Copy, Debug, PartialEq, Eq)]
            pub struct $name;
            impl Modulus for $name {
                // TODO: use inline const for static assertion in Rust >= 1.79
                // const MOD: u32 = const { assert!($modulus < (1u32 << 31)); $modulus };
                const MOD: u32 = $modulus;
            }
        )* };
    }

    define_modulus!((Mod998244353, 998244353), (Mod1000000007, 1000000007));

    #[derive(Clone, Copy, PartialEq, Eq, Hash)]
    pub struct StaticModInt<M> {
        val: u32,
        _phantom: std::marker::PhantomData<fn() -> M>,
    }

    impl<M: Modulus> StaticModInt<M> {
        pub const fn modulus() -> u32 {
            M::MOD
        }

        pub const fn new(val: u32) -> Self {
            Self {
                val: val.rem_euclid(Self::modulus()),
                _phantom: std::marker::PhantomData,
            }
        }

        pub const fn raw(val: u32) -> Self {
            Self {
                val,
                _phantom: std::marker::PhantomData,
            }
        }

        pub const fn val(&self) -> u32 {
            self.val
        }

        pub const fn pow(self, mut exp: u64) -> Self {
            let modulus = Self::modulus() as u64;
            let mut base = self.val() as u64;
            let mut acc = 1u64;

            while exp > 0 {
                if exp & 1 == 1 {
                    acc = acc * base % modulus;
                }
                base = base * base % modulus;
                exp >>= 1;
            }

            Self::raw(acc as u32)
        }

        pub const fn inv(self) -> Self {
            let Some(inv) = self.checked_inv() else {
                panic!()
            };
            inv
        }

        pub const fn checked_inv(self) -> Option<Self> {
            let (gcd, inv) = gcd_inv(self.val() as i64, Self::modulus() as i64);
            if gcd == 1 {
                Some(Self::raw(inv as u32))
            } else {
                None
            }
        }

        /// invariant: x.0 == val * x.1 (mod M) for x = u,v
        /// https://en.wikipedia.org/wiki/Rational_reconstruction_(mathematics)
        fn into_rational(&self) -> (i64, i64) {
            let m = Self::modulus() as i64;
            let mut u = (m, 0i64);
            let mut v = (self.val() as i64, 1i64);
            while v.0 * v.0 * 2 > m {
                let q = u.0.div_euclid(v.0);
                let w = (u.0 - q * v.0, u.1 - q * v.1);
                u = std::mem::replace(&mut v, w);
            }
            if v.1 < 0 {
                (-v.0, -v.1)
            } else {
                v
            }
        }
    }

    impl<M: Modulus> std::fmt::Display for StaticModInt<M> {
        fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
            write!(f, "{}", self.val)
        }
    }

    impl<M: Modulus> std::fmt::Debug for StaticModInt<M> {
        fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
            let (num, denom) = self.into_rational();
            if denom == 1 {
                write!(f, "{num}")
            } else {
                write!(f, "{num}/{denom}")
            }
        }
    }

    impl<M: Modulus> std::str::FromStr for StaticModInt<M> {
        type Err = std::num::ParseIntError;
        fn from_str(s: &str) -> Result<Self, Self::Err> {
            let value = s.parse::<u32>()?;
            Ok(value.into())
        }
    }

    macro_rules! impl_from_integer {
        ( $( $ty:tt ),* ) => { $(
            impl<M: Modulus> From<$ty> for StaticModInt<M> {
                fn from(value: $ty) -> StaticModInt<M> {
                    Self::raw((value as $ty).rem_euclid(Self::modulus() as $ty) as u32)
                }
            }
        )* };
    }
    impl_from_integer!(u32, u64, usize, i32, i64, isize);

    impl<M: Modulus> std::ops::Neg for StaticModInt<M> {
        type Output = Self;
        fn neg(mut self) -> Self::Output {
            if self.val > 0 {
                self.val = Self::modulus() - self.val;
            }
            self
        }
    }

    impl<M: Modulus, T: Into<StaticModInt<M>>> AddAssign<T> for StaticModInt<M> {
        fn add_assign(&mut self, rhs: T) {
            self.val += rhs.into().val;
            if self.val >= Self::modulus() {
                self.val -= Self::modulus();
            }
        }
    }

    impl<M: Modulus, T: Into<StaticModInt<M>>> SubAssign<T> for StaticModInt<M> {
        fn sub_assign(&mut self, rhs: T) {
            self.val = self.val.wrapping_sub(rhs.into().val);
            if self.val > Self::modulus() {
                self.val = self.val.wrapping_add(Self::modulus());
            }
        }
    }

    impl<M: Modulus, T: Into<StaticModInt<M>>> MulAssign<T> for StaticModInt<M> {
        fn mul_assign(&mut self, rhs: T) {
            self.val = ((self.val as u64 * rhs.into().val as u64) % Self::modulus() as u64) as u32;
        }
    }

    impl<M: Modulus, T: Into<StaticModInt<M>>> DivAssign<T> for StaticModInt<M> {
        fn div_assign(&mut self, rhs: T) {
            *self *= rhs.into().inv();
        }
    }

    macro_rules! impl_binnary_operators {
        ( $({ $op: ident, $op_assign: ident, $fn: ident, $fn_assign: ident}),* $(,)? ) => { $(
            impl<M: Modulus, T: Into<StaticModInt<M>>> std::ops::$op<T> for StaticModInt<M> {
                type Output = StaticModInt<M>;
                fn $fn(mut self, rhs: T) -> StaticModInt<M> {
                    self.$fn_assign(rhs.into());
                    self
                }
            }

            impl<M: Modulus> std::ops::$op<&StaticModInt<M>> for StaticModInt<M> {
                type Output = StaticModInt<M>;
                fn $fn(self, rhs: &StaticModInt<M>) -> StaticModInt<M> {
                    self.$fn(*rhs)
                }
            }

            impl<M: Modulus, T: Into<StaticModInt<M>>> std::ops::$op<T> for &StaticModInt<M> {
                type Output = StaticModInt<M>;
                fn $fn(self, rhs: T) -> StaticModInt<M> {
                    (*self).$fn(rhs.into())
                }
            }

            impl<M: Modulus> std::ops::$op<&StaticModInt<M>> for &StaticModInt<M> {
                type Output = StaticModInt<M>;
                fn $fn(self, rhs: &StaticModInt<M>) -> StaticModInt<M> {
                    (*self).$fn(*rhs)
                }
            }

            impl<M: Modulus> std::ops::$op_assign<&StaticModInt<M>> for StaticModInt<M> {
                fn $fn_assign(&mut self, rhs: &StaticModInt<M>) {
                    *self = self.$fn(*rhs);
                }
            }
        )* };
    }

    impl_binnary_operators!(
        {Add, AddAssign, add, add_assign},
        {Sub, SubAssign, sub, sub_assign},
        {Mul, MulAssign, mul, mul_assign},
        {Div, DivAssign, div, div_assign},
    );

    impl<M: Modulus> std::iter::Sum for StaticModInt<M> {
        fn sum<I: Iterator<Item = Self>>(iter: I) -> Self {
            iter.fold(Self::raw(0), Add::add)
        }
    }

    impl<'a, M: Modulus> std::iter::Sum<&'a StaticModInt<M>> for StaticModInt<M> {
        fn sum<I: Iterator<Item = &'a Self>>(iter: I) -> Self {
            iter.fold(Self::raw(0), Add::add)
        }
    }

    impl<M: Modulus> std::iter::Product for StaticModInt<M> {
        fn product<I: Iterator<Item = Self>>(iter: I) -> Self {
            iter.fold(Self::raw(1), Mul::mul)
        }
    }

    impl<'a, M: Modulus> std::iter::Product<&'a StaticModInt<M>> for StaticModInt<M> {
        fn product<I: Iterator<Item = &'a Self>>(iter: I) -> Self {
            iter.fold(Self::raw(1), Mul::mul)
        }
    }

    pub type ModInt998244353 = StaticModInt<Mod998244353>;
    pub type ModInt1000000007 = StaticModInt<Mod1000000007>;
}

const TABLE: [u32; 999] = [
    1, 373341033, 45596018, 834980587, 623627864, 428937595, 442819817, 499710224, 833655840,
    83857087, 295201906, 788488293, 671639287, 849315549, 597398273, 813259672, 732727656,
    244038325, 122642896, 310517972, 160030060, 483239722, 683879839, 712910418, 384710263,
    433880730, 844360005, 513089677, 101492974, 959253371, 957629942, 678615452, 34035221,
    56734233, 524027922, 31729117, 102311167, 330331487, 8332991, 832392662, 545208507, 594075875,
    318497156, 859275605, 300738984, 767818091, 864118508, 878131539, 316588744, 812496962,
    213689172, 584871249, 980836133, 54096741, 417876813, 363266670, 335481797, 730839588,
    393495668, 435793297, 760025067, 811438469, 720976283, 650770098, 586537547, 117371703,
    566486504, 749562308, 708205284, 932912293, 939830261, 983699513, 206579820, 301188781,
    593164676, 770845925, 247687458, 41047791, 266419267, 937835947, 506268060, 6177705, 936268003,
    166873118, 443834893, 328979964, 470135404, 954410105, 117565665, 832761782, 39806322,
    478922755, 394880724, 821825588, 468705875, 512554988, 232240472, 876497899, 356048018,
    895187265, 808258749, 575505950, 68190615, 939065335, 552199946, 694814243, 385460530,
    529769387, 640377761, 916128300, 440133909, 362216114, 826373774, 502324157, 457648395,
    385510728, 904737188, 78988746, 454565719, 623828097, 686156489, 713476044, 63602402,
    570334625, 681055904, 222059821, 477211096, 343363294, 833792655, 461853093, 741797144,
    74731896, 930484262, 268372735, 941222802, 677432735, 474842829, 700451655, 400176109,
    697644778, 390377694, 790010794, 360642718, 505712943, 946647976, 339045014, 715797300,
    251680896, 70091750, 40517433, 12629586, 850635539, 110877109, 571935891, 695965747, 634938288,
    69072133, 155093216, 749696762, 963086402, 544711799, 724471925, 334646013, 574791029,
    722417626, 377929821, 743946412, 988034679, 405207112, 18063742, 104121967, 638607426,
    607304611, 751377777, 35834555, 313632531, 18058363, 656121134, 40763559, 562910912, 495867250,
    48767038, 210864657, 659137294, 715390025, 865854329, 324322857, 388911184, 286059202,
    636456178, 421290700, 832276048, 726437551, 526417714, 252522639, 386147469, 674313019,
    274769381, 226519400, 272047186, 117153405, 712896591, 486826649, 119444874, 338909703,
    18536028, 41814114, 245606459, 140617938, 250512392, 57084755, 157807456, 261113192, 40258068,
    194807105, 325341339, 884328111, 896332013, 880836012, 737358206, 202713771, 785454372,
    399586250, 485457499, 640827004, 546969497, 749602473, 159788463, 159111724, 218592929,
    675932866, 314795475, 811539323, 246883213, 696818315, 759880589, 4302336, 353070689,
    477909706, 559289160, 79781699, 878094972, 840903973, 367416824, 973366814, 848259019,
    462421750, 667227759, 897917455, 81800722, 956276337, 942686845, 420541799, 417005912,
    272641764, 941778993, 217214373, 192220616, 267901132, 50530621, 652678397, 354880856,
    164289049, 781023184, 105376215, 315094878, 607856504, 733905911, 457743498, 992735713,
    35212756, 231822660, 276036750, 734558079, 424180850, 433186147, 308380947, 18333316, 12935086,
    351491725, 655645460, 535812389, 521902115, 67016984, 48682076, 64748124, 489360447, 361275315,
    786336279, 805161272, 468129309, 645091350, 887284732, 913004502, 358814684, 281295633,
    328970139, 395955130, 164840186, 820902807, 761699708, 246274415, 592331769, 913846362,
    866682684, 600130702, 903837674, 529462989, 90612675, 526540127, 533047427, 110008879,
    674279751, 801920753, 645226926, 676886948, 752481486, 474034007, 457790341, 166813684,
    287671032, 188118664, 244731384, 404032157, 269766986, 423996017, 182948540, 356801634,
    737863144, 652014069, 206068022, 504569410, 919894484, 593398649, 963768176, 882517476,
    702523597, 949028249, 128957299, 171997372, 50865043, 20937461, 690959202, 581356488,
    369182214, 993580422, 193500140, 540665426, 365786018, 743731625, 144980423, 979536721,
    773259009, 617053935, 247670131, 843705280, 30419459, 985463402, 261585206, 237885042,
    111276893, 488166208, 137660292, 720784236, 244467770, 26368504, 792857103, 666885724,
    670313309, 905683034, 259415897, 512017253, 826265493, 111960112, 633652060, 918048438,
    516432938, 386972415, 996212724, 610073831, 444094191, 72480267, 665038087, 11584804,
    301029012, 723617861, 113763819, 778259899, 937766095, 535448641, 593907889, 783573565,
    673298635, 599533244, 655712590, 173350007, 868198597, 169013813, 585161712, 697502214,
    573994984, 285943986, 675831407, 3134056, 965907646, 401920943, 665949756, 236277883,
    612745912, 813282113, 892454686, 901222267, 624900982, 927122298, 686321335, 84924870,
    927606072, 506664166, 353631992, 165913238, 566073550, 816674343, 864877926, 171259407,
    908752311, 874007723, 803597299, 613676466, 880336545, 282280109, 128761001, 58852065,
    474075900, 434816091, 364856903, 149123648, 388854780, 314693916, 423183826, 419733481,
    888483202, 238933227, 336564048, 757103493, 100189123, 855479832, 51370348, 403061033,
    496971759, 831753030, 251718753, 272779384, 683379259, 488844621, 881783783, 659478190,
    445719559, 740782647, 546525906, 985524427, 548033568, 333772553, 331916427, 752533273,
    730387628, 93829695, 655989476, 930661318, 334885743, 466041862, 428105027, 888238707,
    232218076, 769865249, 730641039, 616996159, 231721356, 326973501, 426068899, 722403656,
    742756734, 663270261, 364187931, 350431704, 671823672, 633125919, 226166717, 386814657,
    237594135, 451479365, 546182474, 119366536, 465211069, 605313606, 728508871, 249619035,
    663053607, 900453742, 48293872, 229958401, 62402409, 69570431, 71921532, 960467929, 537087913,
    514588945, 513856225, 415497414, 286592050, 645469437, 102052166, 163298189, 873938719,
    617583886, 986843080, 962390239, 580971332, 665147020, 88900164, 89866970, 826426395,
    616059995, 443012312, 659160562, 229855967, 687413213, 59809521, 398599610, 325666688,
    154765991, 159186619, 210830877, 386454418, 84493735, 974220646, 820097297, 2191828, 481459931,
    729073424, 551556379, 926316039, 151357011, 808637654, 218058015, 786112034, 850407126,
    84202800, 94214098, 30019651, 121701603, 176055335, 865461951, 553631971, 286620803, 984061713,
    888573766, 302767023, 977070668, 110954576, 83922475, 51568171, 60949367, 19533020, 510592752,
    615419476, 341370469, 912573425, 286207526, 206707897, 384156962, 414163604, 193301813,
    749570167, 366933789, 11470970, 600191572, 391667731, 328736286, 30645366, 215162519,
    604947226, 236199953, 718439098, 411423177, 803407599, 632441623, 766760224, 263006576,
    757681534, 61082578, 681666415, 947466395, 12206799, 659767098, 933746852, 978860867, 59215985,
    161179205, 439197472, 259779111, 511621808, 145770512, 882749888, 943124465, 872053396,
    631078482, 166861622, 743415395, 772287179, 602427948, 924112080, 385643091, 794973480,
    883782693, 869723371, 805963889, 313106351, 262132854, 400034567, 488248149, 265769800,
    791715397, 408753255, 468381897, 415812467, 172922144, 64404368, 281500398, 512318142,
    288791777, 955559118, 242484726, 536413695, 205340854, 707803527, 576699812, 218525078,
    875554190, 46283078, 833841915, 763148293, 807722138, 788080170, 556901372, 150896699,
    253151120, 97856807, 918256774, 771557187, 582547026, 472709375, 911615063, 743371401,
    641382840, 446540967, 184639537, 157247760, 775930891, 939702814, 499082462, 19536133,
    548753627, 593243221, 563850263, 185475971, 687419227, 396799323, 657976136, 864535682,
    433009242, 860830935, 33107339, 517661450, 467651311, 812398757, 202133852, 431839017,
    709549400, 99643620, 773282878, 290471030, 61134552, 129206504, 929147251, 837008968,
    422332597, 353775281, 469563025, 62265336, 835064501, 851685235, 21197005, 264793769,
    326416680, 118842991, 84257200, 763248924, 687559609, 150907932, 401832452, 242726978,
    766752066, 959173604, 390269102, 992293822, 744816299, 476631694, 177284763, 702429415,
    374065901, 169855231, 629007616, 719169602, 564737074, 475119050, 714502830, 40993711,
    820235888, 749063595, 239329111, 612759169, 18591377, 419142436, 442202439, 941600951,
    158013406, 637073231, 471564060, 447222237, 701248503, 599797734, 577221870, 69656699,
    51052704, 6544303, 10958310, 554955500, 943192237, 192526269, 897983911, 961628039, 240232720,
    627280533, 710239542, 70255649, 261743865, 228474833, 776408079, 304180483, 63607040,
    953297493, 758058902, 395529997, 156010331, 825833840, 539880795, 234683685, 52626619,
    751843490, 116909119, 62806842, 574857555, 353417551, 40061330, 822203768, 681051568,
    490913702, 9322961, 766631257, 124794668, 37844313, 163524507, 729108319, 490867505, 47035168,
    682765157, 53842115, 817965276, 757179922, 339238384, 909741023, 150530547, 158444563,
    140949492, 993302799, 551621442, 137578883, 475122706, 443869843, 605400098, 689361523,
    769596520, 801661499, 474900284, 586624857, 349960501, 134084537, 650564083, 877097974,
    379857427, 887890124, 159436401, 133274277, 986182139, 729720334, 568925901, 459461496,
    499309445, 493171177, 460958750, 380694152, 168836226, 840160881, 141116880, 225064950,
    109618190, 842341383, 85305729, 759273275, 97369807, 669317759, 766247510, 829017039,
    550323884, 261274540, 918239352, 29606025, 870793828, 293683814, 378510746, 367270918,
    481292028, 813097823, 798448487, 230791733, 899305835, 504040630, 162510533, 479367951,
    275282274, 806951470, 462774647, 56473153, 184659008, 905122161, 664034750, 109726629,
    59372704, 325795100, 486860143, 843736533, 924723613, 880348000, 801252478, 616515290,
    776142608, 284803450, 583439582, 274826676, 6018349, 377403437, 244041569, 527081707,
    544763288, 708818585, 354033051, 904309832, 589922898, 673933870, 682858433, 945260111,
    899893421, 515264973, 911685911, 9527148, 239480646, 524126897, 48259065, 578214879, 118677219,
    786127243, 869205770, 923276513, 937928886, 802186160, 12198440, 638784295, 34200904,
    758925811, 185027790, 80918046, 120604699, 610456697, 573601211, 208296321, 49743354,
    653691911, 490750754, 674335312, 887877110, 875880304, 308360096, 414636410, 886100267,
    8525751, 636257427, 558338775, 500159951, 696213291, 97268896, 364983542, 937928436, 641582714,
    586211304, 345265657, 994704486, 443549763, 207259440, 302122082, 166055224, 623250998,
    239642551, 476337075, 283167364, 211328914, 68064804, 950202136, 187552679, 18938709,
    646784245, 598764068, 538505481, 610424991, 864445053, 390248689, 278395191, 686098470,
    935957187, 868529577, 329970687, 804930040, 84992079, 474569269, 810762228, 573258936,
    756464212, 155080225, 286966169, 283614605, 19283401, 24257676, 871831819, 612689791,
    846988741, 617120754, 971716517, 979541482, 297910784, 991087897, 783825907, 214821357,
    689498189, 405026419, 946731704, 609346370, 707669156, 457703127, 957341187, 980735523,
    649367684, 791011898, 82098966, 234729712, 105002711, 130614285, 291032164, 193188049,
    363211260, 58108651, 100756444, 954947696, 346032213, 863300806, 36876722, 622610957,
    289232396, 667938985, 734886266, 395881057, 417188702, 183092975, 887586469, 83334648,
    797819763, 100176902, 781587414, 841864935, 371674670, 18247584,
];