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

• 問題: No.3394 Big Binom
• ユーザー: Today03
• 提出日時: 2025-12-02 10:01:37
• 言語: C++23 (gcc 13.3.0 + boost 1.87.0)
• 結果: WA
• 実行時間: -
• コード長: 22,791 bytes
• コンパイル時間: 3,327 ms
• コンパイル使用メモリ: 279,864 KB
• 実行使用メモリ: 7,848 KB
• 最終ジャッジ日時: 2025-12-02 10:01:42
• 合計ジャッジ時間: 4,319 ms
• ジャッジサーバーID （参考情報）: judge5 / judge3

ファイルパターン	結果
sample	AC * 4
other	AC * 9 WA * 12

ソースコード

#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,140694225,595392237,132637259,994098667,5145511,364699203,596369501,568578178,405285221,353555276,62409863,493983122,527598875,906718537,207409792,121127074,144205967,909014738,487490270,945896249,14075777,342399609,685944208,790120527,41452646,147253931,348405456,67264528,957079174,790714464,831409334,189532209,377280719,833738102,196556028,931626412,700049338,151863245,684231640,826994544,526802028,481093241,300686401,932212199,926834013,731187718,262304055,767796707,204186302,605638460,361204078,958695288,702930351,771291337,761576944,590085129,911991035,446480069,147507019,147972654,542109375,350136354,762257605,373694116,149990012,227237896,102921590,97514572,53367343,140068258,405474669,53133250,335709566,845289612,7207404,72954666,390373931,36877369,161668113,718271290,695517130,449456491,868029181,379246062,628743319,817276949,462095342,534271093,807381580,384445058,74728333,389084505,466261182,867959402,268428645,952145269,257252735,958877809,674584252,311054462,762498801,412426956,951894725,844279367,12975331,740083353,345086267,416456072,253629949,118457308,474140497,416329418,63447682,142048503,330761148,643654954,277806294,643951383,586307788,848172652,315772255,791853697,74232247,520007859,774903326,878967378,484690837,762841202,431569876,570305432,613689250,713917629,538131063,11692343,403154827,205846393,763461539,905147505,54315136,487479281,413867170,972125219,697222374,678016718,732116220,484746409,411286602,350309690,53982074,695700125,983373454,713970818,213513862,583720832,455061665,126424592,65193159,25713030,426433508,181218541,228003244,82188970,882253427,989697798,415939865,602326140,75401390,459677495,752763801,59807900,405959194,689138366,396786756,44957896,495206613,888819701,665356332,800005439,321625719,225032295,530038211,624211688,806575609,547511989,560903271,196954736,773034617,199119222,435147414,306295040,205682613,910980912,9215287,474605685,866717958,84623561,155271135,963825048,626181019,464016596,262425716,953756759,962529977,536600821,755162690,881161978,200707253,184568840,120093284,906328577,878508380,82034877,952782055,943074294,397444628,830724750,138560090,688870120,100283384,303879624,377447973,213840689,986336688,570227860,410035241,914456594,517992865,368538553,586367784,140809956,161723613,220748012,396299983,744155485,420737325,852101189,383601240,611264038,379224646,711595889,941162118,792814350,88571094,975294274,996136999,848600022,192452471,343924424,638665659,314335513,328693413,465367007,728731094,176980096,106121091,361199635,360742721,208713699,1968334,801978400,913097801,451768574,91043894,300105126,836697310,862344307,727299378,125513337,770524853,768082522,910132095,322916689,21717535,809611624,653093815,277541931,233522288,630852905,578402437,274311861,892878449,187673498,366201132,539880032,299324919,311717293,902111973,472449704,333539757,653242584,213818240,498068555,369825826,252296198,691527120,363821284,277294891,742302802,678728777,262505243,957471229,61466981,389822756,423276274,841810426,872503756,169723430,247799911,30523795,116138354,120403357,383733698,848797640,425387704,570124222,13084878,40419959,533446507,342199686,197661226,356797034,524712423,439475298,228313145,393383247,33526971,665776438,802055000,32898194,27654656,760916850,863102494,422097981,562080061,963035612,16014076,724064976,794297633,126485914,560969645,485060067,419973417,109795971,77884032,4741664,437172123,421035644,297193207,261111381,99282379,648287905,234484360,82075642,263675940,135145866,126078806,924251137,402256206,525706222,59654808,337947300,432633334,443564740,325399309,839839524,809276166,218290312,357087064,864688256,921613763,882121596,526694283,219367557,316138501,538759785,678750759,233341194,746036991,795232232,844084429,33934405,182773758,77068020,171987279,594402905,186981318,773103047,226494117,822490207,697926519,878529885,501264723,409871029,174203892,4304007,979944216,513446553,838454217,866107536,63299249,81125928,446954988,215143761,973678486,591040696,22468573,374109967,797563226,579597967,73974893,723245155,7811805,253641946,141549107,710631912,648758305,787297465,551877892,449236154,656698209,252535821,14577434,739197002,648537396,241505976,321672967,37990072,490582127,246770300,402544298,68712338,383677592,317197996,222602878,521659281,335207692,393170112,192440082,996368034,745706197,434690091,624113557,224220392,123808157,834142458,34041106,459744493,153359445,951485157,291330079,29567682,472937961,489564167,306641884,189304163,230002032,259816496,17620570,717592906,782663844,710957659,648326974,870308699,40641926,140462539,919496066,633941976,156812438,801500469,216776143,669633879,771982491,444654141,293156514,84238996,108393392,801954312,647247774,337833450,722450722,533505874,828756035,217943544,296777468,750647451,292267840,238306871,113800523,239185991,848869015,367489882,536983436,930283246,606989542,882265346,139244082,69898618,615719226,657327835,437503635,947590810,793559065,796617005,89411865,724690228,731975481,650121127,916663471,661928558,303118346,258966896,802766503,324261516,815443393,18541661,825125398,927910676,103129214,861378674,974490943,680992526,187537789,278534170,317640466,328376545,991859661,695127166,353447868,682995518,48936855,832701297,29690011,762885952,794847444,126759562,463865,313302301,980160470,277593030,756414660,649210776,658969388,779204641,480314263,335014502,754477681,989239957,969920264,857461623,234792522,393772369,950393370,173566259,9447745,779566817,219942453,68002808,896955380,723176056,100919583,648047184,961268059,690453473,257469327,473636091,256874276,547950651,602365627,202822354,332446515,385315436,820649009,122868475,852123798,702303914,931366341,381083745,363907999,402642188,567153381,761669991,829287382,659802118,316346223,942265322,204961939,783949766,892519996,956837439,200218172,903318344,409447584,617444839,413759816,986358113,511398700,466008250,525424686,536740020,434731971,488841232,201655127,720968952,527555374,75301260,534794906,526843842,673507495,711282889,856245130,762530427,774101120,290200788,316483089,629760653,456128068,558350065,304654619,14468652,992060846,903240915,895759186,572259487,535475656,848548626,391328370,192202390,570367126,378013509,433478530,602680995,461728255,102119893,603820946,624928294,848514617,857454902,938410313,497836616,397327632,102022578,781599555,33235402,387140465,897547514,325988071,853151489,983792111,949891083,831072860,54175819,274348231,544152449,244781184,675539014,557916799,350923073,495793161,282016876,588176542,527946625,707818671,614891639,399615775,170431485,396614675,602700653,970475852,933969933,617930862,250814478,142739589,450696547,481058302,494875784,72381331,490154633,733049039,464167384,152285902,187054455,620495701,953866629,211702428,188378244,292557494,872022246,754934951,407055324,448280657,793689071,937708104,188469388,114944122,630593841,403777490,662424853,234007857,68424386,561146832,209447806,331194565,582467471,187621296,306445706,831153252,436348978,266665958,544522860,112619512,933307534,495003569,915288951,314735447,138982481,993669991,743123693,166588036,532095588,410851918,736776468,378056607,995402050,938214670,694774870,875914014,741704173,509839345,920761254,908559433,600857769,199330441,226913622,49979382,236533194,36988609,47974156,111999291,4307754,739984378,867823816,543681812,341965122,751797733,731312703,219169756,785975847,926165187,610123452,965929333,625809539,192013508,478906938,124287897,208322139,744235249,765336256,214142835,1138992,631617451,158750809,607439447,875332787,36894593,813992568,114499232,351669279,987645276,681495236,107847633,891942736,600387283,170858941,155188867,696521158,413413086,138639227,591533181,532409606,918814530,897297717,830813489,189461995,729210384,211920813,205051208,267409838,444664579,42987428,814708615,335213245,54373694,460457324,893137468,238503409,462169319,576832051,86850668,239042763,55395755,753846863,533476316,94424048,492646207,247268851,226225078,156322281,901380105,978498965,789027050,701183811,177181362,620957413,968738480,960349971,305676848,63224834,639555094,583289733,984167498,33258888,685479246,282233226,221841167,506422687,592384146,215544466,230433631,349418767,555498231,356923358,420397116,695260052,697327970,154558318,46120170,412552214,210986816,962740981,880949811,461463755,975742763,615966567,329617586,7883429,597332621,849216295,55112303,830134827,292856026,89181344,814595319,255697518,17505696,527153516,483002713,186548101,396971174,833269244,904643816,758985208,768219428,680405804,256284681,314981051,152997554,831664321,596845812,772811349,44432164,477746241,630791386,95579433,754488680,467637819,506741102,68791773,920451383,619940935,713793642,811301816,426508708,772117027,632541790,871689724,783981500,647918361,590850286,206963741,141366782,441774194,527699907,80098442,822616858,82934958,344354411,793499442,61669915,337737541,44666331,388990041,954114587,810591351,160369717,959003674,924245234,865168856,887359392,886637716,636881588,856256387,153741665,14617032,189035156,610379232,821628333,197657033,517544552,691229991,712775427,75375249,417098537,551708636,460892316,785118013,557654999,563365534,450746749,416063147,131822321,901151290,583409364,548678974,284898500,383075801,59972237,757482730,376745393,82388363,443688906,618286385,586798088,46039543,66114037,485260501,781232294,68936999,465856500,664095299,824502125,447616968,324523678,563529374,504497384,215255099,401826176,564858684,551318162,941723498,488198727,832411928,18062959,824039646,576088832,325634827,336329877,340509456,388353305,201220804,133376514,163313933,604434514,260453849,250436000,532921746,115227070,189114710,249909750,268529645,374504494,822061897,723812318,630465050,365320562,115480982,55028369,475015949,734795127,246431061,10297859,145189938,372761109,685280462,694638249,777787368,83989185,900041226,539182349,682591278,15814281,108341049,51128986,340270556,779724202,161679690,2316419,418964712,728360831,11512989,19763134,984939760,886768819,788044703,16531010,434694820,367140027,149254129,910158745,573319088,809754637,706003203,431204028,489960319,809872091,371578375,507143038,60345310,611973586,653640960,498284694,589190080,128965735,704927711,190884132,893584032,867295530,127811152,187957506,860605023,581403016,408502716,218215230,986722053,641795957,55207180,783681839,49687746,205848961,26218850,550668434,685808446,317343290,746779468,18537853,545025983,568791889,748039589,312146958,836773196,931134979,321642320,496041138,837511872,706649849,313872562,413599989,32187246,541140074,186736359,901017129,577165051,134917425,211999765,370928963,927571247,51552071,14358105,973730060,435974155,415434801,250459902,853819639,534249585,245567895,99309372,774482725,360884406,324993538,134899353,562216456,948377281,173600178,759311902,196955863,756334868,571957460,718033226,859557027,513973486,733417940,673060282,872992467,401620604,438241014,376604734,584325580,913466278,626308021,149331105,677428365,250765919,619727706,106212664,108646702,439373033,106873343,528610412,222985154,48719645,522329741,396221258,236067460,210498514,234993577,485236360,96915194,300569071,598303963,734896734,947968222,811011048,79192481,721587933,499192702,314781883,671902371,720284600,57627377,392788455,396654552,686808432,238290506,623914589,698968535,173712226,565719861,488948080,912077970,703917433,222633276,891795813,317855167,505945846,879270128,233938418,779281316,298008499,955106365,728104455,691138193,798536116,308501832,883039109,705116133,431637696,80804698,725398317,448274648,47758435,847238837,899917826,520429741,126406350,557547885,693152939,94096283,338335473,497936103,248006399,924037483,192979269,939432873,306752340,57780840,726425930,760085361,424980550,384575346,285941813,75784802,960835276,824151635,19489678,29501741,393346489,379498076,2868064,778852431,160648442,565294571,184672835,556952741,341925260,975088906,410476799,508647871,574745111,386440005,566521365,657590261,242482067,516827714,648288481,166179375,406413697,347645094,906401180,646791668,961403766,647279052,846659494,330524184,89784022,254602615,733930891,680643418,789857750,120278192,631178626,311672806,83289173,3419365,767900796,528266191,21661066,668433402,316865667,869010361,546395530,93888746,337329513,874764664,326058673,7678883,764483388,595828102,357899534,57261570,814922918,639380383,810348742,476079227,472980645,825433822,671370526,67314075,107957389,558200771,224533621,491863506,214168785,975190854,154060753,329289831,359809332,115085876,708183271,899090728,63037671,770171766,338193383,733423427,357796304,885411040,710788707,480959252,623380214,812588784,374455479,860288574,936766699,286559442,786067761,99042494,816943736,257048195,118118686,667673747,32727232,446642320,233492362,23426726,369901676,263781585,623275178,482321203,467423194,808698759,473564374,933267285,686260259,571158203,303300324,931650100,906289681,948732229,902965453,214316593,96807284,419100884,451766543,551572735,347948658,25545413,370462714,346054244,446754047,522774276,571142219,420593226,272591836,830119981,902397005,704867943,647466675,808652500,676768927,873443503,546403596,271941489,269249121,45004197,258212013,946541714,470145206,942010031,627907525,58788813,76514129,601485588,109746979,889162335,366799730,629629777,123383609,942066355,430846158,69680317,902306926,590458601,200153429,28415574,515494771,630884829,354620515,366933511,638189171,211402977,786243696,643768503,885233125,256301973,627855827,750822365,427340187,190901055,33189733,964782071,266931106,474044896,691954642,811223744,865881357,602838712,817205764,103215692,108240089,867156301,324116016,139726730,589948248,776840567,406422167,34257564,899847191,334413933,670140597,100841599,818673715,742905800,854430932,211983919,747045091,814705811,565272365,898907822,948929361,552939281,876070758,293833759,88927351,605216439,53505107,533706271,760484225,287490492,140354881,398448421,504254315,624299070,875689880,743951081,508220829,170411789,749806190,80606745,259325303,503624390,300809711,963402916,956439616,389692312,317710875,813390763,583138412,739515297,838221511,184376222,371849585,827065538,745508014,837221562,422077517,321295324,226744741,327597778,60039941,892731887,992050631,983736712,543085591,492798473,397129635,35984619,484978293,793708555,354352010,326086492,399919901,404364827,280953835,451702921,182230954,482632581,356712405,542573191,452600625,81652622,895029523,496456348,997000023,800081529,803014154,365229403,934159407,440120940,163140162,541283515,808259779,589831663,135106521,836513171,614578989,1622617,434114893,699711706,650367806,9822392,391140546,270369543,95303817,48502767,353699458,483818821,384447072,807306658,122039741,940195863,122160044,996802989,129889007,335498204,493965992,351302711,394204477,976125219,575220974,946799877,411028527,205793557,197416065,617335930,210648515,263016216,960000024,700471076,434350845,418289169,87222830,182905451,43153354,607010941,749079234,390184940,394399491,94136116,597435296,31679432,345462289,946545391,630301579,809891733,901434753,969973383,901929894,892136591,757331513,631298019,407001210,366867646,604056779,477362882,4181776,920685404,478226906,213289765,121158490,531334242,258597046,54554286,295857132,422615203,506909132,525372095,810247795,656468235,24091275,905676076,884427016,32225043,494846063,20265962,626059720,380486949,94918499,115141105,316808124,27242809,32999346,827540230,351571543,888356568,252307726,204724891,700789035,63636020,215355188,198164769,634247036,608600317,48307310,664039496,723024342,151223236,84200655,52175584,166498571,529818930,25928829,533325452,289124481,975804881,223457265,22859440,618759676,591906248,253965261,157158652,81701305,546572665,239403844,572396411,699475401,77285142,466534580,519470403,491282359,293988261,22313975,851627080,424929531,359416799,317856434,128854789,990755172,390105487,84697382,334196221,735706182,961139032,21802348,576755576,477277369,769092767,188628350,765332191,379960591,611040608,30528089,695240733,710973482,172879869,914307079,783994344,84434530,175402510,354595114,705142949,612717258,713972251,526182022,673925638,520115380,856907379,983610383,110202669,886331058,667250514,771938545,872441336,829579564,712476943,107965951,970085043,414257007,59198404,33506122,872316337,796722160,29604923,583149510,183874646,814338304,504806164,903850233,902310614,718951111,554327038,745158489,641905269,995326867,52061896,616562633,902200540,227421040,395872459,135347164,988111741,92947691,768505655,400996223,473627888,275002007,804695792,288426852,55347567,847437263,710946704,318083891,107293455,18218400,92200509,839264881,704829749,66650611,743343740,350336334,241780062,179843620,179458641,767351154,346163421,149602292,774005945,997217309,86267265,803920980,224283483,67698802,814887934,145410171,31123382,931023309,363309393,300174715,343021423,564675511,383938420,687143705,872523550,269172654,618586545,765751864,700288922,439790261,788490304,878927114,634936943,447578275,659546511,596608401,484554681,801300670,102530791,945648592,276464068,855170750,207521663,84935369,954340220,141584890,814858862,297079633,870757766,636044601,748435096,224261509,328536851,712896261,435069442,698921587,571887249,414875375,231026552,360921003,245087300,429177281,762391974,56621311,357151315,568585996,679385907,939891495,412917909,792989259,827211507,480474611,509717055,134006645,36312125,238149057,914806434,578622464,895628093,934899601,898484288,312429236,846605255,852614076,99876908,355347408,336853372,606040988,434699551,157232471,811027687,929914050,46877701,56372306,691840784,890509324,146433951,594818169,838191932,786675765,47148225,495089899,635728168,238116589,543329324,648757001,410255605,517721390,348561090,284079185,721576925,823360230,247694661,973326715,130777589,183190785,189684562,7487512,177693062,94737715,52290606,778879787,319328025,748362387,169326224,479573515,336263817,263065366,462250787,653530085,55202532,79818832,254949596,244163497,586041601,782365892,183721437,466950448,641794349,726405901,468267168,928867014,642753409,826294846,73501047,597731406,288998311,162869316,282501541,671568402,557408127,566525968,210177896,804765303,696055209,663997252,876411538,101208008,650287689,79544507,495452371,413646847,47816836,911575990,994758950,734435354,78276683,692447407,992027086,645592041,172330480,938018331,831774842,684749899,627965301,126805178,194786127,285184759,393313795,358107161,126452951,848693009,18783119,220287025,737013685,864575096,527689467,109742772,196339666,424263681,448659958,606094111,362583102,857202410,914253051,631541912,917575025,5255216,267644388,839917693,43344897,98220700,106852423,626661605,748022413,360041046,270862077,66564829,3180391,742074589,143673177,864650704,302944738,396469044,159075500,733931884,86074777,527401406,556910829,259329703,37844673,288674695,352544729,232462724,134136040,945604232,3833015,781437168,723939606,189206446,635470843,147524866,690636846,488743477,818001905,160531855,583087706,237899253,144748417,747566720,600846731,211608414,324917882,676639499,318644096,542135173,621611555,410276977,240286626,867448416,330730430,531624673,102463110,469732184,839514995,503385786,656215179,162371975,241972476,907883499,283521826,598678909,874936737,627124500,957091307,103813943,861277421,92458884,488484366,170050640,700680708,87254261,588885096,64758279,613224734,175305239,155777384,937338788,4060373,280138630,555779120,286974162,733506432,331215011,779114281,255690756,562668889,579604955,37746662,205971186,876240334,73220501,986766124,249639193,923597279,897483645,422941353,240596832,68201608,415172613,380597528,588217028,647180359,920045627,521561067,938769328,30193991,699007685,633380145,432694406,268768862};

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();
}