結果

問題 No.2149 Vanitas Vanitatum
ユーザー 👑 NachiaNachia
提出日時 2022-12-21 06:15:44
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 3 ms / 2,000 ms
コード長 12,314 bytes
コンパイル時間 947 ms
コンパイル使用メモリ 87,884 KB
実行使用メモリ 4,512 KB
最終ジャッジ日時 2023-08-11 10:42:07
合計ジャッジ時間 2,206 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge14
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,380 KB
testcase_01 AC 2 ms
4,388 KB
testcase_02 AC 2 ms
4,384 KB
testcase_03 AC 2 ms
4,380 KB
testcase_04 AC 1 ms
4,384 KB
testcase_05 AC 1 ms
4,380 KB
testcase_06 AC 2 ms
4,380 KB
testcase_07 AC 1 ms
4,384 KB
testcase_08 AC 2 ms
4,508 KB
testcase_09 AC 1 ms
4,384 KB
testcase_10 AC 2 ms
4,384 KB
testcase_11 AC 1 ms
4,384 KB
testcase_12 AC 2 ms
4,380 KB
testcase_13 AC 2 ms
4,384 KB
testcase_14 AC 3 ms
4,384 KB
testcase_15 AC 2 ms
4,380 KB
testcase_16 AC 2 ms
4,380 KB
testcase_17 AC 2 ms
4,380 KB
testcase_18 AC 2 ms
4,384 KB
testcase_19 AC 2 ms
4,380 KB
testcase_20 AC 3 ms
4,384 KB
testcase_21 AC 2 ms
4,384 KB
testcase_22 AC 2 ms
4,380 KB
testcase_23 AC 3 ms
4,384 KB
testcase_24 AC 2 ms
4,384 KB
testcase_25 AC 2 ms
4,388 KB
testcase_26 AC 2 ms
4,512 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <utility>
#include <atcoder/modint>

using namespace std;
using i32 = int32_t;
using u32 = uint32_t;
using i64 = int64_t;
using u64 = uint64_t;
#define rep(i,n) for(int i=0; i<(int)(n); i++)
const i64 INF = 1001001001001001001;

using Modint = atcoder::static_modint<998244353>;



Modint I[1024];

void extend(int newN = 1000){
    std::vector<Modint> F(newN+1, Modint(1));
    std::vector<Modint> iF(newN+1, Modint(1));
    for(int i=1; i<=newN; i++) F[i] = F[i-1] * Modint::raw(i);
    iF[newN] = F[newN].inv();
    for(int i=newN; i>=1; i--) iF[i-1] = iF[i] * Modint::raw(i);
    for(int i=1; i<=newN; i++) I[i] = F[i-1] * iF[i];
}

