結果
| 問題 | No.2149 Vanitas Vanitatum |
| ユーザー |
👑  p-adic
|
| 提出日時 | 2022-12-07 12:22:24 |
| 言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
AC
|
| 実行時間 | 4 ms / 2,000 ms |
| コード長 | 15,601 bytes |
| コンパイル時間 | 3,263 ms |
| コンパイル使用メモリ | 221,684 KB |
| 実行使用メモリ | 6,944 KB |
| 最終ジャッジ日時 | 2024-04-27 04:19:07 |
| 合計ジャッジ時間 | 3,455 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge3 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 2 ms
6,816 KB |
| testcase_01 | AC | 1 ms
6,944 KB |
| testcase_02 | AC | 2 ms
6,940 KB |
| testcase_03 | AC | 2 ms
6,940 KB |
| testcase_04 | AC | 1 ms
6,940 KB |
| testcase_05 | AC | 1 ms
6,944 KB |
| testcase_06 | AC | 1 ms
6,940 KB |
| testcase_07 | AC | 2 ms
6,940 KB |
| testcase_08 | AC | 2 ms
6,940 KB |
| testcase_09 | AC | 2 ms
6,940 KB |
| testcase_10 | AC | 2 ms
6,940 KB |
| testcase_11 | AC | 2 ms
6,940 KB |
| testcase_12 | AC | 2 ms
6,940 KB |
| testcase_13 | AC | 2 ms
6,944 KB |
| testcase_14 | AC | 2 ms
6,940 KB |
| testcase_15 | AC | 2 ms
6,940 KB |
| testcase_16 | AC | 2 ms
6,944 KB |
| testcase_17 | AC | 2 ms
6,944 KB |
| testcase_18 | AC | 2 ms
6,944 KB |
| testcase_19 | AC | 2 ms
6,940 KB |
| testcase_20 | AC | 2 ms
6,940 KB |
| testcase_21 | AC | 1 ms
6,940 KB |
| testcase_22 | AC | 3 ms
6,940 KB |
| testcase_23 | AC | 2 ms
6,940 KB |
| testcase_24 | AC | 2 ms
6,940 KB |
| testcase_25 | AC | 2 ms
6,940 KB |
| testcase_26 | AC | 4 ms
6,944 KB |
ソースコード
#pragma GCC optimize ( "O3" )
#pragma GCC target ( "avx" )
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define TYPE_OF( VAR ) remove_const<remove_reference<decltype( VAR )>::type >::type
#define UNTIE ios_base::sync_with_stdio( false ); cin.tie( nullptr )
#define CEXPR( LL , BOUND , VALUE ) constexpr const LL BOUND = VALUE
#define CIN( LL , A ) LL A; cin >> A
#define ASSERT( A , MIN , MAX ) assert( MIN <= A && A <= MAX )
#define CIN_ASSERT( A , MIN , MAX ) CIN( TYPE_OF( MAX ) , A ); ASSERT( A , MIN , MAX )
#define FOR( VAR , INITIAL , FINAL_PLUS_ONE ) for( TYPE_OF( FINAL_PLUS_ONE ) VAR = INITIAL ; VAR < FINAL_PLUS_ONE ; VAR ++ )
#define FOREQ( VAR , INITIAL , FINAL ) for( TYPE_OF( FINAL ) VAR = INITIAL ; VAR <= FINAL ; VAR ++ )
#define REPEAT( HOW_MANY_TIMES ) FOR( VARIABLE_FOR_REPEAT , 0 , HOW_MANY_TIMES )
#define QUIT return 0
#define COUT( ANSWER ) cout << ( ANSWER ) << "\n";
#define RETURN( ANSWER ) COUT( ANSWER ); QUIT
#define POWER_MOD( ANSWER , ARGUMENT , EXPONENT , MODULO ) \
TYPE_OF( ARGUMENT ) ANSWER{ 1 }; \
{ \
TYPE_OF( ARGUMENT ) ARGUMENT_FOR_SQUARE_FOR_POWER = ( MODULO + ( ARGUMENT ) % MODULO ) % MODULO; \
TYPE_OF( EXPONENT ) EXPONENT_FOR_SQUARE_FOR_POWER = ( EXPONENT ); \
while( EXPONENT_FOR_SQUARE_FOR_POWER != 0 ){ \
if( EXPONENT_FOR_SQUARE_FOR_POWER % 2 == 1 ){ \
ANSWER = ( ANSWER * ARGUMENT_FOR_SQUARE_FOR_POWER ) % MODULO; \
} \
ARGUMENT_FOR_SQUARE_FOR_POWER = ( ARGUMENT_FOR_SQUARE_FOR_POWER * ARGUMENT_FOR_SQUARE_FOR_POWER ) % MODULO; \
EXPONENT_FOR_SQUARE_FOR_POWER /= 2; \
} \
} \
// 通常の二分探索
#define BS( ANSWER , MINIMUM , MAXIMUM , EXPRESSION , TARGET ) \
ll ANSWER = MAXIMUM; \
{ \
ll VARIABLE_FOR_BINARY_SEARCH_L = MINIMUM; \
ll VARIABLE_FOR_BINARY_SEARCH_U = ANSWER; \
ll VARIABLE_FOR_DIFFERENCE_FOR_BINARY_SEARCH = ( TARGET ) - ( EXPRESSION ); \
if( VARIABLE_FOR_DIFFERENCE_FOR_BINARY_SEARCH == 0 ){ \
VARIABLE_FOR_BINARY_SEARCH_L = ANSWER; \
} else { \
ANSWER = ( VARIABLE_FOR_BINARY_SEARCH_L + VARIABLE_FOR_BINARY_SEARCH_U ) / 2; \
} \
while( VARIABLE_FOR_BINARY_SEARCH_L != ANSWER ){ \
VARIABLE_FOR_DIFFERENCE_FOR_BINARY_SEARCH = ( TARGET ) - ( EXPRESSION ); \
if( VARIABLE_FOR_DIFFERENCE_FOR_BINARY_SEARCH == 0 ){ \
VARIABLE_FOR_BINARY_SEARCH_L = ANSWER; \
break; \
} else { \
if( VARIABLE_FOR_DIFFERENCE_FOR_BINARY_SEARCH > 0 ){ \
VARIABLE_FOR_BINARY_SEARCH_L = ANSWER; \
} else { \
VARIABLE_FOR_BINARY_SEARCH_U = ANSWER; \
} \
ANSWER = ( VARIABLE_FOR_BINARY_SEARCH_L + VARIABLE_FOR_BINARY_SEARCH_U ) / 2; \
} \
} \
} \
\
inline vector<int> Difference( const vector<int>& A )
{
int size = A.size();
vector<int> answer{};
if( size == 0 ){
return answer;
}
answer.push_back( A[0] );
FOR( i , 1 , size ){
answer.push_back( A[i] - A[i-1] );
}
return answer;
}
inline vector<int> inv_Difference( const vector<int>& A )
{
int size = A.size();
vector<int> answer{};
int sum = 0;
FOR( i , 0 , size ){
answer.push_back( sum += A[i] );
}
return answer;
}
inline CEXPR( ll , bound , 1000 );
inline string to_bit( const vector<int>& A )
{
int size = A.size();
string answer{};
static const string zero = "0";
FOR( i , 0 , size ){
answer += string( A[i] , '1' );
answer += zero;
}
return answer;
}
inline vector<int> inv_to_bit( const string& A , const int& r )
{
int size = A.size();
vector<int> answer{};
int i_start = 0;
int i = 0;
int i2r = r;
while( i2r < size ){
if( A.substr( i2r , 1 ) == "0" ){
answer.push_back( i - i_start );
i_start = i + 1;
}
i++;
i2r += 2;
}
return answer;
}
int main()
{
UNTIE;
CIN_ASSERT( N , 1 , bound );
vector<int> A{};
int Ai_prev = 1;
ll sum_A = 0;
REPEAT( N ){
CIN_ASSERT( Ai , Ai_prev , bound );
A.push_back( Ai_prev = Ai );
sum_A += Ai;
}
string A_bit = to_bit( Difference( A ) );
vector<int> B_dif[2] = { move( inv_to_bit( A_bit , 0 ) ) , move( inv_to_bit( A_bit , 1 ) ) };
vector<int> B[2] = { move( inv_Difference( B_dif[0] ) ) , move( inv_Difference( B_dif[1] ) ) };
int sum_B[2] = {};
FOR( d , 0 , 2 ){
int& sum_B_d = sum_B[d];
vector<int>& B_d = B[d];
int size_B_d = B_d.size();
FOR( i , 0 , size_B_d ){
sum_B_d += B_d[i];
}
}
ll sum_B_01 = sum_B[0] + sum_B[1];
if( sum_B_01 * 2 != sum_A ){
RETURN( 0 );
}
CEXPR( ll , P , 998244353 );
// 前計算
// CEXPR( ll , bound2 , bound * bound );
// ll factorial_current = 1;
// cout << "{" << factorial_current;
// FOREQ( i , 1 , bound2 ){
// ( factorial_current *= i ) %= P;
// if( i % bound == 0 ){
// cout << "," << factorial_current;
// }
// }
// cout << "};";
ll factorial[bound + 1] = {1,421678599,421897391,201761277,975751463,779957103,811023346,77283583,230436398,202725520,777990065,658971441,535841686,899997958,561691914,335637931,311994785,171957212,872342036,183347899,766786010,299387596,700950120,557992731,841841596,663187109,900860030,168379707,378353235,712393996,512513096,254006230,89776222,254335821,480253064,250423118,724424295,343641911,693419952,763338707,705983787,832815587,784917336,291493057,684317176,166434408,769590242,158584196,249454012,573153214,734256002,352559112,53220578,485942388,949917099,989270228,60396366,282045022,979110144,689558463,244148993,857321500,443477891,419375715,57485441,602145528,668684803,299054125,200809269,119136438,533292028,494124292,909146263,701969836,946239080,248563501,533148765,800546409,588321487,668220045,210582481,177571511,145668625,357777890,703821475,441608988,816061365,419086708,720070615,446886271,688517539,481982141,782602264,27392992,173649229,540285475,137535234,212960261,955951013,41124263,215582594,330168107,768338011,731249850,934170518,971401091,546231112,853484939,380221490,186935812,14820617,707752257,724533551,911446528,422010819,240962051,176612261,34166931,524591154,354495218,129246395,321138156,511588376,949113297,585768021,39512857,584947644,188510542,129980885,815424910,150625187,794813567,251620428,478643293,579901970,930392139,270038191,751741663,492834958,471614670,86672976,938153878,765345844,50091135,864306267,579405346,9045244,618366320,709034272,961375931,764239242,892722022,244905002,253062836,728556724,104026264,506346610,917281823,901828100,238525271,21874704,168638220,647209250,730768279,426659130,874354593,736907116,877499431,829760151,557059516,57288446,987552536,215428490,150951833,886840242,622797582,919921121,974019893,165239668,673148008,850657009,771668738,444894901,431816332,161979166,502870144,374350995,740115545,501262987,86948451,774583782,659464066,811492921,12298863,408193890,678200842,4225205,976589688,734074699,595940044,638474417,250192629,524016245,481703903,347459767,135803799,296393492,853533694,861645144,513986312,128284758,82421553,975414757,794412966,497846530,489257203,464640625,51378125,382252956,267348394,786368753,275779213,265887160,351489322,516134909,499852368,193429198,730607813,348646378,74836084,472986042,615464186,250367363,343669928,267234739,924895817,780542896,83867622,771007334,351538985,103549395,351817096,702434719,67828542,443814994,922954052,49191889,169745560,964515733,25967732,495451255,633639471,82026208,750269260,948798692,802658201,47474609,756769809,95340122,520776890,264078536,19340365,410870176,918549864,309261371,676344761,414122357,983288184,430377561,446891073,433635135,614318761,325224960,782743350,814050222,712190695,712855736,329833646,507826796,224868552,625262204,93164986,910223899,449953048,171589300,729323490,584586528,911006138,938900082,928396312,766766525,821007666,770464550,607531836,431226082,204595061,121285825,44193136,94976999,567086801,185226044,196667474,195109303,557445350,361536782,710596105,361755804,232380890,882179668,243254334,35932350,754288736,62286712,356070990,649866538,956177070,83346559,694156180,603141919,585208358,902168850,306659171,852650131,717812235,964374461,952764509,603902980,200354342,232360575,56238,455715166,976316122,410467403,374922710,801632633,731183756,229909332,771349191,139413297,616044762,218641259,856279572,261351197,615980223,745077177,107855499,883218073,551550920,229265039,561069894,972559028,661952009,533564073,265114678,767021612,213735112,122093041,393975179,120912557,879809476,640480499,720782780,711149796,367795291,654739122,525106737,197794233,555270481,192432996,16381385,206662314,532251158,302594460,766823690,566609318,76393737,831868900,727633170,468526310,567220062,683003246,747974225,717553382,773252694,607696540,169774756,548398730,94269934,596461726,961178585,923831102,438492267,887639871,374342279,630711843,447952131,261522976,199400045,842150002,512634028,876712294,578129756,709688266,588052298,324983231,477822042,774661833,938211304,907952749,108704413,724261094,705733280,411764688,174016609,825415245,158297458,856743968,506646665,689841498,427335092,408525348,125600946,732997090,415527963,164742409,114188120,436451755,450302344,115081646,983140002,763874992,406849677,955425167,592788131,382496831,879009134,835994417,452604836,651004830,315599780,547233394,759558977,248770047,698913755,106533239,356419815,155640407,539228802,804079539,868067625,109140246,844084681,687204050,386626575,730453482,65882917,852432203,666769578,275841476,177502968,300634900,387444360,106384964,339969399,254191128,99807036,208368872,42676771,145645731,444360778,256419515,969708497,452550117,349428902,433860503,668301859,197620362,716603123,665870049,618032392,371584155,506315330,618325469,984072630,647251727,636138261,388908561,344980056,852663314,349455490,276107980,435835353,491773394,606451485,689311382,694382319,279585805,771264188,231486827,592632950,832944090,859431938,445575464,44209922,680527105,22533413,883870744,395051341,723970056,455254097,540250216,356459641,527832013,722098577,686021893,673861840,486250798,995431637,696814345,302834610,893651744,529547487,611526426,101544850,812481884,278487759,70592471,931860306,130495309,164490752,936348937,814985429,264792610,252606640,403718858,860257894,119083440,480532678,954426667,744124459,326512726,367365905,454960817,777692148,236794842,335815225,644418312,850173499,243027886,540550713,516396135,607856947,139728260,718469529,565616181,27825421,136681964,529173337,182158160,177719476,843656716,911856813,657605179,528448199,464391613,343741298,229812466,899470214,559664837,967400881,776879789,103570228,824041317,159066458,862916931,452284117,934613922,602934978,131054087,289242567,359802705,636972072,997266795,108956484,561554546,280707977,1821367,781468309,585878809,245611883,356307409,931606245,838511743,23936396,918150738,259244730,856249495,961290301,804818093,225686426,949283602,864988450,208562210,218998710,520936288,943472786,476549806,90138172,743970018,885271575,121678346,586197923,82800689,399537521,333087267,146672150,218734938,988694802,278109992,617242571,755038370,568080889,119790231,265058911,440857453,777742346,243246376,748539366,800248168,106281262,144825638,891041691,752733536,91631993,327271331,897972505,616624596,655934837,791097655,699418307,398849114,496979430,852597203,437240858,498243677,259785107,207547436,166957229,165650317,644412854,243664371,452527412,514259598,29207504,622003012,619111787,153402563,622646972,537787046,20131999,157125107,962991071,195513390,178220783,435189858,951527810,880723573,381841693,775739742,612592396,752722108,133569109,184239633,410462336,651376746,11414374,300880259,819686744,981012454,126639316,971617941,7518369,756198666,621351958,362099126,541294570,855897390,441709265,726200155,256841522,787502726,73149479,912014425,894019208,606878657,221918459,193234972,446058386,782519496,557580561,951610819,755255964,738001955,767174341,745316260,465275010,633742488,379276457,253296837,783732370,720346213,439673190,104106143,587055656,539062660,594898465,197901771,970341953,682485798,375325046,481304016,212535591,665533192,749316869,538581644,317006985,968296352,808495028,830590521,531784288,361949821,632464819,1684642,511829606,222924458,934199693,967973644,787643802,606746849,96604575,680950950,308049679,546546208,960477105,238868753,951218324,197237322,890301452,972648121,211993439,387120559,209301382,528364764,231165541,761712833,286215380,339702698,661632118,265666133,21277340,575366956,716976999,241186148,104820150,100188502,360813771,96370711,543325956,266146398,203589709,411040690,106621604,579932960,577626310,11913834,337308047,291029322,615491474,687224688,190425016,816984038,346398440,588409598,380479061,743503811,825801773,781123011,92346696,832653861,92237470,668571204,764993338,114598625,539690884,843853494,736831032,574746196,14285749,672541450,822156862,187142323,636619609,787292178,171719565,199603936,121098038,404690112,865522996,75878404,376313619,552289458,911154270,497254008,525065672,553424287,543018068,197149277,727216358,425033035,211649283,722805387,450849915,739911356,554014894,786196360,280549074,970139977,67362579,941660926,745823196,993149209,481918480,64818902,581309654,949717760,329490815,289859320,435456727,75963792,850196338,318238233,325557403,635339142,367775081,827703363,185677785,428919174,738976525,875538282,238042422,904486800,650554490,575412075,654723259,53675617,935449102,195352411,334069943,728649426,162107018,968982693,588778317,717156071,624016364,424122244,326485387,440375118,118401023,812646527,841141837,875054001,268534610,590310860,559440494,590169945,153453963,539306384,468804560,161299303,377528159,578248523,413462617,321305369,853371346,905943370,232872556,384720840,679670440,831017707,990741477,925025550,305949527,200910087,103153211,590873037,372906255,634981065,389564676,63032279,956542862,271818664,167659381,667083639,840092893,977878826,144646518,294771082,582170420,194452282,873063389,509541523,854404404,552369283,962077967,948720381,634945898,784941894,311661910,109099564,366341144,500499768,456956931,368394667,837806741,961106658,144386550,929717504,396567069,137531553,291100606,929802162,431923993,284389342,181803203,127324323,168153386,959225802,842271485,399568012,732642728,849466163,691677896,437546833,842030400,416846330,358484336,15095984,366226314,542562022,328789906,523746388,860753212,186354678,810926224,335076529,27711233,86838495,557198019,764341904,834502832,268604730,572153660,803675856,623701656,674805873,614645680,493171373,624456734,451575096,973640306,311862148,480066936,863085498,595086682,115423688,807099733,413558429,253928703,733385551,91071236,211074478,225243719,255245243,524854324,701418736,987012788,316956781,760485487,919893175,445244568,804711044,136754592,742232625,533511717,496098992,760516994,300605714,96355730,481642766,587543454,373341033};
ll answer = factorial[sum_B_01 / bound];
FOREQ( i , sum_B_01 - ( sum_B_01 % bound ) + 1 , sum_B_01 ){
( answer *= i ) %= P;
}
ll q = 1;
FOR( d , 0 , 2 ){
vector<int>& B_d = B[d];
int i_min = 0;
int size_B_d = B_d.size();
if( size_B_d > 0 ){
int i_max = size_B_d - 1;
int j_lim = B_d[i_max];
FOR( j , 0 , j_lim ){
BS( i_start , i_min , i_max , B_d[i_start] <= j ? -1 : i_start == 0 ? 0 : B_d[i_start - 1] <= j ? 0 : 1 , 0 );
i_min = i_start;
FOR( i , i_start , size_B_d ){
( q *= ( B_d[i] - j ) + ( i - i_start ) ) %= P;
}
}
}
}
POWER_MOD( inv_q , q , P - 2 , P );
( answer *= inv_q ) %= P;
RETURN( answer );
}