#1138036 (C++23) No.3394 Big Binom

• 問題: No.3394 Big Binom
• ユーザー: Today03
• 提出日時: 2025-12-02 19:09:57
• 言語: C++23 (gcc 13.3.0 + boost 1.87.0)
• 結果: AC
• 実行時間: 18 ms / 2,000 ms
• コード長: 22,822 bytes
• コンパイル時間: 2,923 ms
• コンパイル使用メモリ: 279,900 KB
• 実行使用メモリ: 7,844 KB
• 最終ジャッジ日時: 2025-12-02 19:10:01
• 合計ジャッジ時間: 4,174 ms
• ジャッジサーバーID （参考情報）: judge5 / judge1

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

ソースコード

#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0; i<n; i++)
#define all(x) (x).begin(), (x).end()
bool chmax(auto& a, auto b) { return a<b ? a=b, true : false; }
bool chmin(auto& a, auto b) { return a>b ? a=b, true : false; }
using ll=long long; const int INF=1e9+10; const ll INFL=4e18;

#ifdef DEBUG
#include "./debug.hpp"
#else
#define debug(...)
#define print_line
#endif


/// @brief ModInt
template<ll MOD>
struct ModInt {
    ModInt(ll x=0){ value=(x>=0?x%MOD:MOD-(-x)%MOD); }

    ModInt operator-() const { return ModInt(-value); }
    ModInt operator+() const { return ModInt(*this); }
    ModInt& operator+=(const ModInt& other) {
        value+=other.value;
        if(value>=MOD) value-=MOD;
        return*this;
    }
    ModInt& operator-=(const ModInt& other) {
        value+=MOD-other.value;
        if(value>=MOD) value-=MOD;
        return*this;
    }
    ModInt& operator*=(const ModInt other) {
        value=value*other.value%MOD;
        return*this;
    }
    ModInt& operator/=(ModInt other) {
        (*this)*=other.inv();
        return*this;
    }
    ModInt operator+(const ModInt& other) const { return ModInt(*this)+=other; }
    ModInt operator-(const ModInt& other) const { return ModInt(*this)-=other; }
    ModInt operator*(const ModInt& other) const { return ModInt(*this)*=other; }
    ModInt operator/(const ModInt& other) const { return ModInt(*this)/=other; }
    bool operator==(const ModInt& other) const { return value==other.value; }
    bool operator!=(const ModInt& other) const { return value!=other.value; }
    friend ostream& operator<<(ostream& os, const ModInt& x) { return os<<x.value; }
    friend istream& operator>>(istream& is, ModInt& x) {
        ll v;
        is>>v;
        x=ModInt<MOD>(v);
        return is;
    }

    ModInt pow(ll x) const { 
        ModInt ret(1),mul(value);
        while(x) {
            if(x&1) ret*=mul;
            mul*=mul;
            x>>=1;
        }
        return ret;
    }
    ModInt inv() const { return pow(MOD-2); }
    ll val() {return value; }
    static constexpr ll mod() { return MOD; }

private:
    ll value;
};

using Mod998=ModInt<998244353>;
using Mod107=ModInt<1000000007>;


using Mint=Mod998;
//----------------------------------------------------------