u32 f[]={1,941747501,776540593,210672823,690071003,46617525,213768760,693968959,80489582,706932617,794151417,465499254,696674125,679081391,691448896,713797428,275558954,609927147,557311239,831274938,893291440,167105676,415665360,192812445,680052439,557094195,688128904,792752264,192208002,847923750,28263099,728717984,491684840,336918851,633366503,758306641,296930470,699020919,910172402,905192639,792232676,535935445,410591335,810793504,856039476,765650325,702144816,374640872,197994359,320889851,883115987,151590670,245098264,286989423,729221238,511226407,874957813,979489918,228248737,453190470,223927796,852989243,50287712,509033048,243625084,40159580,655302994,829942035,299277458,86622874,109276119,75894103,424113548,567421291,676588086,620367716,815463188,44143218,810930880,499782,416513770,59750787,280879191,113328955,910641127,542089438,873391271,49111081,422655771,749741439,838916518,825928836,422316600,445140078,135792920,796315921,334523653,505750213,745454889,284439669,264422227,488144299,264594887,332021570,256723915,768304408,506153085,533770970,929732704,471614028,243021423,36822049,195608626,792193516,215245367,588445499,10232161,974583034,843169718,33517339,744867256,422042779,971678608,929209828,740055526,129980885,404829672,225807005,528205456,240143253,706174821,263068586,794757329,221639463,240967815,20047837,331134934,127470054,793695956,210565051,959206504,138448490,667121261,136048183,226620404,692730832,887464126,715216840,786895056,680299255,592465564,104271019,241786040,302567286,781777622,695362768,267443112,60985765,733684226,937002588,298149860,170166008,805749567,79282620,437665466,386653062,754588014,265310082,81266867,109466639,595236940,591251736,755288980,912652888,460141120,759221877,825572784,18194464,368427783,571463817,553552793,218414240,8897606,791219964,987232136,626678298,363848504,23298153,623570515,506916981,151639897,269752482,341219264,108067268,360379612,245950594,64405509,799733966,607922664,255515653,169008059,832297534,475858276,990269468,56687032,487125465,715077943,946099639,419973380,30892688,823299765,890460664,875848715,155161884,374508954,548318802,921787093,698253774,302647199,259167661,143814525,129489686,795264610,975222339,968512986,345514813,646295751,970375323,591627665,300860854,909331562,720624591,385294700,7631741,443276555,350397413,827870055,225714870,401347161,77749271,597036959,606229862,154326026,361671183,413774614,227075193,608071418,914590447,407447508,552058576,47474609,386778642,758202478,385950691,703740000,966684774,546362027,298705630,676952658,326449356,843917452,242409430,587833706,40469219,210585234,354879640,771230526,34097422,102287772,902362543,722263693,814944322,451297925,902863475,817029670,905023960,555424886,272662632,394766353,666370092,206219158,15110235,976379739,965535222,935252937,650991646,958967237,363182237,233817196,344617468,791123841,630913138,726529184,562573003,563061146,792960341,994145576,230805329,299465420,259430953,179251015,566371622,567895990,558709601,401533746,472680587,807075382,388625548,342362854,714080723,354518461,501335155,921205714,245572383,995121871,597206529,697042204,260992104,462829184,62381294,98950871,913320293,752117967,982560320,257419215,463752698,697205827,656377881,419290152,856531770,447197724,657965581,404661208,722130014,899687713,718707067,430330393,639106400,834964009,902887941,810884366,650679669,328559029,108952421,175250094,141508696,394269300,94451378,262192347,556407145,661623397,656765174,893733886,359124883,407147338,808451311,157717476,949408897,371377907,798014486,870707644,11124205,741182897,157137689,593507555,598520569,306478687,42984407,411434960,116335798,367793469,345378248,332981554,863453067,588666836,607696540,175011207,886178571,387142464,568865780,148884679,477839356,859137664,898399404,46230887,716245342,919506383,429269215,489098767,920899704,397809292,323931347,417053198,292836984,916151861,903880874,530159990,969165939,930377972,143032010,308745688,229058228,904049457,60317698,729051789,192106544,936997143,184865547,169635803,457399664,408032575,961424900,378907963,965079378,946148009,745479287,341457669,573316525,140488077,559501368,217284569,576419480,775027508,235369686,852776706,238333284,188364228,154707197,555869026,259713631,976997327,135089920,637108313,605899300,425299135,630257864,414103956,979668540,465614154,736566528,578651185,500126788,80473976,482476368,671936429,35129612,389885031,703915264,423047129,748946352,989296698,3993118,974224703,841241239,932795359,258719575,251469715,16846321,829202764,9295132,213896299,331463491,472169457,817096142,274013552,803636696,940028364,742052578,854664711,615518321,593217956,761584448,355182187,843893299,269045370,953802150,37568955,542668251,606642174,349512365,736272199,770343238,300023457,658958330,122738470,738075352,594519714,497862531,938212102,435561555,918773761,884365386,579355058,354020897,592394585,827412134,973741053,589739172,312826770,337102791,527832013,824911332,521867730,61667222,55417785,731992906,378154470,145250909,177299477,98768957,991600964,978388836,495787634,474558986,672353832,253475753,196214303,536802012,449818931,550681984,98005228,292553790,222817032,691608599,638418413,156543041,443440271,943694930,1316251,111637293,427974745,726491902,48389379,599921716,420509798,651853658,88490275,417224036,963106927,199002083,165867002,645430252,816535156,692541078,900972774,266960681,341241584,821525955,133464546,6636983,149464497,229216326,812413066,252821803,36405236,639255352,967552244,151984988,116774694,321750932,874814096,484127291,614908099,973071400,192216885,351532941,920720784,748896212,493940100,741160184,403825582,227938660,921368915,416202451,126428415,675655870,662918350,480606683,605800134,215010628,545337822,258597915,963284809,559623501,494269864,254859157,515513147,636201689,829928735,643143037,518080555,31545149,467832290,790879519,855428672,495718360,811113878,154710394,171180624,521269077,137914848,134102954,723331664,342748417,570981210,104856274,766854145,928403164,822269089,99110539,672549046,342082754,525884032,346019232,604021771,737599117,174852240,112539187,555192840,683300128,166527270,187898829,124464213,844382245,49211224,398849114,440214295,463216192,93819707,158453464,11578188,155210899,569116690,336548398,120289318,625068414,764078412,349969756,983300879,345570633,113102141,840126473,721324662,242599519,850926608,546816577,905169045,136484042,245382335,695426142,594706487,332772667,560821012,636115343,784592400,202835456,949553775,724155645,597805696,503303067,856988979,309047421,212690671,177075959,753517341,137066106,320310578,982886218,481086669,657115889,226576254,390643181,181567228,499355976,631029765,906750169,495348425,816084819,450475224,846672840,627095773,289089534,300662272,890252965,543084796,739050888,785339461,406308098,888398339,226579305,462354756,600417550,653169897,648041290,754941779,829617766,462754894,168673211,105641891,443974269,888236349,290305659,757350402,574522890,931460682,668938271,671766461,188974769,560872757,177379310,291876563,93319741,513468406,79902386,52762654,220888658,761946441,720441759,740944491,795804685,663302465,34767568,834122280,274747984,145901430,974640559,698671345,149525820,195845535,469846335,357549060,828189195,319900459,124521364,914316246,496130688,704001460,649319045,27968158,219839565,242977494,641079385,156120792,688452662,598334659,353806514,967404727,601272627,934935916,814260781,266146398,940228669,948389718,787713716,74515967,644566859,21931132,69490732,884463579,128000299,239422352,275083780,158148417,682562033,32147436,955973916,382312128,205518544,15003321,313872451,291300083,287214908,839772587,144259933,331390207,451305085,646767988,967852396,97390722,618580054,540136488,64140208,943049052,495578535,732483530,468547260,789579598,118481583,470500283,769240075,835619831,220444455,358215033,248469429,914351548,458991521,251028379,665634977,302008471,737464526,598697328,964689926,282090512,296796108,883515395,231289592,291682007,996173017,270857754,732018381,11341328,896111866,987106841,659158800,719510287,425430293,895347465,353448341,776453626,645340587,736880412,235834456,48821076,527042662,284870981,223624224,606154734,132892765,426081112,291405288,797741757,60737990,235601319,341313631,869457955,260744788,222624201,543355906,805829873,337827985,737127494,159038730,943856042,799516113,485661889,209647561,64237599,418515222,460863758,535078334,607246618,819048901,939968472,351231922,115982991,155194614,613954471,788790780,267992811,253569052,748809821,329377705,352656550,523904938,139558687,189564007,578162302,59855380,17196544,52951027,444650259,869357808,976737524,606048462,877432165,634981065,985514670,676397969,181205870,293841787,495621860,129073181,557787161,608852229,854528467,54682000,949584604,938303529,965410296,935411254,504349291,926408335,432051917,69835089,651568992,990010023,949044875,988199503,502018396,406198306,941160724,797430576,885025562,875891317,748011372,440867620,232024063,981851613,922761564,592289177,492931260,652701094,739020341,649282186,38206020,566235476,402006168,123126309,735910600,201091962,872135798,887383729,392952149,521805418,24935599,573457148,766951395,491937850,592792669,417424347,164242226,429754560,806506632,747969409,910352581,91313813,787706358,797800468,556338062,61294602,679505964,880229108,15809981,728044191,754415667,223341063,173757788,505068818,543776033,987141132,711584656,573870412,884859775,692924402,949258578,446690415,526255226,743970871,426823635,783197103,430087279,935284810,364596630,567737782,507809810,657545692,583895526,971542947,612412719,670063301,649742047,774686353,568449098,114870353,850893687,895331872,81347340,304323425,989786170,18380681,183857839,321032144,321366217,569671551,979960121,610899947,409372276,434775126,359451158,874195761,791807002,422142660,788432649,881438979,633603142,471167390,758861816,553832542,173681614,199236091,61776243,948214315,189539151,833019507,934124486,777091618,609061201,900991416,956722240,655552466,527478770,333428136,994774443,377610676,408575434,573461739,334773713,287692255,157357638,742477328,278527879,808101817,531413565,483432276,467742124};

