#ifndef INCLUDE_MODE #define INCLUDE_MODE // #define REACTIVE // #define USE_GETLINE #define SUBMIT_ONLY #define DEBUG_OUTPUT // #define SAMPLE_CHECK dummy #endif #ifdef INCLUDE_MAIN VO Solve() { CIN_HW; grid = vector( H , string( W , '.' ) ); int p = 1 << HW; vector found( p ); vector count( HW + 1 ); vector> dfs{}; FOR( i , 0 , HW ){ int s = 1 << i; found[s] = true; int bs = 0; RUN( EdgeOnGrid( EnumHW( i ) ) , u ){ auto&& j = EnumHW_inv( u ); bs |= ( 1 << j ); } dfs.push_back( {s,bs} ); } while( !dfs.empty() ){ auto [s,bs] = dfs.back(); dfs.pop_back(); int c = __builtin_popcount( s ); count[c] += 1 << ( HW - c - __builtin_popcount( bs ) ); FOR( i , 0 , HW ){ if( ( ( bs >> i ) & 1 ) == 1 ){ int t = s | ( 1 << i ); if( found[t] ){ continue; } found[t] = true; int bt = bs ^ ( 1 << i ); RUN( EdgeOnGrid( EnumHW( i ) ) , u ){ auto&& j = EnumHW_inv( u ); ( ( s >> j ) & 1 ) == 0 ? bt |= ( 1 << j ) : bt; } dfs.push_back( {t,bt} ); } } } CIN( ll , K , M ); DynamicMod::SetModulo( M ); DynamicMod power_sum{} , coef{}; FOREQ( c , 1 , HW ){ power_sum += Power( DynamicMod::Derepresent( c ) , K ) * count[c]; } FOREQ( n , 1 , HW ){ coef += DynamicMod::one() / ( HW - n + 1 ); } RETURN( power_sum * coef * Power( DynamicMod::Derepresent( 2 ) , -HW ) ); } REPEAT_MAIN(1); #else /* INCLUDE_MAIN */ #ifdef INCLUDE_SUB /* 圧縮時は中身だけ削除する。*/ IN VO Experiment() { /* // 1変数 ../Contest/Template/Experiment/OneVariable.txt */ /* // 2変数 ../Contest/Template/Experiment/TwoVariable.txt */ /* // 3変数 ../Contest/Template/Experiment/ThreeVariable.txt */ } /* 圧縮時は中身だけ削除する。*/ IN VO SmallTest() { /* // 数 ../Contest/Template/SmallTest/Number.txt */ /* // 配列 ../Contest/Template/SmallTest/Array.txt */ /* // 順列 ../Contest/Template/SmallTest/Permutation.txt */ /* // 文字列 ../Contest/Template/SmallTest/String.txt */ /* // グリッド ../Contest/Template/SmallTest/Grid.txt */ /* // グラフ ../Contest/Template/SmallTest/Graph.txt */ /* // 重み付きグラフ ../Contest/Template/SmallTest/WeightedGraph.txt */ /* // 区間クエリ ../Contest/Template/SmallTest/IntervalQuery.txt */ } /* 圧縮時は中身だけ削除する。*/ IN VO RandomTest( const int& test_case_num ) { /* // 数 ../Contest/Template/SmallTest/Number.txt */ /* // 配列 ../Contest/Template/SmallTest/Array.txt */ /* // 順列 ../Contest/Template/SmallTest/Permutation.txt */ /* // 文字列 ../Contest/Template/SmallTest/String.txt */ /* // グリッド ../Contest/Template/SmallTest/Grid.txt */ /* // グラフ ../Contest/Template/SmallTest/Graph.txt */ /* // 重み付きグラフ ../Contest/Template/SmallTest/WeightedGraph.txt */ /* // 区間クエリ ../Contest/Template/SmallTest/IntervalQuery.txt */ /* // 多種クエリ ../Contest/Template/SmallTest/MultiTypeQuery.txt */ REPEAT( test_case_num ){ } } #define INCLUDE_MAIN #include __FILE__ #else /* INCLUDE_SUB */ #ifdef INCLUDE_LIBRARY /* VVV 常設でないライブラリは以下に挿入する。*/ /* // BFS ../Contest/Template/Library/BFS.txt */ /* // BIT ../Contest/Template/Library/BIT.txt */ /* // CoordinateCompress ../Contest/Template/Library/CoordinateCompress.txt */ /* // DFS ../Contest/Template/Library/DFS.txt */ /* // DifferenceSequence ../Contest/Template/Library/DifferenceSequence.txt */ /* // Dijkstra ../Contest/Template/Library/Dijkstra.txt */ /* // Divisor ../Contest/Template/Library/Divisor.txt */ /* // Knapsack ../Contest/Template/Library/Knapsack.txt */ /* // Matrix ../Contest/Template/Library/Matrix.txt */ /* // Set ../Contest/Template/Library/Set.txt */ /* // Polynomial ../Contest/Template/Library/Polynomial.txt */ /* // SqrtDecomposition ../Contest/Template/Library/SqrtDecomposition.txt */ /* // UnionFind ../Contest/Template/Library/UnionFind.txt */ #ifdef DEBUG #include "c:/Users/user/Documents/Programming/Mathematics/Arithmetic/Mod/DynamicModulo/Debug/a_Body.hpp" #else #define RP Represent #define DeRP Derepresent TE CE INT1 Residue(INT1 n,CO INT2& M)NE{RE MO(n < 0?((((++n)*= -1)%= M)*= -1)+= M - 1:n < M?n:n %= M);} TE CL DynamicMods;TE CL COantsForDynamicMods{PU:COantsForDynamicMods()= delete;ST uint g_M;ST uint g_M_minus;ST int g_order;ST int g_order_minus_1;ST int g_order_minus_1_neg;ST bool g_M_is_prime;}; TE uint COantsForDynamicMods::g_M = 0;TE uint COantsForDynamicMods::g_M_minus = -1;TE int COantsForDynamicMods::g_order = 1;TE int COantsForDynamicMods::g_order_minus_1 = 0;TE int COantsForDynamicMods::g_order_minus_1_neg = 0;TE bool COantsForDynamicMods::g_M_is_prime = false; #define DC_OF_CM_FOR_DYNAMIC_MOD(OPR)IN bool OP OPR(CO DynamicMods& n)CO NE #define DC_OF_AR_FOR_DYNAMIC_MOD(OPR,EX)IN DynamicMods OP OPR(DynamicMods n)CO EX; #define DF_OF_CM_FOR_DYNAMIC_MOD(OPR)TE IN bool DynamicMods::OP OPR(CO DynamicMods& n)CO NE{RE m_n OPR n.m_n;} #define DF_OF_AR_FOR_DYNAMIC_MOD(OPR,EX,LEFT,OPR2)TE IN DynamicMods DynamicMods::OP OPR(DynamicMods n)CO EX{RE MO(LEFT OPR2 ## = *TH);}TE IN DynamicMods OP OPR(T n0,CO DynamicMods& n1)EX{RE MO(DynamicMods(MO(n0))OPR ## = n1);} TE CL DynamicMods{PU:uint m_n;IN DynamicMods()NE;IN DynamicMods(CO DynamicMods& n)NE;IN DynamicMods(DynamicMods&& n)NE;TE IN DynamicMods(T n)NE;IN DynamicMods& OP=(DynamicMods n)NE;IN DynamicMods& OP+=(CO DynamicMods& n)NE;IN DynamicMods& OP-=(CO DynamicMods& n)NE;IN DynamicMods& OP*=(CO DynamicMods& n)NE;IN DynamicMods& OP/=(DynamicMods n);TE IN DynamicMods& OP<<=(INT n);TE IN DynamicMods& OP>>=(INT n);IN DynamicMods& OP++()NE;IN DynamicMods OP++(int)NE;IN DynamicMods& OP--()NE;IN DynamicMods OP--(int)NE;DC_OF_CM_FOR_DYNAMIC_MOD(==);DC_OF_CM_FOR_DYNAMIC_MOD(!=);DC_OF_CM_FOR_DYNAMIC_MOD(<);DC_OF_CM_FOR_DYNAMIC_MOD(<=);DC_OF_CM_FOR_DYNAMIC_MOD(>);DC_OF_CM_FOR_DYNAMIC_MOD(>=);DC_OF_AR_FOR_DYNAMIC_MOD(+,NE);DC_OF_AR_FOR_DYNAMIC_MOD(-,NE);DC_OF_AR_FOR_DYNAMIC_MOD(*,NE);DC_OF_AR_FOR_DYNAMIC_MOD(/,);TE IN DynamicMods OP^(INT EX)CO;TE IN DynamicMods OP<<(INT n)CO;TE IN DynamicMods OP>>(INT n)CO;IN DynamicMods OP-()CO NE;IN DynamicMods& SignInvert()NE;IN DynamicMods& Invert();TE IN DynamicMods& PW(INT EX);IN VO swap(DynamicMods& n)NE;IN CRUI RP()CO NE;ST IN DynamicMods DeRP(uint n)NE;ST IN CO DynamicMods& Inverse(CRUI n);ST IN CO DynamicMods& Factorial(CRUI n);ST IN CO DynamicMods& FactorialInverse(CRUI n);ST IN DynamicMods Combination(CRUI n,CRUI i);ST IN CO DynamicMods& zero()NE;ST IN CO DynamicMods& one()NE;ST IN CRUI GetModulo()NE;ST IN VO SetModulo(CRUI M,CRI order_minus_1 = -1)NE;TE IN DynamicMods& PositivePW(INT EX)NE;TE IN DynamicMods& NonNegativePW(INT EX)NE;US COants = COantsForDynamicMods;}; US DynamicMod = DynamicMods<0>; TE IN DynamicMods::DynamicMods()NE:m_n(){}TE IN DynamicMods::DynamicMods(CO DynamicMods& n)NE:m_n(n.m_n){}TE IN DynamicMods::DynamicMods(DynamicMods&& n)NE:m_n(MO(n.m_n)){}TE TE IN DynamicMods::DynamicMods(T n)NE:m_n(Residue(uint(MO(n)),COants::g_M)){ST_AS(is_COructible_v >);}TE IN DynamicMods& DynamicMods::OP=(DynamicMods n)NE{m_n = MO(n.m_n);RE *TH;}TE IN DynamicMods& DynamicMods::OP+=(CO DynamicMods& n)NE{(m_n += n.m_n)< COants::g_M?m_n:m_n -= COants::g_M;RE *TH;}TE IN DynamicMods& DynamicMods::OP-=(CO DynamicMods& n)NE{m_n < n.m_n?(m_n += COants::g_M)-= n.m_n:m_n -= n.m_n;RE *TH;}TE IN DynamicMods& DynamicMods::OP*=(CO DynamicMods& n)NE{m_n = Residue(MO(ull(m_n)* n.m_n),COants::g_M);RE *TH;}TE IN DynamicMods& DynamicMods::OP/=(DynamicMods n){RE OP*=(n.Invert());}TE TE IN DynamicMods& DynamicMods::OP<<=(INT n){AS(n >= 0);RE *TH *= DynamicMods(2).NonNegativePW(MO(n));}TE TE IN DynamicMods& DynamicMods::OP>>=(INT n){AS(n >= 0);WH(n-- > 0){((m_n & 1)== 0?m_n:m_n += COants::g_M)>>= 1;}RE *TH;}TE IN DynamicMods& DynamicMods::OP++()NE{m_n < COants::g_M_minus?++m_n:m_n = 0;RE *TH;}TE IN DynamicMods DynamicMods::OP++(int)NE{DynamicMods n{*TH};OP++();RE n;}TE IN DynamicMods& DynamicMods::OP--()NE{m_n == 0?m_n = COants::g_M_minus:--m_n;RE *TH;}TE IN DynamicMods DynamicMods::OP--(int)NE{DynamicMods n{*TH};OP--();RE n;}DF_OF_CM_FOR_DYNAMIC_MOD(==);DF_OF_CM_FOR_DYNAMIC_MOD(!=);DF_OF_CM_FOR_DYNAMIC_MOD(>);DF_OF_CM_FOR_DYNAMIC_MOD(>=);DF_OF_CM_FOR_DYNAMIC_MOD(<);DF_OF_CM_FOR_DYNAMIC_MOD(<=);DF_OF_AR_FOR_DYNAMIC_MOD(+,NE,n,+);DF_OF_AR_FOR_DYNAMIC_MOD(-,NE,n.SignInvert(),+);DF_OF_AR_FOR_DYNAMIC_MOD(*,NE,n,*);DF_OF_AR_FOR_DYNAMIC_MOD(/,,n.Invert(),*);TE TE IN DynamicMods DynamicMods::OP^(INT EX)CO{RE MO(DynamicMods(*TH).PW(MO(EX)));}TE TE IN DynamicMods DynamicMods::OP<<(INT n)CO{RE MO(DynamicMods(*TH)<<= MO(n));}TE TE IN DynamicMods DynamicMods::OP>>(INT n)CO{RE MO(DynamicMods(*TH)>>= MO(n));}TE IN DynamicMods DynamicMods::OP-()CO NE{RE MO(DynamicMods(*TH).SignInvert());}TE IN DynamicMods& DynamicMods::SignInvert()NE{m_n > 0?m_n = COants::g_M - m_n:m_n;RE *TH;}TE IN DynamicMods& DynamicMods::Invert(){RE m_n <(COants::g_M_is_prime?1e6:3e4)?*TH = Inverse(m_n):NonNegativePW(COants::g_order_minus_1);}TE TE IN DynamicMods& DynamicMods::PositivePW(INT EX)NE{DynamicMods PW{*TH};EX--;WH(EX != 0){(EX & 1)== 1?*TH *= PW:*TH;EX >>= 1;PW *= PW;}RE *TH;}TE TE IN DynamicMods& DynamicMods::NonNegativePW(INT EX)NE{RE EX == 0?(m_n = 1,*TH):PositivePW(MO(EX));}TE TE IN DynamicMods& DynamicMods::PW(INT EX){bool neg = EX < 0;RE neg?PositivePW(ll(MO(EX %= COants::g_order))* COants::g_order_minus_1_neg % COants::g_order):NonNegativePW(MO(EX));}TE IN VO DynamicMods::swap(DynamicMods& n)NE{std::swap(m_n,n.m_n);}TE IN CO DynamicMods& DynamicMods::Inverse(CRUI n){ST VE> memory ={zero(),one()};ST uint LE_curr = 2;AS(COants::g_M == 1||(0 < n && n < COants::g_M));WH(LE_curr <= n){memory.push_back(COants::g_M_is_prime?DeRP(COants::g_M - memory[COants::g_M % LE_curr].m_n * ull(COants::g_M / LE_curr)% COants::g_M):DeRP(n).NonNegativePW(COants::g_order_minus_1));LE_curr++;}RE memory[n];}TE IN CO DynamicMods& DynamicMods::Factorial(CRUI n){ST VE> memory ={one(),one()};ST uint LE_curr = 2;if(COants::g_M <= n){RE zero();}WH(LE_curr <= n && memory.back().m_n != 0){memory.push_back(memory.back()* DeRP(LE_curr));LE_curr++;}RE LE_curr <= n?memory.back():memory[n];}TE IN CO DynamicMods& DynamicMods::FactorialInverse(CRUI n){ST VE> memory ={one(),one()};ST uint LE_curr = 2;WH(LE_curr <= n){memory.push_back(memory[LE_curr - 1]* Inverse(LE_curr));LE_curr++;}RE memory[n];}TE IN DynamicMods DynamicMods::Combination(CRUI n,CRUI i){RE i <= n?Factorial(n)* FactorialInverse(i)* FactorialInverse(n - i):zero();}TE IN CRUI DynamicMods::RP()CO NE{RE m_n;}TE IN DynamicMods DynamicMods::DeRP(uint n)NE{DynamicMods n_copy{};n_copy.m_n = MO(n);RE n_copy;}TE IN CO DynamicMods& DynamicMods::zero()NE{ST CO DynamicMods z{};RE z;}TE IN CO DynamicMods& DynamicMods::one()NE{ST CO DynamicMods o{1};RE o;}TE IN CRUI DynamicMods::GetModulo()NE{RE COants::g_M;}TE IN VO DynamicMods::SetModulo(CRUI M,CRI order_minus_1)NE{COants::g_M = M;COants::g_M_minus = M - 1;COants::g_order = order_minus_1 == -1?M - 1:order_minus_1+1;COants::g_order_minus_1 = COants::g_order-1;COants::g_order_minus_1_neg = -COants::g_order_minus_1;COants::g_M_is_prime = order_minus_1 == -1;}TE IN DynamicMods Inverse(CO DynamicMods& n){RE MO(DynamicMods(n).Invert());}TE IN DynamicMods PW(DynamicMods n,INT EX){RE MO(n.PW(MO(EX)));}TE IN VO swap(DynamicMods& n0,DynamicMods& n1)NE{n0.swap(n1);}TE IN string to_string(CO DynamicMods& n)NE{RE to_string(n.RP())+ " + " + to_string(DynamicMods::GetModulo())+ "Z";}TE IN IS& OP>>(IS& is,DynamicMods& n){ll m;is >> m;n = m;RE is;}TE IN OS& OP<<(OS& os,CO DynamicMods& n){RE os << n.RP();} TE INT1 GCD(CO INT1& b_0,CO INT2& b_1){INT1 a_0 = b_0 < 0?-b_0:b_0;INT1 a_1 = b_1 < 0?-b_1:b_1;WH(a_1 != 0){swap(a_0 %= a_1,a_1);}RE a_0;}TE IN INT1 LCM(CO INT1& b_0,CO INT2& b_1){RE(b_0 == 0 && b_1 == 0)?0:(b_0 / GCD(b_0,b_1))* b_1;} #endif /* AAA 常設でないライブラリは以上に挿入する。*/ #define INCLUDE_SUB #include __FILE__ #else /* INCLUDE_LIBRARY */ #ifdef DEBUG #define _GLIBCXX_DEBUG #else #pragma GCC optimize ( "O3" ) #pragma GCC optimize ( "unroll-loops" ) #pragma GCC target ( "sse4.2,fma,avx2,popcnt,lzcnt,bmi2" ) #define REPEAT_MAIN( BOUND ) START_MAIN; CEXPR( int , bound_test_case_num , BOUND ); int test_case_num = 1; if CE( bound_test_case_num > 1 ){ SET_ASSERT( test_case_num , 1 , bound_test_case_num ); } FINISH_MAIN #define FINISH_MAIN REPEAT( test_case_num ){ if CE( bound_test_case_num > 1 ){ CERR( "testcase " , VARIABLE_FOR_REPEAT_test_case_num , ":" ); } Solve(); CERR( "" ); } } #define DEXPR( LL , BOUND , VALUE1 , VALUE2 ) CEXPR( LL , BOUND , VALUE1 ) #define ASSERT( A , MIN , MAX ) AS( ( MIN ) <= A && A <= ( MAX ) ) #ifdef USE_GETLINE #define SET_SEPARATE( SEPARATOR , ... ) VariadicGetline( cin , SEPARATOR , __VA_ARGS__ ) #define SET( ... ) SET_SEPARATE( '\n' , __VA_ARGS__ ) #define GETLINE_SEPARATE( SEPARATOR , ... ) string __VA_ARGS__; SET_SEPARATE( SEPARATOR , __VA_ARGS__ ) #define GETLINE( ... ) GETLINE_SEPARATE( '\n' , __VA_ARGS__ ) #else #define SET( ... ) VariadicCin( cin , __VA_ARGS__ ) #define CIN( LL , ... ) LL __VA_ARGS__; SET( __VA_ARGS__ ) #define SET_A( I , N , ... ) VariadicResize( N + I , __VA_ARGS__ ); FOR( VARIABLE_FOR_SET_A , 0 , N ){ VariadicSet( cin , VARIABLE_FOR_SET_A + I , __VA_ARGS__ ); } #define CIN_A( LL , I , N , ... ) VE __VA_ARGS__; SET_A( I , N , __VA_ARGS__ ) #define CIN_AA( LL , I0 , N0 , I1 , N1 , VAR ) VE> VAR( N0 + I0 ); FOR( VARIABLE_FOR_CIN_AA , 0 , N0 ){ SET_A( I1 , N1 , VAR[VARIABLE_FOR_CIN_AA + I0] ); } #endif #define SET_ASSERT( A , MIN , MAX ) SET( A ); ASSERT( A , MIN , MAX ) #define SOLVE_ONLY #define COUT( ... ) VariadicCout( cout , __VA_ARGS__ ) << ENDL #define COUTNS( ... ) VariadicCoutNonSep( cout , __VA_ARGS__ ) #define CERR( ... ) #define CERRNS( ... ) #define COUT_A( I , N , A ) CoutArray( cout , I , N , A ) << ENDL #define CERR_A( I , N , A ) #endif #ifdef REACTIVE #ifdef DEBUG #define RSET( A , ... ) A = __VA_ARGS__ #else #define RSET( A , ... ) SET( A ) #endif #define RCIN( LL , A , ... ) LL A; RSET( A , __VA_ARGS__ ) #define ENDL endl #else #define ENDL "\n" #endif #include using namespace std; #define ATT __attribute__( ( target( "sse4.2,fma,avx2,popcnt,lzcnt,bmi2" ) ) ) #define START_MAIN int main(){ ios_base::sync_with_stdio( false ); cin.tie( nullptr ) #define START_WATCH chrono::system_clock::time_point watch = chrono::system_clock::now(); double loop_average_time = 0.0 , loop_start_time = 0.0 , current_time = 0.0; int loop_count = 0 #define CURRENT_TIME ( current_time = static_cast( chrono::duration_cast( chrono::system_clock::now() - watch ).count() / 1000.0 ) ) #define CHECK_WATCH( TL_MS ) ( CURRENT_TIME , loop_count == 0 ? loop_start_time = current_time : loop_average_time = ( current_time - loop_start_time ) / loop_count , ++loop_count , current_time < TL_MS - loop_average_time * 2 - 100.0 ) #define CEXPR( LL , BOUND , VALUE ) CE LL BOUND = VALUE #define SET_A_ASSERT( I , N , A , MIN , MAX ) FOR( VARIABLE_FOR_SET_A , 0 , N ){ SET_ASSERT( A[VARIABLE_FOR_SET_A + I] , MIN , MAX ); } #define SET_AA_ASSERT( I0 , N0 , I1 , N1 , A , MIN , MAX ) FOR( VARIABLE_FOR_SET_AA0 , 0 , N0 ){ FOR( VARIABLE_FOR_SET_AA1 , 0 , N1 ){ SET_ASSERT( A[VARIABLE_FOR_SET_AA0 + I0][VARIABLE_FOR_SET_AA1 + I1] , MIN , MAX ); } } #define CIN_ASSERT( A , MIN , MAX ) decldecay_t( MAX ) A; SET_ASSERT( A , MIN , MAX ) #define CIN_A_ASSERT( I , N , A , MIN , MAX ) vector A( N + I ); SET_A_ASSERT( I , N , A , MIN , MAX ) #define CIN_AA_ASSERT( I0 , N0 , I1 , N1 , A , MIN , MAX ) vector A( N0 + I0 , vector( N1 + I1 ) ); SET_AA_ASSERT( I0 , N0 , I1 , N1 , A , MIN , MAX ) #define FOR( VAR , INITIAL , FINAL_PLUS_ONE ) for( decldecay_t( FINAL_PLUS_ONE ) VAR = INITIAL ; VAR < FINAL_PLUS_ONE ; VAR ++ ) #define FOREQ( VAR , INITIAL , FINAL ) for( decldecay_t( FINAL ) VAR = INITIAL ; VAR <= FINAL ; VAR ++ ) #define FOREQINV( VAR , INITIAL , FINAL ) for( decldecay_t( INITIAL ) VAR = INITIAL ; VAR + 1 > FINAL ; VAR -- ) #define ITR( ARRAY ) auto begin_ ## ARRAY = ARRAY .BE() , itr_ ## ARRAY = begin_ ## ARRAY , end_ ## ARRAY = ARRAY .EN() #define FOR_ITR( ARRAY ) for( ITR( ARRAY ) , itr = itr_ ## ARRAY ; itr_ ## ARRAY != end_ ## ARRAY ; itr_ ## ARRAY ++ , itr++ ) #define RUN( ARRAY , ... ) for( auto&& __VA_ARGS__ : ARRAY ) #define REPEAT( HOW_MANY_TIMES ) FOR( VARIABLE_FOR_REPEAT_ ## HOW_MANY_TIMES , 0 , HOW_MANY_TIMES ) #define SET_PRECISION( DECIMAL_DIGITS ) cout << fixed << setprecision( DECIMAL_DIGITS ); cerr << fixed << setprecision( DECIMAL_DIGITS ) #define RETURN( ... ) SOLVE_ONLY; COUT( __VA_ARGS__ ); RE #define COMPARE( ... ) auto naive = Naive( __VA_ARGS__ , false ); auto answer = Answer( __VA_ARGS__ , false ); bool match = naive == answer; CERR( "(" , #__VA_ARGS__ , ") == (" , __VA_ARGS__ , ") : Naive == " , naive , match ? "==" : "!=" , answer , "== Answer" ); if( !match ){ RE; } /* 圧縮用 */ #define TE template #define TY typename #define US using #define ST static #define AS assert #define IN inline #define CL class #define PU public #define OP operator #define CE constexpr #define CO const #define NE noexcept #define RE return #define WH while #define VO void #define VE vector #define LI list #define BE begin #define EN end #define SZ size #define LE length #define PW Power #define MO move #define TH this #define CRI CO int& #define CRUI CO uint& #define CRL CO ll& #define VI virtual #define IS basic_istream #define OS basic_ostream #define ST_AS static_assert #define reMO_CO remove_const #define is_COructible_v is_constructible_v #define rBE rbegin /* 型のエイリアス */ #define decldecay_t(VAR)decay_t TE US ret_t = decltype(declval()(declval()...)); TE US inner_t = TY T::type; US uint = unsigned int; US ll = long long; US ull = unsigned long long; US ld = long double; US lld = __float128; TE US T2 = pair; TE US T3 = tuple; TE US T4 = tuple; US path = pair; /* VVV 常設ライブラリは以下に挿入する。*/ #ifdef DEBUG #include "C:/Users/user/Documents/Programming/Contest/Template/Local/a_Body.hpp" #else /* Random (1KB)*/ ll GetRand(CRI Rand_min,CRI Rand_max){AS(Rand_min <= Rand_max);ll AN = time(NULL);RE AN * rand()%(Rand_max + 1 - Rand_min)+ Rand_min;} /* Set (1KB)*/ #define DC_OF_HASH(...)struct hash<__VA_ARGS__>{IN size_t OP()(CO __VA_ARGS__& n)CO;}; CL is_ordered{PU:is_ordered()= delete;TE ST CE auto Check(CO T& t)-> decltype(t < t,true_type());ST CE false_type Check(...);TE ST CE CO bool value = is_same_v< decltype(Check(declval())),true_type >;}; TE US Set = conditional_t>,unordered_set,conditional_t,set,VO>>; /* Tuple (5KB)*/ #define DF_OF_AR_FOR_TUPLE(OPR)TE TY V> IN auto OP OPR ## =(V& t0,CO V& t1)-> decltype((get<0>(t0),t0))&{get<0>(t0)OPR ## = get<0>(t1);get<1>(t0)OPR ## = get<1>(t1);RE t0;}TE IN tuple& OP OPR ## =(tuple& t0,CO tuple& t1){get<0>(t0)OPR ## = get<0>(t1);get<1>(t0)OPR ## = get<1>(t1);get<2>(t0)OPR ## = get<2>(t1);RE t0;}TE IN tuple& OP OPR ## =(tuple& t0,CO tuple& t1){get<0>(t0)OPR ## = get<0>(t1);get<1>(t0)OPR ## = get<1>(t1);get<2>(t0)OPR ## = get<2>(t1);get<3>(t0)OPR ## = get<3>(t1);RE t0;}TE TY V> IN auto OP OPR ## =(V& t0,CO ARG& t1)-> decltype((get<0>(t0),t0))&{get<0>(t0)OPR ## = t1;get<1>(t0)OPR ## = t1;RE t0;}TE IN tuple& OP OPR ## =(tuple& t0,CO ARG& t1){get<0>(t0)OPR ## = t1;get<1>(t0)OPR ## = t1;get<2>(t0)OPR ## = t1;RE t0;}TE IN tuple& OP OPR ## =(tuple& t0,CO ARG& t1){get<0>(t0)OPR ## = t1;get<1>(t0)OPR ## = t1;get<2>(t0)OPR ## = t1;get<3>(t0)OPR ## = t1;RE t0;}TE TY V,TY...ARGS,TY ARG> IN auto OP OPR(CO V& t0,CO ARG& t1)-> decldecay_t((get<0>(t0),t0)){auto t = t0;RE MO(t OPR ## = t1);} #define DF_OF_INCREMENT_FOR_TUPLE(INCR)TE TY V> IN auto OP INCR(V& t)-> decltype((get<0>(t),t))&{INCR get<0>(t);INCR get<1>(t);RE t;}TE IN tuple& OP INCR(tuple& t){INCR get<0>(t);INCR get<1>(t);INCR get<2>(t);RE t;}TE IN tuple& OP INCR(tuple& t){INCR get<0>(t);INCR get<1>(t);INCR get<2>(t);INCR get<3>(t);RE t;} TE IN IS& OP>>(IS& is,tuple& arg){RE is >> get<0>(arg);}TE TY V> IN auto OP>>(IS& is,V& arg)-> decltype((get<0>(arg),is))&{RE is >> get<0>(arg)>> get<1>(arg);}TE IN IS& OP>>(IS& is,tuple& arg){RE is >> get<0>(arg)>> get<1>(arg)>> get<2>(arg);}TE IN IS& OP>>(IS& is,tuple& arg){RE is >> get<0>(arg)>> get<1>(arg)>> get<2>(arg)>> get<3>(arg);}TE IN OS& OP<<(OS& os,CO tuple& arg){RE os << get<0>(arg);}TE TY V> IN auto OP<<(OS& os,CO V& arg)-> decltype((get<0>(arg),os))&{RE os << get<0>(arg)<< " " << get<1>(arg);}TE IN OS& OP<<(OS& os,CO tuple& arg){RE os << get<0>(arg)<< " " << get<1>(arg)<< " " << get<2>(arg);}TE IN OS& OP<<(OS& os,CO tuple& arg){RE os << get<0>(arg)<< " " << get<1>(arg)<< " " << get<2>(arg)<< " " << get<3>(arg);}DF_OF_AR_FOR_TUPLE(+);TE TY V> IN auto OP-(CO V& t)-> decltype(get<0>(t),t){RE{-get<0>(t),-get<1>(t)};}TE IN tuple OP-(CO tuple& t){RE{-get<0>(t),-get<1>(t),-get<2>(t)};}TE IN tuple OP-(CO tuple& t){RE{-get<0>(t),-get<1>(t),-get<2>(t),-get<3>(t)};}DF_OF_AR_FOR_TUPLE(-);DF_OF_AR_FOR_TUPLE(*);DF_OF_AR_FOR_TUPLE(/);DF_OF_AR_FOR_TUPLE(%);DF_OF_INCREMENT_FOR_TUPLE(++);DF_OF_INCREMENT_FOR_TUPLE(--); #define DF_OF_HASH_FOR_TUPLE(PAIR)TE IN size_t hash>::OP()(CO PAIR& n)CO{ST CO size_t seed =(GetRand(1e3,1e8)<< 1)| 1;ST CO hash h0;ST CO hash h1;RE(h0(get<0>(n))* seed)^ h1(get<1>(n));} TE DC_OF_HASH(tuple);TE DC_OF_HASH(pair);TE DC_OF_HASH(tuple);TE DC_OF_HASH(tuple);TE DC_OF_HASH(tuple); TE IN size_t hash>::OP()(CO tuple& n)CO{ST CO hash h;RE h(get<0>(n));}DF_OF_HASH_FOR_TUPLE(pair);DF_OF_HASH_FOR_TUPLE(tuple);TE IN size_t hash>::OP()(CO tuple& n)CO{ST CO size_t seed =(GetRand(1e3,1e8)<< 1)| 1;ST CO hash> h01;ST CO hash h2;RE(h01({get<0>(n),get<1>(n)})* seed)^ h2(get<2>(n));}TE IN size_t hash>::OP()(CO tuple& n)CO{ST CO size_t seed =(GetRand(1e3,1e8)<< 1)| 1;ST CO hash> h01;ST CO hash> h23;RE(h01({get<0>(n),get<1>(n)})* seed)^ h23({get<2>(n),get<3>(n)});} /* Vector (2KB)*/ #define DF_OF_COUT_FOR_VE(V)TE IN OS& OP<<(OS& os,CO V& arg){auto BE = arg.BE(),EN = arg.EN();auto IT = BE;WH(IT != EN){(IT == BE?os:os << " ")<< *IT;IT++;}RE os;} #define DF_OF_AR_FOR_VE(V,OPR)TE IN V& OP OPR ## =(V& a,CO T& t){for(auto& s:a){s OPR ## = t;}RE a;}TE IN V& OP OPR ## =(V& a0,CO V& a1){AS(a0.SZ()<= a1.SZ());auto IT0 = a0.BE(),EN0 = a0.EN();auto IT1 = a1.BE();WH(IT0 != EN0){*(IT0++)OPR ## = *(IT1++);}RE a0;}TE IN V OP OPR(V a,CO U& u){RE MO(a OPR ## = u);} #define DF_OF_INCREMENT_FOR_VE(V,INCR)TE IN V& OP INCR(V& a){for(auto& i:a){INCR i;}RE a;} #define DF_OF_ARS_FOR_VE(V)DF_OF_AR_FOR_VE(V,+);DF_OF_AR_FOR_VE(V,-);DF_OF_AR_FOR_VE(V,*);DF_OF_AR_FOR_VE(V,/);DF_OF_AR_FOR_VE(V,%);DF_OF_INCREMENT_FOR_VE(V,++);DF_OF_INCREMENT_FOR_VE(V,--);TE IN V OP*(CO T& scalar,V v){for(auto& t:v){t *= scalar;}RE MO(v);} DF_OF_COUT_FOR_VE(VE);DF_OF_COUT_FOR_VE(LI);DF_OF_ARS_FOR_VE(VE);DF_OF_ARS_FOR_VE(LI);IN VO VariadicResize(CRI SZ){}TE IN VO VariadicResize(CRI SZ,Arg& arg,ARGS&... args){arg.resize(SZ);VariadicResize(SZ,args...);}TE IN auto Get(V& a){RE[&](CRI i = 0)-> CO decldecay_t(a[0])&{RE a[i];};}TE IN VE id(CRI SZ){VE AN(SZ);FOR(i,0,SZ){AN[i]= i;}RE AN;}TE VO Sort(VE& a,CO bool& reversed = false){if(reversed){ST auto comp =[](CO T& t0,CO T& t1){RE t1 < t0;};sort(a.BE(),a.EN(),comp);}else{sort(a.BE(),a.EN());}}TE IN VE IndexSort(CO VE& a,CO bool& reversed = false){auto index = id(a.SZ());if(reversed){sort(index.BE(),index.EN(),[&](CRI i,CRI j){RE a[j]< a[i];});}else{sort(index.BE(),index.EN(),[&](CRI i,CRI j){RE a[i]< a[j];});}RE index;}TE IN U Sum(CO VE& a){U AN{};for(auto& x:a){AN += x;}RE AN;}TE IN U Product(CO VE& a){U AN{};for(auto& x:a){AN *= x;}RE AN;} /* Map (1KB)*/ #define DF_OF_AR_FOR_MAP(MAP,OPR)TE IN MAP& OP OPR ## =(MAP& a,CO pair& v){a[v.first]OPR ## = v.second;RE a;}TE IN MAP& OP OPR ## =(MAP& a0,CO MAP& a1){for(auto&[t,u]:a1){a0[t]OPR ## = u;}RE a0;}TE IN MAP OP OPR(MAP a,CO ARG& arg){RE MO(a OPR ## = arg);} #define DF_OF_ARS_FOR_MAP(MAP)DF_OF_AR_FOR_MAP(MAP,+);DF_OF_AR_FOR_MAP(MAP,-);DF_OF_AR_FOR_MAP(MAP,*);DF_OF_AR_FOR_MAP(MAP,/);DF_OF_AR_FOR_MAP(MAP,%); TE US Map = conditional_t>,unordered_map,conditional_t,map,VO>>; DF_OF_ARS_FOR_MAP(map);DF_OF_ARS_FOR_MAP(unordered_map); /* StdStream (2KB)*/ TE IN IS& VariadicCin(IS& is){RE is;}TE IN IS& VariadicCin(IS& is,Arg& arg,ARGS&... args){RE VariadicCin(is >> arg,args...);}TE IN IS& VariadicSet(IS& is,CRI i){RE is;}TE IN IS& VariadicSet(IS& is,CRI i,Arg& arg,ARGS&... args){RE VariadicSet(is >> arg[i],i,args...);}TE IN IS& VariadicGetline(IS& is,CO char& separator){RE is;}TE IN IS& VariadicGetline(IS& is,CO char& separator,Arg& arg,ARGS&... args){RE VariadicGetline(getline(is,arg,separator),separator,args...);}TE IN OS& VariadicCout(OS& os,Arg&& arg){RE os << forward(arg);}TE IN OS& VariadicCout(OS& os,Arg1&& arg1,Arg2&& arg2,ARGS&&... args){RE VariadicCout(os << forward(arg1)<< " ",forward(arg2),forward(args)...);}TE IN OS& VariadicCoutNonSep(OS& os,Arg&& arg){RE os << forward(arg);}TE