// 入力制約/フォーマットチェック #ifndef INCLUDE_MODE #define INCLUDE_MODE // #define REACTIVE #define USE_GETLINE #endif #ifdef INCLUDE_MAIN void Solve() { CEXPR( int , bound_M , 1<<10 ); CEXPR( int , bound_N , 1<<12 ); GETLINE_COUNT( MN_str , 2 , ' ' ); STOI( MN_str , M , 1 , bound_M ); STOI( MN_str , N , 1 , bound_N ); CEXPR( int , digit , 4096 ); using T = bitset; vector b( M ); FOR( j , 0 , M ){ GETLINE( S ); assert( int( S.size() ) == N ); FOR( i , 0 , N ){ assert( S[i] == '0' || S[i] == '1' ); } b[j] = T{ S }; } vector neigh( N , ~T{} ); FOR( j , 0 , M ){ FOR( i , 0 , N ){ if( b[j][i] == 1 ){ neigh[i] &= b[j]; } } } UnionFindForest uff( N ); FOR( i , 0 , N ){ FOR( j , 0 , N ){ if( neigh[i][j] == 1 ){ uff.Graft( i , j ); } } } RETURN( uff.RootSize() ); } REPEAT_MAIN(1); #else // INCLUDE_MAIN #ifdef INCLUDE_LIBRARY // https://github.com/p-adic/cpp // VVV ライブラリは以下に挿入する。redefinitionを避けるため圧縮元はincludeしない。 /* 圧縮用 */ #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 DC_OF_CPOINT(POINT)IN CO U& POINT()CO NE #define DC_OF_POINT(POINT)IN U& POINT()NE #define DF_OF_CPOINT(POINT)TE IN CO U& VirtualPointedSet::POINT()CO NE{RE Point();} #define DF_OF_POINT(POINT)TE IN U& VirtualPointedSet::POINT()NE{RE Point();} TE CL UnderlyingSet{PU:US type = U;};TE CL VirtualPointedSet:VI PU UnderlyingSet{PU:VI CO U& Point()CO NE = 0;VI U& Point()NE = 0;DC_OF_CPOINT(Unit);DC_OF_CPOINT(Zero);DC_OF_CPOINT(One);DC_OF_CPOINT(Infty);DC_OF_POINT(init);DC_OF_POINT(root);};TE CL PointedSet:VI PU VirtualPointedSet{PU:U m_b_U;IN PointedSet(U b_u = U());IN CO U& Point()CO NE;IN U& Point()NE;};TE CL VirtualNSet:VI PU UnderlyingSet{PU:VI U Transfer(CO U& u)= 0;IN U Inverse(CO U& u);};TE CL AbstractNSet:VI PU VirtualNSet{PU:F_U m_f_U;IN AbstractNSet(F_U f_U);IN AbstractNSet& OP=(CO AbstractNSet&)NE;IN U Transfer(CO U& u);};TE CL VirtualMagma:VI PU UnderlyingSet{PU:VI U Product(U u0,CO U& u1)= 0;IN U Sum(U u0,CO U& u1);};TE CL AdditiveMagma:VI PU VirtualMagma{PU:IN U Product(U u0,CO U& u1);};TE CL MultiplicativeMagma:VI PU VirtualMagma{PU:IN U Product(U u0,CO U& u1);};TE CL AbstractMagma:VI PU VirtualMagma{PU:M_U m_m_U;IN AbstractMagma(M_U m_U);IN AbstractMagma& OP=(CO AbstractMagma&)NE;IN U Product(U u0,CO U& u1);}; TE IN PointedSet::PointedSet(U b_U):m_b_U(MO(b_U)){}TE IN CO U& PointedSet::Point()CO NE{RE m_b_U;}TE IN U& PointedSet::Point()NE{RE m_b_U;}DF_OF_CPOINT(Unit);DF_OF_CPOINT(Zero);DF_OF_CPOINT(One);DF_OF_CPOINT(Infty);DF_OF_POINT(init);DF_OF_POINT(root);TE IN AbstractNSet::AbstractNSet(F_U f_U):m_f_U(MO(f_U)){ST_AS(is_invocable_r_v);}TE IN AbstractNSet& AbstractNSet::operator=(CO AbstractNSet&)NE{RE *TH;}TE IN U AbstractNSet::Transfer(CO U& u){RE m_f_U(u);}TE IN U VirtualNSet::Inverse(CO U& u){RE Transfer(u);}TE IN AbstractMagma::AbstractMagma(M_U m_U):m_m_U(MO(m_U)){ST_AS(is_invocable_r_v);}TE IN AbstractMagma& AbstractMagma::OP=(CO AbstractMagma&)NE{RE *TH;}TE IN U AdditiveMagma::Product(U u0,CO U& u1){RE MO(u0 += u1);}TE IN U MultiplicativeMagma::Product(U u0,CO U& u1){RE MO(u0 *= u1);}TE IN U AbstractMagma::Product(U u0,CO U& u1){RE m_m_U(MO(u0),u1);}TE IN U VirtualMagma::Sum(U u0,CO U& u1){RE Product(MO(u0),u1);} TE CL VirtualMonoid:VI PU VirtualMagma,VI PU VirtualPointedSet{};TE CL AdditiveMonoid:VI PU VirtualMonoid,PU AdditiveMagma,PU PointedSet{};TE CL MultiplicativeMonoid:VI PU VirtualMonoid,PU MultiplicativeMagma,PU PointedSet{PU:IN MultiplicativeMonoid(U e_U);};TE CL AbstractMonoid:VI PU VirtualMonoid,PU AbstractMagma,PU PointedSet{PU:IN AbstractMonoid(M_U m_U,U e_U);}; TE IN MultiplicativeMonoid::MultiplicativeMonoid(U e_U):PointedSet(MO(e_U)){}TE IN AbstractMonoid::AbstractMonoid(M_U m_U,U e_U):AbstractMagma(MO(m_U)),PointedSet(MO(e_U)){} TE CL VirtualGroup:VI PU VirtualMonoid,VI PU VirtualPointedSet,VI PU VirtualNSet{};TE CL AdditiveGroup:VI PU VirtualGroup,PU AdditiveMonoid{PU:IN U Transfer(CO U& u);};TE CL AbstractGroup:VI PU VirtualGroup,PU AbstractMonoid,PU AbstractNSet{PU:IN AbstractGroup(M_U m_U,U e_U,I_U i_U);}; TE IN AbstractGroup::AbstractGroup(M_U m_U,U e_U,I_U i_U):AbstractMonoid(MO(m_U),MO(e_U)),AbstractNSet(MO(i_U)){}TE IN U AdditiveGroup::Transfer(CO U& u){RE -u;} TE CL VirtualGraph:VI PU UnderlyingSet{PU:VI R1 Enumeration(CRI i)= 0;IN R2 Enumeration_inv(CO T& t);TE IN R2 Enumeration_inv(CO PATH& p);IN VO Reset();VI CRI SZ()CO NE = 0;VI E& edge()NE = 0;VI ret_t Edge(CO T& t)= 0;TE IN ret_t Edge(CO PATH& p);ST IN CO T& Vertex(CO T& t)NE;TE ST IN CO T& Vertex(CO PATH& e)NE;VI R2 Enumeration_inv_Body(CO T& t)= 0;};TE CL EdgeImplimentation:VI PU VirtualGraph{PU:int m_SZ;E m_edge;IN EdgeImplimentation(CRI SZ,E edge);IN CRI SZ()CO NE;IN E& edge()NE;IN ret_t Edge(CO T& t);};TE CL Graph:PU EdgeImplimentation{PU:IN Graph(CRI SZ,E edge);IN CRI Enumeration(CRI i);TE IN Graph GetGraph(F edge)CO;IN CRI Enumeration_inv_Body(CRI t);};TE CL EnumerationGraph:PU EdgeImplimentation,ret_t,E>{PU:Enum_T m_enum_T;Enum_T_inv m_enum_T_inv;IN EnumerationGraph(CRI SZ,Enum_T enum_T,Enum_T_inv enum_T_inv,E edge);IN ret_t Enumeration(CRI i);TE IN EnumerationGraph GetGraph(F edge)CO;IN ret_t Enumeration_inv_Body(CO T& t);};TE EnumerationGraph(CRI SZ,Enum_T enum_T,Enum_T_inv enum_T_inv,E edge)-> EnumerationGraph()(0)),Enum_T,Enum_T_inv,E>;TE CL MemorisationGraph:PU EdgeImplimentation{PU:int m_LE;VE m_memory;Map m_memory_inv;IN MemorisationGraph(CRI SZ,CO T& dummy,E edge);IN T Enumeration(CRI i);IN VO Reset();TE IN MemorisationGraph GetGraph(F edge)CO;IN CRI Enumeration_inv_Body(CO T& t);}; TE IN EdgeImplimentation::EdgeImplimentation(CRI SZ,E edge):m_SZ(SZ),m_edge(MO(edge)){ST_AS(is_COructible_v && is_COructible_v && is_invocable_v);}TE IN Graph::Graph(CRI SZ,E edge):EdgeImplimentation(SZ,MO(edge)){}TE IN EnumerationGraph::EnumerationGraph(CRI SZ,Enum_T enum_T,Enum_T_inv enum_T_inv,E edge):EdgeImplimentation,ret_t,E>(SZ,MO(edge)),m_enum_T(MO(enum_T)),m_enum_T_inv(MO(enum_T_inv)){}TE IN MemorisationGraph::MemorisationGraph(CRI SZ,CO T& dummy,E edge):EdgeImplimentation(SZ,MO(edge)),m_LE(),m_memory(),m_memory_inv(){ST_AS(is_invocable_v);}TE IN CRI Graph::Enumeration(CRI i){RE i;}TE IN ret_t EnumerationGraph::Enumeration(CRI i){RE m_enum_T(i);}TE IN T MemorisationGraph::Enumeration(CRI i){AS(0 <= i && i < m_LE);RE m_memory[i];}TE IN R2 VirtualGraph::Enumeration_inv(CO T& t){RE Enumeration_inv_Body(t);}TE TE IN R2 VirtualGraph::Enumeration_inv(CO PATH& p){RE Enumeration_inv_Body(get<0>(p));}TE IN CRI Graph::Enumeration_inv_Body(CRI i){RE i;}TE IN ret_t EnumerationGraph::Enumeration_inv_Body(CO T& t){RE m_enum_T_inv(t);}TE IN CRI MemorisationGraph::Enumeration_inv_Body(CO T& t){if(m_memory_inv.count(t)== 0){AS(m_LE < TH->SZ());m_memory.push_back(t);RE m_memory_inv[t]= m_LE++;}RE m_memory_inv[t];}TE VO VirtualGraph::Reset(){}TE IN VO MemorisationGraph::Reset(){m_LE = 0;m_memory.clear();m_memory_inv.clear();}TE IN CRI EdgeImplimentation::SZ()CO NE{RE m_SZ;}TE IN E& EdgeImplimentation::edge()NE{RE m_edge;}TE IN ret_t EdgeImplimentation::Edge(CO T& t){RE m_edge(t);}TE TE IN ret_t VirtualGraph::Edge(CO PATH& p){RE Edge(get<0>(p));}TE TE IN Graph Graph::GetGraph(F edge)CO{RE Graph(TH->SZ(),MO(edge));}TE TE IN EnumerationGraph EnumerationGraph::GetGraph(F edge)CO{RE EnumerationGraph(TH->SZ(),m_enum_T,m_enum_T_inv,MO(edge));}TE TE IN MemorisationGraph MemorisationGraph::GetGraph(F edge)CO{RE MemorisationGraph(TH->SZ(),MO(edge));}TE IN CO T& VirtualGraph::Vertex(CO T& t)NE{RE t;}TE TE IN CO T& VirtualGraph::Vertex(CO PATH& e)NE{RE Vertex(get<0>(e));} CL LinearEdge{PU:int m_SZ;int m_direction;IN LinearEdge(CRI SZ,CRI direction);IN VE> OP()(CRI t);};CL LinearGraph:PU Graph{PU:IN LinearGraph(CRI SZ,CRI direction = 1);}; IN LinearEdge::LinearEdge(CRI SZ,CRI direction):m_SZ(SZ),m_direction(direction){}IN VE> LinearEdge::OP()(CRI t){VE> AN{};if((m_direction >> 1)== 1 && t > 0){AN.push_back({t - 1,1});}if((m_direction & 1)== 1 && t + 1 < m_SZ){AN.push_back({t + 1,1});}RE AN;}IN LinearGraph::LinearGraph(CRI SZ,CRI direction):Graph(SZ,LinearEdge(SZ,direction)){} TE CL AbstractUnionFindForest{PU:GRAPH& m_G;ABEL_GROUP m_M;int m_root_SZ;VE m_pred;VE m_height;VE m_w;AbstractUnionFindForest(GRAPH& G,ABEL_GROUP M);CO decltype((declval().Enumeration(0)))RootOfNode(CO T&);TE TY V> VE GetRoot()CO;IN U Potential(CO T& t0,CO T& t1);IN CRI NodeSize()CO NE;IN CRI RootSize()CO NE;bool Graft(CO T& t0,CO T& t1,CO U& w = U());TE IN bool Graft(CO T& t0,CO PATH& t1);};TE AbstractUnionFindForest(GRAPH& G,ABEL_GROUP M)-> AbstractUnionFindForest,GRAPH,inner_t,ABEL_GROUP>;TE CL UnionFindForest:PU LinearGraph,PU AbstractUnionFindForest>{PU:IN UnionFindForest(CRI SZ);}; TE AbstractUnionFindForest::AbstractUnionFindForest(GRAPH& G,ABEL_GROUP M):m_G(G),m_M(MO(M)),m_root_SZ(m_G.SZ()),m_pred(m_root_SZ),m_height(m_root_SZ,1),m_w(m_root_SZ,m_M.Zero()){CRI SZ = m_G.SZ();for(int i = 0;i < SZ;i++){m_pred[i]= i;}for(int i = 0;i < SZ;i++){auto&& s = m_G.Enumeration(i);for(auto& t:m_G.Edge(s)){Graft(s,t);}}}TE IN UnionFindForest::UnionFindForest(CRI SZ):LinearGraph(SZ,0),AbstractUnionFindForest>(*TH,AdditiveGroup()){}TE CO decltype((declval().Enumeration(0)))AbstractUnionFindForest::RootOfNode(CO T& t){auto&& num = m_G.Enumeration_inv(t);int& pred1 = m_pred[num];WH(true){int& pred2 = m_pred[pred1];if(pred1 == pred2){break;}m_w[num]= m_M.Sum(m_w[num],m_w[pred1]= m_M.Sum(m_w[pred1],m_w[pred2]));pred1 = pred2 = m_pred[pred2];}RE m_G.Enumeration(pred1);}TE TE TY V>VE AbstractUnionFindForest::GetRoot()CO{VE AN{};AN.reserve(m_root_SZ);CRI SZ = m_G.SZ();for(int i = 0;i < SZ;i++){if(i == m_pred[i]){AN.push_back(m_G.Enumeration(i));}}RE AN;}TE U AbstractUnionFindForest::Potential(CO T& t0,CO T& t1){CO T& root0 = RootOfNode(t0);CO T& root1 = RootOfNode(t1);AS(root0 == root1);RE m_M.Sum(m_w[m_G.Enumeration_inv(t0)],m_M.Inverse(m_w[m_G.Enumeration_inv(t1)]));}TE IN CRI AbstractUnionFindForest::NodeSize()CO NE{RE m_G.SZ();}TE IN CRI AbstractUnionFindForest::RootSize()CO NE{RE m_root_SZ;}TE bool AbstractUnionFindForest::Graft(CO T& t0,CO T& t1,CO U& w){CO T& root0 = RootOfNode(t0);CO T& root1 = RootOfNode(t1);if(root0 == root1){RE Potential(t0,t1)== w;}auto&& num0 = m_G.Enumeration_inv(t0);auto&& num1 = m_G.Enumeration_inv(t1);auto&& rnum0 = m_G.Enumeration_inv(root0);auto&& rnum1 = m_G.Enumeration_inv(root1);int& height0 = m_height[rnum0];CRI height1 = m_height[rnum1];CO int* p_reMOd_root;CO int* p_reMOd_node;CO int* p_kept_root;if(height0 < height1){p_reMOd_root = &rnum0;p_reMOd_node = &num0;p_kept_root = &rnum1;m_w[*p_reMOd_root]= m_M.Sum(m_w[*p_reMOd_root],m_M.Sum(m_M.Sum(m_w[num1],w),m_M.Inverse(m_w[num0])));}else{if(height0 == height1){height0++;}p_reMOd_root = &rnum1;p_reMOd_node = &num1;p_kept_root = &rnum0;m_w[*p_reMOd_root]= m_M.Sum(m_w[*p_reMOd_root],m_M.Sum(m_M.Inverse(m_M.Sum(m_w[num1],w)),m_w[num0]));}if(*p_reMOd_node != *p_reMOd_root){m_w[*p_reMOd_node]= m_M.Sum(m_w[*p_reMOd_node],m_w[*p_reMOd_root]);}m_pred[*p_reMOd_node]= m_pred[*p_reMOd_root]= *p_kept_root;m_root_SZ--;RE true;}TE TE IN bool AbstractUnionFindForest::Graft(CO T& t0,CO PATH& t1){RE Graft(t0,get<0>(t1),get<1>(t1));} // AAA ライブラリは以上に挿入する。 #define INCLUDE_MAIN #include __FILE__ #else // INCLUDE_LIBRARY #ifdef DEBUG #define _GLIBCXX_DEBUG #define DEXPR( LL , BOUND , VALUE1 , VALUE2 ) CEXPR( LL , BOUND , VALUE2 ) #define SIGNAL signal( SIGABRT , &AlertAbort ); #define ASSERT( A , MIN , MAX ) CERR( "ASSERTチェック: " , ( MIN ) , ( ( MIN ) <= A ? "<=" : ">" ) , A , ( A <= ( MAX ) ? "<=" : ">" ) , ( MAX ) ); assert( ( MIN ) <= A && A <= ( MAX ) ) #define COUT( ... ) VariadicCout( cout << "出力:" , __VA_ARGS__ ) << endl #define COUTNS( ... ) VariadicCoutNonSep( cout , __VA_ARGS__ ) << flush #define CERR( ... ) VariadicCout( cerr , __VA_ARGS__ ) << endl #define CERRNS( ... ) VariadicCout( cerr , __VA_ARGS__ ) << flush #define COUT_A( A , N ) OUTPUT_ARRAY( cout << "出力:" , A , N ) << endl #define CERR_A( A , N ) OUTPUT_ARRAY( cerr , A , N ) << endl int exec_mode = 0; #else #pragma GCC optimize ( "O3" ) #pragma GCC optimize ( "unroll-loops" ) #pragma GCC target ( "sse4.2,fma,avx2,popcnt,lzcnt,bmi2" ) #define SIGNAL #define DEXPR( LL , BOUND , VALUE1 , VALUE2 ) CEXPR( LL , BOUND , VALUE1 ) #define ASSERT( A , MIN , MAX ) assert( ( MIN ) <= A && A <= ( MAX ) ) #define COUT( ... ) VariadicCout( cout , __VA_ARGS__ ) << ENDL #define COUTNS( ... ) VariadicCoutNonSep( cout , __VA_ARGS__ ) #define CERR( ... ) #define CERRNS( ... ) #define COUT_A( A , N ) OUTPUT_ARRAY( cout , A , N ) << ENDL #define CERR_A( A , N ) #endif #ifdef REACTIVE #ifdef DEBUG #define RSET( A , ... ) A = __VA_ARGS__ #else #define RSET( A , ... ) cin >> A #endif #define RCIN( LL , A , ... ) LL A; RSET( A , __VA_ARGS__ ) #define ENDL endl #else #define ENDL "\n" #endif #ifdef USE_GETLINE #define SET_LL( A ) { GETLINE( A ## _str ); A = stoll( A ## _str ); } #define GETLINE_SEPARATE( SEPARATOR , ... ) string __VA_ARGS__; VariadicGetline( cin , SEPARATOR , __VA_ARGS__ ) #define GETLINE( ... ) GETLINE_SEPARATE( '\n' , __VA_ARGS__ ) #else #define SET_LL( A ) cin >> A #define CIN( LL , ... ) LL __VA_ARGS__; VariadicCin( cin , __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 , ... ) vector __VA_ARGS__; SET_A( I , N , __VA_ARGS__ ) #define CIN_AA( LL , I0 , N0 , I1 , N1 , VAR ) vector> VAR( N0 + I0 ); FOR( VARIABLE_FOR_CIN_AA , 0 , N0 ){ SET_A( I1 , N1 , VAR[VARIABLE_FOR_CIN_AA + I0] ); } #endif #include using namespace std; #define REPEAT_MAIN( BOUND ) int main(){ ios_base::sync_with_stdio( false ); cin.tie( nullptr ); SIGNAL; CEXPR( int , bound_test_case_num , BOUND ); int test_case_num = 1; if constexpr( bound_test_case_num > 1 ){ CERR( "テストケースの個数を入力してください。" ); SET_ASSERT( test_case_num , 1 , bound_test_case_num ); } FOR( test_case , 0 , test_case_num ){ if constexpr( bound_test_case_num > 1 ){ CERR( "testcase" , test_case , ":" ); } Solve(); CERR( "" ); } CHECK_REDUNDANT_INPUT; } #define START_WATCH chrono::system_clock::time_point watch = chrono::system_clock::now() #define CURRENT_TIME static_cast( chrono::duration_cast( chrono::system_clock::now() - watch ).count() / 1000.0 ) #define CHECK_WATCH( TL_MS ) ( CURRENT_TIME < TL_MS - 100.0 ) #define CEXPR( LL , BOUND , VALUE ) constexpr LL BOUND = VALUE #define SET_ASSERT( A , MIN , MAX ) SET_LL( A ); ASSERT( A , MIN , MAX ) #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 , 0 , HOW_MANY_TIMES ) #define SET_PRECISION( DECIMAL_DIGITS ) cout << fixed << setprecision( DECIMAL_DIGITS ) #define RETURN( ... ) COUT( __VA_ARGS__ ); return // 型のエイリアス #define decldecay_t( VAR ) decay_t template using ret_t = decltype( declval()( declval()... ) ); template using inner_t = typename T::type; using uint = unsigned int; using ll = long long; using ull = unsigned long long; using ld = long double; using lld = __float128; template using T2 = pair; template using T3 = tuple; template using T4 = tuple; using path = pair; /* VVV 常設ライブラリの非圧縮版は以下に挿入する。*/ // Random ll GetRand( const int& Rand_min , const int& Rand_max ) { assert( Rand_min <= Rand_max ); ll answer = time( NULL ); return answer * rand() % ( Rand_max + 1 - Rand_min ) + Rand_min; } // Set #define DECLARATION_OF_HASH( ... ) \ struct hash<__VA_ARGS__> \ { \ \ inline size_t operator()( const __VA_ARGS__& n ) const; \ \ }; \ class is_ordered { private: is_ordered() = delete; template static constexpr auto Check( const T& t ) -> decltype( t < t , true_type() ); static constexpr false_type Check( ... ); public: template static constexpr const bool value = is_same_v< decltype( Check( declval() ) ) , true_type >; }; template using Set = conditional_t>,unordered_set,conditional_t,set,void>>; // Tuple #define DECLARATION_OF_ARITHMETIC_FOR_TUPLE( OPR ) \ template typename V> inline auto operator OPR ## =( V& t0 , const V& t1 ) -> decltype( ( get<0>( t0 ) , t0 ) )&; \ template inline tuple& operator OPR ## =( tuple& t0 , const tuple& t1 ); \ template inline tuple& operator OPR ## =( tuple& t0 , const tuple& t1 ); \ template typename V> inline auto operator OPR ## =( V& t0 , const ARG& t1 ) -> decltype( ( get<0>( t0 ) , t0 ) )&; \ template inline tuple& operator OPR ## =( tuple& t0 , const ARG& t1 ); \ template inline tuple& operator OPR ## =( tuple& t0 , const ARG& t1 ); \ template