Modint factorial(int n){
    int m = n >> 10;
    Modint x = Modint::raw(f[m]);
    for(int i=(m<<10)+1; i<=n; i++) x *= Modint::raw(i);
    return x;
}

int cnt[1024] = {};

void hook(string s){
    vector<int> A, B;
    int a = 0, b = 0;
    for(char c : s) if(c == '0') a++;
    for(char c : s){
        if(c == '0'){ B.push_back(b); a--; }
        if(c == '1'){ A.push_back(a); b++; }
    }
    reverse(B.begin(), B.end());
    int lambda = 0;
    for(int a : A) lambda += a;
    rep(i,A.size()) rep(j,B.size()){
        if(A[i] <= j || B[j] <= i) continue;
        cnt[A[i] + B[j] - i - j - 1]++;
    }
}

int main(){
    extend();
    int N; cin >> N;
    vector<int> A(N+1); rep(i,N) cin >> A[i+1];
    string S;
    rep(i,N){
        rep(j,A[i+1]-A[i]) S.push_back('1');
        S.push_back('0');
    }

    string S2[2];
    rep(i,S.size()) S2[i%2].push_back(S[i]);
    hook(S2[0]); hook(S2[1]);
    int acnt = 0;
    Modint ans = 1;
    for(int i=1; i<=1005; i++){
        ans *= I[i].pow(cnt[i]);
        acnt += cnt[i];
    }
    ans *= factorial(acnt);

    rep(t,2) sort(S2[t].begin(), S2[t].end());

    string S3;
    rep(i,S.size()) S3.push_back(S2[i%2][i/2]);

    if(S3.find("10") != string::npos) ans = 0;
    cout << ans.val() << '\n';
    return 0;
}


struct ios_do_not_sync{
    ios_do_not_sync(){
        std::ios::sync_with_stdio(false);
        std::cin.tie(nullptr);
    }
} ios_do_not_sync_instance;
0