const int B=500000;
const vector<Mint> fac={1,832944090,373341033,797725335,45596018,400767242,834980587,248173708,623627864,45768177,428937595,938010479,442819817,79339328,499710224,280520923,833655840,488985182,83857087,541638394,295201906,590816585,788488293,920148457,671639287,376932643,849315549,816974015,597398273,124154585,813259672,217747323,732727656,218643760,244038325,63319660,122642896,971171783,310517972,926200354,160030060,925196798,483239722,414439169,683879839,532570327,712910418,388145942,384710263,581661214,433880730,173571241,844360005,403113505,513089677,783433753,101492974,80769679,959253371,118894170,957629942,447354505,678615452,736977921,34035221,649701456,56734233,159132239,524027922,468138917,31729117,592853902,102311167,636387003,330331487,994936544,8332991,64516363,832392662,549792287,545208507,583955648,594075875,282838202,318497156,246960789,859275605,961059853,300738984,973949196,767818091,94103993,864118508,344751572,878131539,139166895,316588744,952658900,812496962,3809256,213689172,621625417,584871249,47871012,980836133,934524094,54096741,247171495,417876813,913810874,363266670,331007466,335481797,733430406,730839588,972352458,393495668,571071750,435793297,397078549,760025067,683769540,811438469,311992864,720976283,959687845,650770098,254292706,586537547,592547811,117371703,111424627,566486504,269593491,749562308,183549717,708205284,173702524,932912293,3112027,939830261,205136297,983699513,128206525,206579820,819019072,301188781,32831957,593164676,553027839,770845925,500160984,247687458,281996439,41047791,824079688,266419267,592015961,937835947,566508289,506268060,417547027,6177705,752298111,936268003,911071683,166873118,86881583,443834893,732910917,328979964,907574085,470135404,781258799,954410105,629364895,117565665,777954612,832761782,910359169,39806322,886530187,478922755,778232855,394880724,970951247,821825588,811613185,468705875,310117544,512554988,820096045,232240472,194317833,876497899,782503434,356048018,249529935,895187265,376434083,808258749,946688696,575505950,405818905,68190615,135874923,939065335,234323545,552199946,854311893,694814243,255817786,385460530,934382603,529769387,972329033,640377761,177505870,916128300,267186921,440133909,325306038,362216114,271764120,826373774,223645171,502324157,43396730,457648395,153607577,385510728,841757416,904737188,949574462,78988746,613911907,454565719,298455371,623828097,384618762,686156489,384556971,713476044,346933158,63602402,115907565,570334625,563518607,681055904,356545546,222059821,936711084,477211096,441562317,343363294,554515045,833792655,568547002,461853093,552194509,741797144,562294304,74731896,111323216,930484262,115224037,268372735,372253810,941222802,242955420,677432735,135949777,474842829,196903079,700451655,641712098,400176109,357463193,697644778,235378409,390377694,337794938,790010794,343574671,360642718,676879599,505712943,729394427,946647976,734019573,339045014,131024043,715797300,846126190,251680896,580182727,70091750,4026311,40517433,887571270,12629586,616055244,850635539,148148705,110877109,450504243,571935891,22972802,695965747,390170340,634938288,314155550,69072133,405109385,155093216,782455383,749696762,945486010,963086402,152382421,544711799,524660433,724471925,281441289,334646013,362590988,574791029,707907771,722417626,749411690,377929821,195477693,743946412,504766652,988034679,806194461,405207112,793140734,18063742,573002996,104121967,604995871,638607426,17072522,607304611,573260625,751377777,249313873,35834555,859063290,313632531,537713022,18058363,460292716,656121134,430685260,40763559,945185707,562910912,560197516,495867250,565674543,48767038,765087730,210864657,653182925,659137294,607587840,715390025,943978614,865854329,73829568,324322857,820659294,388911184,599853934,286059202,689085284,636456178,144083321,421290700,499504831,832276048,161469854,726437551,139587306,526417714,287164086,252522639,695170959,386147469,763409373,674313019,89579335,274769381,379123792,226519400,500852683,272047186,482955274,117153405,699472685,712896591,572034017,486826649,407044692,119444874,182246631,338909703,180314221,18536028,604083278,41814114,205703813,245606459,938935679,140617938,431422340,250512392,534716559,57084755,529636454,157807456,799116522,261113192,200339866,40258068,258443815,194807105,99248981,325341339,318312497,884328111,366531168,896332013,229760327,880836012,272306426,737358206,639927681,202713771,319166486,785454372,65470108,399586250,258813464,485457499,267340023,640827004,286201406,546969497,675156986,749602473,381868041,159788463,976103033,159111724,20605854,218592929,676071811,675932866,352848238,314795475,469317129,811539323,266969472,246883213,894844836,696818315,441058799,759880589,819694816,4302336,127908138,353070689,135880356,477909706,747005383,559289160,454617564,79781699,715992834,878094972,3849298,840903973,876102344,367416824,458856366,973366814,319621069,848259019,905381092,462421750,74246228,667227759,630633017,897917455,454054685,81800722,120666251,956276337,398569237,942686845,808829439,420541799,379813641,417005912,210349085,272641764,898565465,941778993,442269270,217214373,234914626,192220616,745889478,267901132,489378896,50530621,943521477,652678397,16975850,354880856,860890895,164289049,958701621,781023184,657571756,105376215,8281998,315094878,283594293,607856504,989696784,733905911,332768246,457743498,515265905,992735713,852022418,35212756,974318096,231822660,500589169,276036750,240244823,734558079,453159002,424180850,558171578,433186147,741188054,308380947,175201678,18333316,431826926,12935086,320892230,351491725,667607812,655645460,46130651,535812389,992721148,521902115,273864146,67016984,460430046,48682076,909939621,64748124,87472057,489360447,745772016,361275315,578237795,786336279,405604940,805161272,185738240,468129309,55463513,645091350,919253966,887284732,144656392,913004502,283677534,358814684,224223399,281295633,712469410,328970139,539007390,395955130,438202728,164840186,712765876,820902807,988813626,761699708,699586874,246274415,953811386,592331769,718153724,913846362,637484334,866682684,383641732,600130702,56937956,903837674,890994178,529462989,238722354,90612675,856087886,526540127,491257181,533047427,345620144,110008879,193503980,674279751,850968717,801920753,614450034,645226926,194215392,676886948,37084690,752481486,104380130,474034007,224568724,457790341,657787665,166813684,43491027,287671032,770930721,188118664,142841178,244731384,984665638,404032157,810784829,269766986,218143896,423996017,15377221,182948540,563376927,356801634,841283169,737863144,304304531,652014069,292379530,206068022,779392398,504569410,794071584,919894484,564897051,593398649,627020578,963768176,76638918,882517476,829179397,702523597,695277052,949028249,985720687,128957299,860803109,171997372,772578472,50865043,332271173,20937461,640989391,690959202,339419587,581356488,267254444,369182214,469924989,993580422,514613891,193500140,483893912,540665426,676354191,365786018,81284878,743731625,855433507,144980423,278831849,979536721,680983918,773259009,601439171,617053935,433343609,247670131,330472656,843705280,385010920,30419459,68413389,985463402,865887787,261585206,181757036,237885042,371933483,111276893,577307350,488166208,378042900,137660292,73038186,720784236,414303786,244467770,191352133,26368504,481122132,792857103,598912935,666885724,478141716,670313309,235930496,905683034,506720558,259415897,556236929,512017253,555826384,826265493,793500995,111960112,497524572,633652060,237267936,918048438,570980543,516432938,907627672,386972415,197441299,996212724,768149574,610073831,671440529,444094191,636153946,72480267,158914543,665038087,108098721,11584804,549526920,301029012,149601896,723617861,974049138,113763819,226679934,778259899,651352198,937766095,496660349,535448641,582931632,593907889,913417823,783573565,83841128,673298635,753949576,599533244,469235245,655712590,918047155,173350007,884348235,868198597,499762681,169013813,106991774,585161712,402625656,697502214,733293086,573994984,199277726,285943986,112626357,675831407,851890897,3134056,404842178,965907646,522281121,401920943,464052112,665949756,773072522,236277883,22635007,612745912,136520896,813282113,18029104,892454686,130554895,901222267,141719810,624900982,939871132,927122298,558939036,686321335,643220541,84924870,517813266,927606072,690048406,506664166,569780495,353631992,561778544,165913238,440306227,566073550,549913601,816674343,123123616,864877926,654814082,171259407,738659199,908752311,516752706,874007723,981914153,803597299,226123130,613676466,253259031,880336545,252446209,282280109,353376084,128761001,533037542,58852065,328414620,474075900,763600065,434816091,594892791,364856903,569427230,149123648,640376329,388854780,658821659,314693916,66875096,423183826,31679515,419733481,898931104,888483202,833683001,238933227,911768047,336564048,777432642,757103493,676927696,100189123,347584166,855479832,714981380,51370348,659988891,403061033,318426902,496971759,161762682,831753030,515639881,251718753,165764458,272779384,216602020,683379259,940963861,488844621,929656934,881783783,283669437,659478190,406514898,445719559,572363270,740782647,668145434,546525906,282162992,985524427,502627130,548033568,377302156,333772553,178097451,331916427,628227429,752533273,685294755,730387628,194878869,93829695,953921783,655989476,894080888,930661318,139454535,334885743,938849953,466041862,636669802,428105027,655571802,888238707,511656834,232218076,243623833,769865249,62937819,730641039,932665093,616996159,665881400,231721356,228896235,326973501,106306760,426068899,695319633,722403656,238503495,742756734,442409213,663270261,672778417,364187931,322321698,350431704,590154831,671823672,187377827,633125919,636960214,226166717,216810256,386814657,312901043,237594135,207682764,451479365,570845386,546182474,882390793,119366536,483341379,465211069,586993270,605313606,75997138,728508871,357332913,249619035,492786580,663053607,359293168,900453742,598232132,48293872,634854021,229958401,600637177,62402409,876634467,69570431,321955188,71921532,944493710,960467929,350793545,537087913,214171146,514588945,916211253,513856225,607675257,415497414,431465317,286592050,42170635,645469437,431078364,102052166,861424676,163298189,945972149,873938719,927383833,617583886,154379305,986843080,369072251,962390239,314105314,580971332,533669323,665147020,790623469,88900164,805066551,89866970,144845964,826426395,813075905,616059995,524177144,443012312,573689501,659160562,419971454,229855967,568913884,687413213,888793284,59809521,144904536,398599610,384148068,325666688,74984693,154765991,347631844,159186619,863055215,210830877,847213386,386454418,154109583,84493735,549236112,974220646,224142228,820097297,264002620,2191828,668866476,481459931,829298212,729073424,795732739,551556379,197131075,926316039,240310961,151357011,459774415,808637654,729575642,218058015,74875198,786112034,517132007,850407126,263886490,84202800,954440955,94214098,562688140,30019651,694354242,121701603,242555109,176055335,74756157,865461951,875307217,553631971,704530114,286620803,450131129,984061713,163614016,888573766,572712620,302767023,658966747,977070668,784520396,110954576,443769168,83922475,96268554,51568171,458260906,60949367,112299483,19533020,142997677,510592752,587546203,615419476,44573952,341370469,426627450,912573425,854018206,286207526,717503712,206707897,947490708,384156962,810382327,414163604,297496275,193301813,704178218,749570167,989500285,366933789,712680771,11470970,571323306,600191572,145201581,391667731,57244308,328736286,463264880,30645366,871213346,215162519,99088082,604947226,194598619,236199953,721437863,718439098,755906638,411423177,468211039,803407599,992887653,632441623,763167849,766760224,160769664,263006576,542760732,757681534,278553376,61082578,824103006,681666415,653688431,947466395,986338640,12206799,896249745,659767098,969471438,933746852,377167213,978860867,127688605,59215985,260432233,161179205,971163184,439197472,235577085,259779111,504454934,511621808,128294878,145770512,418299073,882749888,75096516,943124465,879782782,872053396,241283855,631078482,85050758,166861622,289498325,743415395,58593262,772287179,576239933,602427948,97637,924112080,772336195,385643091,140864383,794973480,451306513,883782693,300807531,869723371,232575329,805963889,611685962,313106351,813728268,262132854,576463104,400034567,357452818,488248149,520254156,265769800,789603936,791715397,883026008,408753255,891804478,468381897,732060187,415812467,441007152,172922144,505406671,64404368,538391322,281500398,628193651,512318142,280451497,288791777,867347500,955559118,902806182,242484726,703029737,536413695,285606138,205340854,548415110,707803527,69317309,576699812,493700595,218525078,75341419,875554190,306461604,46283078,768664924,833841915,959534504,763148293,903932923,807722138,590777804,788080170,226667442,556901372,765325938,150896699,488713659,253151120,969372918,97856807,873971293,918256774,515956797,771557187,906639585,582547026,643354764,472709375,286575093,911615063,348838489,743371401,690955997,641382840,651752957,446540967,455010247,184639537,269440836,157247760,746724586,775930891,709808375,939702814,788029239,499082462,35012191,19536133,424534614,548753627,203949090,593243221,590720525,563850263,587958946,185475971,70072720,687419227,415172563,396799323,929589707,657976136,518653538,864535682,229489740,433009242,677157394,860830935,527283602,33107339,640040635,517661450,903090976,467651311,61482516,812398757,126119506,202133852,626243916,431839017,30764380,709549400,422849768,99643620,621088888,773282878,12353400,290471030,363286435,61134552,99573160,129206504,627085963,929147251,722271113,837008968,113530136,422332597,359110992,353775281,950730177,469563025,850494290,62265336,991960449,835064501,535962057,851685235,125989194,21197005,916796988,264793769,70235875,326416680,794540714,118842991,920829832,84257200,118313891,763248924,287382235,687559609,70194888,150907932,792628065,401832452,72696396,242726978,308434049,766752066,613819068,959173604,792070838,390269102,648239805,992293822,438901650,744816299,259108485,476631694,485373441,177284763,874130302,702429415,980717464,374065901,14486009,169855231,954060265,629007616,808411597,719169602,410540656,564737074,413493712,475119050,603008600,714502830,432435464,40993711,915987858,820235888,78279913,749063595,133409849,239329111,424794013,612759169,194927803,18591377,207625120,419142436,737561937,442202439,524358084,941600951,532235909,158013406,718963971,637073231,355627316,471564060,848047960,447222237,540460268,701248503,199849979,599797734,274443446,577221870,958558474,69656699,137556046,51052704,841145308,6544303,100508770,10958310,152326611,554955500,551940618,943192237,624952423,192526269,79391333,897983911,29347815,961628039,751666318,240232720,203966976,627280533,215903295,710239542,947934816,70255649,430974582,261743865,964933732,228474833,738197286,776408079,129094583,304180483,369537169,63607040,146358489,953297493,248761804,758058902,875608190,395529997,51471616,156010331,317581002,825833840,906041802,539880795,846058959,234683685,566909819,52626619,819627703,751843490,868467550,116909119,861830114,62806842,380191330,574857555,777612598,353417551,928962761,40061330,353738850,822203768,616224373,681051568,866566664,490913702,630336296,9322961,849854078,766631257,879838585,124794668,268727506,37844313,713102539,163524507,6536694,729108319,577365574,490867505,531660978,47035168,341088739,682765157,793397527,53842115,735784685,817965276,69645122,757179922,289521830,339238384,122694810,909741023,911509636,150530547,520210984,158444563,705468244,140949492,495029674,993302799,745585889,551621442,881731169,137578883,683040308,475122706,21908198,443869843,178550999,605400098,220223011,689361523,154128302,769596520,369263442,801661499,771805796,474900284,346214479,586624857,259219303,349960501,467368547,134084537,561986588,650564083,722467548,877097974,879570065,379857427,878784506,887890124,887968451,159436401,504313530,133274277,132457214,986182139,977025645,729720334,625149025,568925901,844597019,459461496,648096519,499309445,510564866,493171177,852090799,460958750,754849650,380694152,501166149,168836226,760297935,840160881,200290370,141116880,351409385,225064950,633873299,109618190,537975758,842341383,42684759,85305729,305345783,759273275,127229302,97369807,606238693,669317759,278296050,766247510,14051646,829017039,584610845,550323884,986199246,261274540,219510663,918239352,669587379,29606025,725983275,870793828,934652736,293683814,547670789,378510746,323628232,367270918,510909602,481292028,84208501,813097823,553377471,798448487,330227749,230791733,130537808,899305835,331295319,504040630,744390132,162510533,91183628,479367951,959375773,275282274,933252761,806951470,938378265,462774647,624756736,56473153,243468006,184659008,134732093,905122161,90597350,664034750,701433973,109726629,422672761,59372704,371842703,325795100,879735257,486860143,364631219,843736533,532114185,924723613,311231611,880348000,893814294,801252478,799021637,616515290,154244414,776142608,12894694,284803450,648248002,583439582,105626741,274826676,350219412,6018349,224210347,377403437,977176210,244041569,880732199,527081707,170088331,544763288,587724314,708818585,456899308,354033051,675134280,904309832,608505398,589922898,120731582,673933870,297650137,682858433,43267678,945260111,455509925,899893421,276680248,515264973,965971682,911685911,599954960,9527148,809365740,239480646,432788204,524126897,224242249,48259065,937940242,578214879,315538394,118677219,717413522,786127243,201364998,869205770,685701838,923276513,22661180,937928886,712026665,802186160,409004619,12198440,477570851,638784295,472420575,34200904,568826986,758925811,406342250,185027790,712956038,80918046,107802869,120604699,208423940,610456697,188593474,573601211,612977481,208296321,69524477,49743354,248182844,653691911,387527440,490750754,419566619,674335312,544942573,887877110,366590755,875880304,577607916,308360096,512490361,414636410,989600520,886100267,633434380,8525751,629537985,636257427,97883085,558338775,555172579,500159951,975532493,696213291,238704768,97268896,935624632,364983542,43833943,937928436,401635065,641582714,851230991,586211304,900172686,345265657,639814846,994704486,460142734,443549763,965382691,207259440,867382019,302122082,431045102,166055224,606568169,623250998,779897975,239642551,562420988,476337075,322299361,283167364,900553488,211328914,958658813,68064804,148327449,950202136,279470421,187552679,839421428,18938709,370668130,646784245,852945387,598764068,139153545,538505481,187626070,610424991,582032810,864445053,140893630,390248689,867887278,278395191,537837148,686098470,365583126,935957187,747195604,868529577,464237075,329970687,538185762,804930040,397562365,84992079,705532089,474569269,494642313,810762228,559306458,573258936,143578303,756464212,370157205,155080225,285362799,286966169,22001749,283614605,357468496,19283401,313939916,24257676,47976991,871831819,351691470,612689791,880636943,846988741,736638505,617120754,89052476,971716517,186215888,979541482,49247576,297910784,521729071,991087897,693488631,783825907,711222581,214821357,521816469,689498189,968768328,405026419,610012445,946731704,1336042,609346370,120377260,707669156,698229642,457703127,93340818,957341187,744949037,980735523,485417410,649367684,590663983,791011898,369686170,82098966,218627188,234729712,35123793,105002711,980949004,130614285,765321315,291032164,342545023,193188049,524038183,363211260,399373715,58108651,158668444,100756444,114822924,954947696,98791230,346032213,878845644,863300806,441620337,36876722,10210384,622610957,617410196,289232396,709192917,667938985,949210359,734886266,740840102,395881057,756771073,417188702,572315740,183092975,877030530,887586469,187976276,83334648,551037440,797819763,660202270,100176902,597161024,781587414,523857854,841864935,393306928,371674670,171840014,18247584};

Mint factrial(ll n) {
    int bi=n/B;
    Mint ret=fac[bi];
    for(ll i=bi*B+1; i<=n; i++) ret*=i;
    return ret;
}

Mint comb(ll n, ll k) {
    Mint ret=factrial(n);
    ret/=factrial(k);
    ret/=factrial(n-k);
    return ret;
}

Mint comb_naive(ll n, ll k) {
    if(k>n-k) return comb_naive(n,n-k);
    Mint ret=1;
    for(ll i=1; i<=k; i++) {
        ret*=n+1-i;
        ret/=i;
    }
    return ret;
}

void solve() {
    ll N,K; cin>>N>>K;

    if(N>=998244353) {
        if(max(K,N-K)<998244353) cout<<0<<endl;
        else cout<<comb_naive(N,K)<<endl;
    }
    else cout<<comb(N,K)<<endl;
}

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    //cout<<fixed<<setprecision(15);
    int T=1; //cin>>T;
    while(T--) solve();
}