找回密码
 注册
查看: 17|回复: 0

c语言算法填写规范总结来自互联网

[复制链接]

0

主题

0

回帖

9

积分

管理员

积分
9
QQ
发表于 2025-3-21 10:23:44 | 显示全部楼层 |阅读模式
算法 {算法代码模板,算法模板编写规范}
( x' B7 v* h6 y" UsupimoTemplate.cpp1 |! V$ L7 l% Z5 a
代码0 y) L/ h$ n9 ~
#define  ___SUPIMOenvir_
( i3 n+ S4 o" t, d7 e. ]" i* K4 C& C6 j" H+ _- i* J
#include <bits/stdc++.h>
, l) f4 Q" x1 qusing namespace ::std;% V1 w" {2 K) ]+ Y
% Z; [0 m; q9 u0 D
#ifdef  ___SUPIMOenvir_8 p9 }8 J) f6 z: r+ q. `" M
    #include "supimoDebug.hpp"
+ s8 b/ X' _, R: F#else
5 ~9 S5 A# @/ P    #define  TOstringITEMS_( ...)  ""
! \: x) d5 \$ {- u8 S    #define  DE_( ...)% @  H7 t4 d+ B( @
    #define  ASSERTcustom_( _op, ...)   assert(_op)# X7 w# r5 ~/ h; B
    #define  ASSERTsystem_( _op, ...)   assert(_op)
7 O" C6 z2 e% {2 G3 G5 l#endif& E9 n0 I7 I* p/ P) @8 a
5 Z. l( h5 C9 O
#define  ASSERTregion_( ...)  __VA_ARGS__6 _* g) A0 f$ t; t/ @+ V
#define  ASSERTsentence_( ...)
% i' Q) t/ F( L6 ~#define  EXIT_  std::cerr<< "\nExit(2267): Line("<< __LINE__<< ")\n";  std::exit(2267);
" S7 f+ _4 \; |* a, L* K4 s#define  EXITcounter_( _max)  { static int cont = 0; ++ cont; if( cont == _max){ string str = "Exit_Counter(" + std::to_string(_max) + ")"; DE_(str); EXIT_;}}6 c' Z" g1 P( d
#define  FOR_( _i, _l, _r)  for( int _i=int(_l); _i<=int(_r); ++_i)
3 z/ W/ i9 W( i: E6 N#define  FORrev_( _i, _l, _r)  for( int _i=int(_l); _i>=int(_r); --_i)
" q3 E3 Y  D4 }* k4 g7 q+ }; z! {
0 T8 o* \7 j3 F" [using Int64_ = long long;; q! b8 X& C* E' @8 S3 q

- z; g8 P, @& S6 A9 i, w4 }" n- c+ s7 Y$ ?! ^
void ___Solve_oneTest(){
. p8 W9 [& O0 d}: A# G, R" B1 {% r' d
void ___GlobalInitialze(){
. J4 a) O. e% O2 L}; i) {3 X; C9 \6 X( p0 K! G
int main(){
1 B7 f3 Q* n2 t    std::ios::sync_with_stdio(0);  std::cin.tie(0);
( a' A. k8 O7 ?' T- V0 N6 W    std::cerr.setf( std::ios::fixed);  std::cerr.precision( 9);* h2 t# m- q6 e; M
    std::cout.setf( std::ios::fixed);  std::cout.precision( 9);; i/ J9 R+ e8 K

/ p3 D# w' k  C    auto ___Solve = [](){ // Problem-Input4 U9 ?+ t8 ^+ Q8 R# ]4 ?  d' k. ~) p
        constexpr char MODEisSINGLE = 1;2 J  q6 U! h& y( `
        int testsCount;
  K4 Y6 q4 \7 Z9 y        if( MODEisSINGLE){ testsCount = 1;} else{ cin>> testsCount;}
5 E: P: g9 P& Z        for( int id = 0; id < testsCount; ++id){1 V# R: k. M+ h+ b5 R
            if( id == 0){ ___GlobalInitialze();}. k$ i3 b: e# |; Q9 k, J3 U
            ___Solve_oneTest();
8 Y, F; V5 j/ x# W6 c1 \% ?( k! M* y        }* |1 [, T, _# H( Q$ ~
    };8 Y  I" C. t+ j3 t
#ifdef  ___SUPIMOenvir_
% Y3 A: _9 v  u0 L    while( 1){
& G  X" M2 f( A( X4 s9 d        std::string flag;  std::cin>> flag;  ASSERTsystem_( flag.substr( 0, 10) == "#___Input[", flag);+ F- J) O1 }- f: @/ f' L
        flag.replace( 4, 2, "Out");0 V3 y! z0 }2 Q8 y: o9 z, G+ ]5 \
        std::cout<< "    "<< flag<< "\n";  std::cerr<< "    "<< flag<< "\n";% H  M3 Z3 r+ G
        if( flag == "#___Output[-1]#"){ break;}1 w. w4 H, [& y
//        int timeStart = std::clock();$ ?7 i8 S" P# f& b1 X
        ___Solve();
7 g2 b, L4 Q& k: o        std::cout<< "\n";  std::cerr<< "\n";, k( Q9 R/ g; j4 R6 q1 z# `- R! [
//        std::cout<< "TimeElapsed: "<< std::clock() - timeStart<< "\n";* r' ?  z: [7 d: I7 M
    }
7 L" A. o( z  b2 {9 E: i#else
" ^( x5 g% W! `    ___Solve();
9 I# `, V# D; N/ C* c2 O. z. X$ v6 c#endif
, l6 Z/ B6 L7 ]' l+ f
- R7 ^/ K; U$ b: c8 a2 [3 |    return 0;' r5 {4 X& r, B$ I( |9 M
}6 P! t) o. H. L- `
1$ v* w/ X$ s$ H0 N  b
2
, q# C& P9 |# B9 \3
: O5 P# \; o5 j' G4( d+ K0 o$ y$ n. r, V% l
5
+ B' L0 r4 i7 i1 t6" a! G9 B8 `( d1 m8 J3 f
75 x; ~6 q* w9 [$ V5 c. B
8
7 ~# ]1 _7 P7 s0 T* y+ D9 `99 |: l  D9 H, R! Y% ^" O
10
- h  h7 `/ m; Z4 ?11% g6 ^# M) n2 x0 t% \/ D  Y( w
12
5 u, F" s: {/ u1 ?; u: m134 G) l1 p2 N' W% y: U
14
! o+ j/ d, Y- w" |9 h. A154 M6 y9 _* y+ Q: {7 G2 z
169 D6 w- K! K3 l! N" t1 x# J
17
8 f4 \, U/ u# k18
# @& F. O& p# h+ t# l& z& P: f19: h0 \5 A2 P' _/ \9 T1 h
20
/ g$ M  T: \, z- k! [21
) L1 W3 `$ Z  o8 z" ~2 v, O8 j$ \221 A  g* y8 y) a6 U. Y' W, r
23
- o; s  x1 c# f! G9 j- T; [) A244 q2 E0 o/ m, U/ l  }
25
2 x' t) T5 @, ?. m* V26
4 f* _. W. }* {9 }27% M5 C0 Z% j8 m3 `3 D
28. k  F8 H& z  G5 l8 f$ Q
29. E! N4 N& k9 }" Z
30
" I7 l( I4 o1 O312 c) p! B7 K- w+ Y
329 H/ `$ h3 y! L
33
" B. X! Z, b2 U34
8 I7 X1 E- q4 f. v" X# }35
/ t+ q2 z0 V# j) w! S! n362 I: S! W! }. g" I+ F
37$ I6 S$ [/ @2 ], H3 @/ v; W
38- n( g) ?! v4 z" r
395 ]" J# D# \8 P, s! F
40- X1 m7 n/ F" B# b; D/ _' b4 X, X
41
* d1 Z! h2 s$ |* ~+ M  P+ `42
+ X! L! O  y3 S1 t  u+ `# c5 ]43; k6 |/ K/ h0 m+ @, @4 H: [
44
% b) i# q  n+ f$ ^45
7 ~( D4 ^$ Q- e2 q/ W8 X2 w! v9 T462 R0 L' M8 H  g& j
470 [7 U; E: t6 ^5 j3 f7 ]+ n  R6 K
488 l* F" w- o! Q: v4 H
494 ~- l/ Y& Z0 }7 {
50, E1 p5 \  C) E" N" D6 }
51  }7 c8 c$ m. R4 B' A
52
7 r% N  W7 G: o- M4 B$ p9 N) A2 ^53
$ n$ F2 R4 L/ D: Y54% `- M% ^6 b) W' @. d7 P4 a% Z
557 x& p7 f/ K/ B  _
560 R) W' G6 Y2 C% k# C$ ^0 V5 t
57( T) Z( `3 |" p, ]$ ]7 K0 G4 r% t2 L1 d
581 r# z. z& ]) u5 [: y2 z) x
59! b/ ?) g) F. P, e5 O  T$ y
supimoDebug.hpp
; y" u: q( V; P: P7 Y: X代码
8 I) W: g$ X" \. J' i, U  X#include <bits/stdc++.h>
' |- B, m: o7 d: \7 Q8 X
# y( h5 a' m- F6 e/ ^' o#define  VARSandLOCATION_( ...)  std::string(std::string("{File: ")+ __FILE__+ ", Line: "+ std::to_string(__LINE__)+ ", VarName: ["+ #__VA_ARGS__+ "]}")
2 |9 Z1 Z! T  H/ q$ u#define  TOstringITEMS_( ...)  ___DEBUG_::ToString_Items( __VA_ARGS__)
& w- u0 K- e* _#define  DE_( ...)  std::cerr<< TOstringITEMS_( __VA_ARGS__)<< "    "<< VARSandLOCATION_(__VA__ARGS__)<< "\n"
# q1 y4 D3 @% }& M$ F/ J1 Z#define  ASSERTcustom_( _op, ...)   if( !bool(_op)){ std::cerr<<"Assertion_Failed(Custom): ["<< #_op<< "]    {Hint: ["<< TOstringITEMS_( __VA_ARGS__)<< "]("<< #__VA_ARGS__<< ");  Line: "<< __LINE__<< "}";  std::exit(2267);}
) @4 _$ y9 u- ~3 x5 j4 ?#define  ASSERTsystem_( _op, ...)   if( !bool(_op)){ std::cerr<<"Assertion_Failed(System): ["<< #_op<< "]    {Hint: ["<< TOstringITEMS_( __VA_ARGS__)<< "]("<< #__VA_ARGS__<< ");  Line: "<< __LINE__<< "}";  std::exit(2267);}* g. B/ ?  d$ s& i
' u! |) ?9 g1 q" v+ T
namespace ___DEBUG_ {- P& {* O" D$ A  f2 Y; }. o
    //>> 所谓`Container`是指 可以通过`for( auto i : S)`来进行遍历的;  T) I% B# s1 p3 J% _/ X0 r' @! P
    template< class _t> struct __IsContainer_Unwrap : std::false_type{};7 W6 o3 ?) [( F. y4 [7 p
    template< class _t> struct __IsContainer_Unwrap<std::vector<_t> > : std::true_type{};
8 ~5 |. t# C* V/ z, M, h    template< class _t> struct __IsContainer_Unwrap<std::set<_t> > : std::true_type{};# \( y: j- o2 H
    template< class _t> struct __IsContainer_Unwrap<std::unordered_set<_t> > : std::true_type{};: z: m$ l, A2 h7 P+ d$ |- z7 S7 N
    template< class _t> struct __IsContainer_Unwrap<std::multiset<_t> > : std::true_type{};# k% C2 D) w- Y  e
    template< class _t> struct __IsContainer_Unwrap<std::unordered_multiset<_t> > : std::true_type{};
8 |8 j  Y9 P3 Q0 i3 ~2 [# {3 L    template< class _t0, class _t1> struct __IsContainer_Unwrap<std::map<_t0,_t1> > : std::true_type{};+ M! ]4 o  A' [, H
    template< class _t0, class _t1> struct __IsContainer_Unwrap<std::unordered_map<_t0,_t1> > : std::true_type{};. H( F5 y7 O; W& ~
    template< class _t0, int _t1> struct __IsContainer_Unwrap< _t0[_t1] > : std::true_type{};
9 V  }  P; i2 \9 F7 W' q/ n    template< int _t1> struct __IsContainer_Unwrap< char[_t1] > : std::false_type{}; // 特判, 字符串常量"..."不属于容器;- G& d8 Y, @2 y7 O) X' L2 u
    template< class _t> struct IsContainer : __IsContainer_Unwrap<std::remove_const_t<std::remove_reference_t<_t> > >{}; // 不能用`decay` 否则`T[N]`就退化为`T*`了;
# r3 \, J" [) y3 h  Q+ ~0 f: \! N
( N2 r$ w! f6 b, t* A% o& z    template< class _t> struct __IsPair_Unwrap : std::false_type{};+ M( m. p6 G; g" a0 G0 @" }
    template< class _t0, class _t1> struct __IsPair_Unwrap< std::pair<_t0,_t1> > : std::true_type{};
/ j, |& G+ c) Q8 k* |. l    template< class _T> struct IsPair : __IsPair_Unwrap< std::decay_t<_T> >{};8 j) V' o* v& n) J" p" Y
3 f& |8 M/ V: ]5 ?1 S
    template< class _t> struct __IsStack_Unwrap : std::false_type{};  t0 i" [4 P' b) r! W) ]+ z
    template< class _t> struct __IsStack_Unwrap< std::stack<_t> > : std::true_type{};0 f# ]; u6 D, {, V0 @) t0 d
    template< class _T> struct IsStack : __IsStack_Unwrap< std::decay_t<_T> >{};' l! |2 x) I2 n& a

! b6 F4 W1 U: T2 ]6 U; u7 w. T1 P0 W/ Z    template< class _t> struct __IsQueue_Unwrap : std::false_type{};
* g! J9 `5 t9 o$ B: W1 S    template< class _t> struct __IsQueue_Unwrap< std::queue<_t> > : std::true_type{};
" {, N/ n1 E) l3 \$ D    template< class _T> struct IsQueue : __IsQueue_Unwrap< std::decay_t<_T> >{};% M" s) A7 [. l3 u' w

0 x/ m0 D2 k! {# ?( B; b7 `4 O    template< class _t> struct __IsDeque_Unwrap : std::false_type{};
/ i" a& U, Y9 L5 e# O5 D' Z$ @    template< class _t> struct __IsDeque_Unwrap< std::deque<_t> > : std::true_type{};9 r/ }7 P; Q% ^  }! V: \; c# J
    template< class _T> struct IsDeque : __IsDeque_Unwrap< std::decay_t<_T> >{};
5 m. F9 N/ h% \- g7 e0 F) Z' j) t# E! s9 K8 `9 r1 D
    template< class _T> std::string ToString( _T const&);% x8 T0 C( W+ R7 B  S( P! {; k
! H: s1 [9 e2 i% ]6 G
    template< class _T, int _Check> struct __ToString_Category;
8 b0 D1 p* p+ f- J; |3 U    template< class _T> struct __ToString_Category<_T, 0>{ // Single5 y% P- Q* h! H  ~" o+ H
    template< class _t> static std::string TOstring( _t const& _v){
  G$ f: O$ _3 y9 p- o* c        std::ostringstream ANS; ANS.precision( std::cout.precision()); ANS.setf(std::cout.flags()); ANS<<_v;1 ~' Q& t# R3 m' P& l8 V+ H3 E) z
        return ANS.str();  K' Y& Y9 N9 E
    }2 |8 l8 o7 B; C. i7 I* O0 c' }  m
    static std::string TOstring( unsigned __int128 const& _v){ auto v = _v; std::string ANS; if(v==0){ ANS="0";} else{ for(;v!=0;v/=10){ ANS+=('0'+v%10);}  std::reverse(ANS.begin(), ANS.end());}  return ANS;}
* }0 S# C! S$ I# h% V    static std::string TOstring( __int128 const& _v){ std::string ANS; auto v = _v; if(v==0){ ANS="0";} else{ if(v<0){ ANS+="-"; v=-v;}  for(;v!=0;v/=10){ ANS+=('0'+(v%10));}  std::reverse(ANS.begin()+(ANS[0]=='-'?1:0), ANS.end());}  return ANS;}, @+ M; w/ P- I: ?2 M: }: i
    static std::string TOstring( bool const& _b){ return (_b?"1":"0");}0 q- i0 F4 E$ X- G# M* Y
    static std::string TOstring( char const& _a){3 a9 |4 i0 ?, Q0 \) |' a: T  _
        if(_a==0){ return "'\\0'";} // 否则因为她是*结束控制符* 会导致`ostream<<char(0)<<A;`后面的`A`不输出了;
+ d7 c! L8 m$ z* M, \( c! t        std::string ANS="'?'"; ANS[1]=_a; return ANS;. b5 i4 m, e' v; x$ H
    }# T$ e5 D2 Y9 b
    static std::string TOstring( char const* const& _s){ return std::string(_s);}
% W9 \4 B/ r9 Z9 B    static std::string TOstring( std::string const& _tt){ std::string ANS="\""; ANS+=_tt; ANS+='\"'; return ANS;}. P& _- N" P: N' r; E
    };# @5 D& e  U4 @( t- b
    template< class _T> struct __ToString_Category<_T, 1>{ // Container4 t, W" ?0 n0 L9 s+ x! p5 ^
        template< class _t> static std::string TOstring( _t const& _v){; T% i, G5 |# s
            std::string ANS="["; bool first=1;
- e4 `" r$ g! I7 z4 D! q7 N) X            for( auto const& i : _v){ if( 0==first) ANS+=","; if( first) first=0; ANS+=ToString(i);}
8 D( ?( W& }. P" S3 J8 V            ANS+="]";" |8 k$ ]5 o$ h# z/ i$ a
            return ANS;
$ T* b5 ~1 I! i2 J) S$ y        }
! r4 }8 Y" h7 q1 @    };% x* B" [) f4 }" y, p
    template< class _T> struct __ToString_Category<_T, 2>{ // Pair
; j1 o- i, S( T, N, \: n        template< class _t> static std::string TOstring( _t const& _v){ std::string ANS="("; ANS += ToString(_v.first); ANS+=","; ANS+=ToString(_v.second); ANS+=")"; return ANS;}
4 M$ Q* P/ |5 I9 y# ~& P' G: t    };! B; s! L+ l$ T$ y
    template< class _T> struct __ToString_Category<_T, 3>{ // Stack
. S& F/ {* i9 ~+ |/ ]7 x! A+ O        template< class _t> static std::string TOstring( _t const& _v){ std::string ANS="Stack(top)[";  auto t = _v;  for( bool first=1; t.empty()==0; t.pop(), first=0){ if(first==0){ ANS+=",";} ANS += ToString(t.top());} ANS+="]"; return ANS;}/ e- N- c: B; j2 u8 y4 W$ ~3 y) v
    };
( _# g( ~  `2 I6 L    template< class _T> struct __ToString_Category<_T, 4>{ // Queue# d, O' _$ h% o* @& l
        template< class _t> static std::string TOstring( _t const& _v){ std::string ANS="Queue(front)[";  auto t = _v;  for( bool first=1; t.empty()==0; t.pop(), first=0){ if(first==0){ ANS+=",";} ANS += ToString(t.front());} ANS+="]"; return ANS;}
# O8 ^5 ?: [; D' `% L" s! N# n0 D    };
$ d; ~0 B3 x0 E" B: k* v/ r    template< class _T> struct __ToString_Category<_T, 5>{ // Deque5 G7 ]" T1 B' X7 C$ |! N" v7 z
        template< class _t> static std::string TOstring( _t const& _v){ std::string ANS="Deque(front)[";  auto t = _v;  for( bool first=1; t.empty()==0; t.pop_front(), first=0){ if(first==0){ ANS+=",";} ANS += ToString(t.front());} ANS+="]"; return ANS;}
, b: e+ p; H) y. C( }! a    };% N# U( ~8 V( T" s8 B

! C- [! C: S6 _& x8 h0 k    template< class _t> struct __ToString : __ToString_Category<_t, (IsContainer<_t>::value ? 1:(IsPair<_t>::value ? 2:(IsStack<_t>::value ? 3:(IsQueue<_t>::value ? 4:(IsDeque<_t>::value ? 5:0)))))>{};
/ P  N! L  b4 k+ \$ D% W6 q) E" `
    template< class _t> std::string ToString( _t const& _v){ return __ToString<_t>::TOstring(_v);}8 q  C; J  t' h- G& H
: F7 e) |/ [# v( ^  L0 r
    template< class... _H_> std::string ToString_Items( _H_ const&...){ return "";}
5 c9 b+ a- Z# P; D9 Q4 b  q& K% Z    template< class _H_> std::string ToString_Items( _H_ const& _h){ return ToString(_h);}
& @3 g, u6 A; K    template< class _H_, class... _T_> std::string ToString_Items( _H_ const& _h, _T_ const&... _t){ std::string ANS; ANS+=ToString( _h); ANS+=", "; ANS+=ToString_Items( _t...); return ANS;}
" V9 Y3 _2 n! o; q5 s% b% I4 Y}1 a; `# k1 G$ b

: t+ ]5 t1 L, ?( e1$ X' G3 N( i% [! v
25 u- Z$ Y6 H9 F1 `0 t
3$ h" u) ^) v6 P: t( b
4
" V/ e0 A; v. x4 U5* M# E' |4 ]  y9 b
6) A# \/ S4 E, v- R( a1 N' h
7
9 U# ~: a3 {8 }) n7 Y$ Z8
9 K/ Z% X9 J" U94 T- v# ]! ]( E( R% `, \3 J6 q% @/ `' @" F
10
  r9 I: N+ r0 |8 A. m11
- ~% L( p( L1 b2 P; c7 P- ~* F12
" I7 H- y$ y( m) ]) l13
* C7 z+ Z8 h- ]( A145 D9 A& Y$ W3 [5 w2 i
15
6 ]% i; l8 P5 f166 c" o8 p* q3 F
17( N; C4 u& G2 Y; p% q
18- p1 }0 O1 R. @% z" ?" K
19' N- Z( M( y8 l4 z" {. c% J
20# _: y3 A. _1 a# }: i* z& q
21% S! Y5 k6 k' ~( m4 ~2 _
22
' [/ H% s6 r/ x1 `, r" s9 u- ^8 b231 i4 U. l# T$ @" |
24) N+ F1 a8 H( ^
25+ O0 x$ x3 _9 h8 \# }
26
1 E1 e6 y# P. A3 @. _! Z27, b' j6 P8 {6 z+ e$ C% N
28
4 r3 ~- N+ x7 J  D. ~5 e4 G. o29
0 V" }& _+ b" o; `1 o) y30
7 t& g& {! y6 n4 U5 X/ w31
, m( |2 }4 Y( F3 Y, t# P( g32$ X7 @2 l) n6 F$ h1 U# _
33
- ~! h; x5 O' p5 [' d5 p+ e34
2 {; ?1 g7 F; s( E5 r35
: \2 y8 N- m: m0 T9 V7 i36; O. c) X2 Q# p1 x; v
370 d) n% u# K2 [
38
( G, r7 n/ G) B: P* b: X- n39* D" o: Y1 }' h4 [. n
40
5 g3 V9 P, `3 ?1 _41
) H% t3 u8 m1 W% \- ]429 c! x" L2 ?, y8 |% _: ^1 {7 K: z
43
! K- i. n3 m! b* O. j44( n# W. }- v, E1 |" l# f
45
3 h( V- e8 Q% f/ _  M46* G8 i5 W5 u0 r% x& s3 n" o, m
47- i5 B- W" Z/ f" s0 G4 ?/ m8 q; s
48+ Z: D8 m7 q8 O* x1 w) W
49
. r4 I/ w- [' u( j! U50
( Z4 ]. z7 o( o5 a- V51% X, v4 ?' h: x1 ~( E
52# K5 S+ I" U" k. w. p
53
7 E8 }( K( E$ A. n7 }' k: x54
5 ]! B6 U" y: Y( z- t2 H55
- _2 |* P0 I0 k1 p56; G: A- u& h3 [: h7 }0 l
57
' R. y1 q8 D% i: `" m, t58" V  _+ l' l% F# }. x
59; \# I# V& G- E0 F8 S! a
605 R5 F) o! M" e* ]# A. M
61: n1 f4 X4 Z0 d# b3 u6 S7 i
62
, u1 e) |& t9 V: B63
4 y0 f; s& J% r3 a1 x/ R8 D64
; S+ o; j& l8 i/ J) T" d9 p; _65
* c, h% J8 ]- P! f66
6 q: u9 G1 ]$ T8 T6 F67! e3 A; r2 h4 D
68; ~1 A0 U% c/ m( R/ B" j5 f
69
6 b0 J/ U. r+ y9 P7 r703 D% x: O- S% j" ~: i
71
* N$ t2 A3 W/ n* \$ x6 I1 ]728 h9 G. o/ O7 ?5 K7 C. P3 r! ]  U+ T
73, F# h  E, A, q5 I
74/ d% x7 X$ y! j: o0 k. Z
752 U/ b8 n/ I6 o% ]6 `
76( h9 z' l) P$ o
77
4 E  _. X" p' V+ H; F0 v; r78
. I1 q- t5 v$ i2 l4 p; Y# B, w4 d79
# [  I# k, a5 e+ m1 S8 ^4 [808 U8 X1 c% [  @# G
81
6 {  f( S7 G& a" {. Z82
7 }+ @, q( Y: ?( F5 V3 z1 H. t/ ~83
0 g. }8 U4 H& |* Z2 d- S. a& J84
/ J8 M) I7 o  h9 p85. A$ O. u  t! F" ^) z$ e
86+ t* U: H! S1 B; d
性质. T1 B, p' T6 C0 u7 m, g) z
#TOstringITEMS_#8 \1 D' w! W6 `6 C& s. f
这个宏 是为了: 对类进行输出时 可以直接_cout<< TOstringITEMS_(成员变量...);4 o- p% d* m' v- |5 e$ @/ [. X
你可能认为, 直接_cout<< ___Debug_::ToStringItems(...)不就行了?+ P" w/ {2 e* n) K+ G/ \- M  p% Z3 S
. 错误, 因为在最终文件里 是看不见___Debug_的, 所以写成一个宏 在最终文件里 #define TOstringITEMS_ "";4 L. j' C, M  ?# t/ `

9 l7 }8 }/ a! j& ]6 ]! g3 K( I笔记
$ e  `! s$ y4 e#以前的debug.hpp#8 |: \8 s8 H0 b
" J/ J' M# F" Y+ @# f% D
//{ omipusDebug.hpp
2 X' w6 X9 d) A; h& ^  v" W#include <bits/stdc++.h>
! N, I: G# q8 y  n6 c/ Q& a' y0 G3 f
) L) k1 W9 c& j1 A+ A5 k#define  TOstringITEMS_( ...)  ___DEBUG_::ToString_Items( __VA_ARGS__)4 q0 R4 }8 M2 A( D/ H
#define  DE_( ...)  std::cerr<< TOstringITEMS_( __VA_ARGS__)<< "    "<< "{"<< "Line: "<< std::to_string(__LINE__)<< ", Var: ["<< (#__VA_ARGS__)<< "]"<< "}"<< "\n"
" J% i1 f; B3 F6 S: N#define  ASSERT_( _op, ...)   if( !bool(_op)){ std::cerr<<"Assertion: ["<< #_op<< "]    {Info: ["<< TOstringITEMS_( __VA_ARGS__)<< "]("<< #__VA_ARGS__<< ");  Line: "<< __LINE__<< "}";  std::exit(2267);}/ h5 S6 E0 w* b; R* l
#define  ASSERTsystem_( _op, ...)   if( !bool(_op)){ std::cerr<<"Assertion(System): ["<< #_op<< "]    {Info: ["<< TOstringITEMS_( __VA_ARGS__)<< "]("<< #__VA_ARGS__<< ");  Line: "<< __LINE__<< "}";  std::exit(2267);}: n& l7 A: v2 ~, c9 A5 n% M. H

; A$ I) |7 n" {% A4 b3 `namespace ___DEBUG_ {
% G4 v% y. H4 F8 Q    template< class _t> struct __IsContainer_Unwrap : std::false_type{};  // 所谓`Container`是指 可以通过`for( auto i : S)`来进行遍历的;3 b" z; t. }' b8 T9 j4 p4 Y9 N; s; }
    template< class _t> struct __IsContainer_Unwrap<std::vector<_t> > : std::true_type{};% q6 H1 G! k5 O" o3 P
    template< class _t> struct __IsContainer_Unwrap<std::set<_t> > : std::true_type{};
9 S( Y2 o% n7 \6 [# G- j3 q" G    template< class _t> struct __IsContainer_Unwrap<std::unordered_set<_t> > : std::true_type{};% c& o( M7 _; t9 l* K# k4 K3 V
    template< class _t> struct __IsContainer_Unwrap<std::multiset<_t> > : std::true_type{};& A3 _# H2 Q" v6 H: i2 z
    template< class _t> struct __IsContainer_Unwrap<std::unordered_multiset<_t> > : std::true_type{};
" U2 v' M& T9 y; X, n    template< class _t0, class _t1> struct __IsContainer_Unwrap<std::map<_t0,_t1> > : std::true_type{};! a7 R9 S6 j' v0 B6 G" ^" t
    template< class _t0, class _t1> struct __IsContainer_Unwrap<std::unordered_map<_t0,_t1> > : std::true_type{};9 H- z- ~% ]( {
    template< class _t0, std::size_t _t1> struct __IsContainer_Unwrap< _t0[_t1] > : std::true_type{};
- W. q! K6 V# o8 d    template< std::size_t _t1> struct __IsContainer_Unwrap< char[_t1] > : std::false_type{}; // 特判, 字符串常量"..."不属于容器;
" d. E) m2 {! P* ]5 |+ P    template< class _t, std::size_t _siz> struct __IsContainer_Unwrap<std::array<_t,_siz> > : std::true_type{};* N" g% g9 D0 d# R
    template< class _t> struct IsContainer : __IsContainer_Unwrap<std::remove_const_t<std::remove_reference_t<_t> > >{}; // 不能用`decay` 否则`T[N]`就退化为`T*`了;3 o4 O) p, Y3 K4 f* |( h
2 K; o5 t3 p6 g7 z/ E
    template< class _t> struct __IsPair_Unwrap : std::false_type{};: Q7 O: \1 M& [7 _1 q; v# k. p3 o
    template< class _t0, class _t1> struct __IsPair_Unwrap< std::pair<_t0,_t1> > : std::true_type{};
" n# _' o1 s2 `  o1 g8 `    template< class _T> struct IsPair : __IsPair_Unwrap< std::decay_t<_T> >{};
- @. @5 \+ u; [* b# E, v! a' l+ k8 T
    template< class _t> struct __IsStack_Unwrap : std::false_type{};
" J( @+ ^; w& V" r, v) `    template< class _t> struct __IsStack_Unwrap< std::stack<_t> > : std::true_type{};+ d' W8 l$ P8 }9 T; l& b# [
    template< class _T> struct IsStack : __IsStack_Unwrap< std::decay_t<_T> >{};
& k7 T) u; a7 j6 q3 r7 J- ]" V' J
    template< class _t> struct __IsQueue_Unwrap : std::false_type{};! _* f) ^7 Q  W- w
    template< class _t> struct __IsQueue_Unwrap< std::queue<_t> > : std::true_type{};& t, r" M$ H, f- M+ `2 l
    template< class _T> struct IsQueue : __IsQueue_Unwrap< std::decay_t<_T> >{};7 ?: }' i( B: A. a
( |' d3 p! l: i- {9 o5 p" O0 z
    template< class _t> struct __IsDeque_Unwrap : std::false_type{};
# u+ m: F/ [4 C) a8 m    template< class _t> struct __IsDeque_Unwrap< std::deque<_t> > : std::true_type{};
' ^2 ?! G& _1 M) a! M    template< class _T> struct IsDeque : __IsDeque_Unwrap< std::decay_t<_T> >{};3 q! D& F$ J9 o8 q/ d
: U( n0 \3 w1 C/ h
    template< class _T> std::string ToString( _T const&);) W: `5 ], P- b. R: E

+ u1 A6 L& r+ v: z    template< class _T, int _Check> struct __ToString_Category;1 O  ]4 f4 U) S  y2 ?' V
    template< class _T> struct __ToString_Category<_T, 0>{ // Single
3 Q) B7 Q9 R' x( y- K        template< class _t> static std::string TOstring( _t const& _v){
; J# E6 L9 m* T            std::ostringstream ANS; ANS.precision( std::cout.precision()); ANS.setf(std::cout.flags()); ANS<<_v;
0 c6 T; Z( e1 P            return ANS.str();, M0 q* y1 x; z7 I" D7 b
        }" J6 \/ N& X. G2 X7 e4 e# v" ^
        static std::string TOstring( unsigned __int128 const& _v){ auto v = _v; std::string ANS; if(v==0){ ANS="0";} else{ for(;v!=0;v/=10){ ANS+=('0'+v%10);}  std::reverse(ANS.begin(), ANS.end());}  return ANS;}% J# B% e% |& C# @4 ^
        static std::string TOstring( __int128 const& _v){ std::string ANS; auto v = _v; if(v==0){ ANS="0";} else{ if(v<0){ ANS+="-"; v=-v;}  for(;v!=0;v/=10){ ANS+=('0'+(v%10));}  std::reverse(ANS.begin()+(ANS[0]=='-'?1:0), ANS.end());}  return ANS;}
6 K- c9 m8 D& d& V% [        static std::string TOstring( bool const& _b){ return (_b?"1":"0");}
- [$ R& @8 X. m9 @9 f7 `. `        static std::string TOstring( char const& _a){- B# t- V5 M5 D1 e2 t6 {3 ]
            std::string ANS="'?'";, O# A/ L9 [" ^8 \
            ANS.replace( 1, 1, std::to_string(_a));
1 w, o- U, @' x$ j$ x            return ANS;) N7 n: G1 D" G& h; x8 l% M& o  i; N
        }& S- N$ V. U! o7 a; @
        static std::string TOstring( char const* const& _s){ return TOstring(std::string(_s));}) Y" W8 X$ c' M8 W4 B7 I( B
        static std::string TOstring( std::string const& _s){ std::string ANS="\""; ANS+=_s; ANS+='\"'; return ANS;}
) U" w. j+ {& E& \    };8 ?7 \9 b$ \1 F7 m7 l% i5 Y
    template< class _T> struct __ToString_Category<_T, 1>{ // Container
, G3 @0 b5 Y& `% @9 g: b' @) K        template< class _t> static std::string TOstring( _t const& _v){0 s* a1 I& _0 }/ x
            std::string ANS="[";  bool first=1;  for( auto const& i : _v){ if( 0==first) ANS+=","; if( first) first=0; ANS+=ToString(i);}  ANS+="]";
5 j: V& P, h' I" u# f9 o  G8 H- Z; i            return ANS;) b/ H, |2 z* m& x9 E$ V8 e: b. R* m
        }5 z3 w. T( T; z
    };
& X# J/ M: W! ]) e6 T, o- ]* ^7 T    template< class _T> struct __ToString_Category<_T, 2>{ // Pair
& W+ O! n) j- s        template< class _t> static std::string TOstring( _t const& _v){ std::string ANS="("; ANS += ToString(_v.first); ANS+=","; ANS+=ToString(_v.second); ANS+=")"; return ANS;}, {7 e  x5 l* M9 {  ]# p+ ]9 B4 {
    };+ [6 S6 l& f4 D& C4 x
    template< class _T> struct __ToString_Category<_T, 3>{ // Stack+ W, G7 X4 S/ d# ]1 j
        template< class _t> static std::string TOstring( _t const& _v){ std::string ANS="Stack(top)[";  auto t = _v;  for( bool first=1; t.empty()==0; t.pop(), first=0){ if(first==0){ ANS+=",";} ANS += ToString(t.top());} ANS+="]"; return ANS;}
1 o/ t0 h& h) D3 `. H. c! r3 M    };, l* ~/ X( k- Z. c4 i, b& M
    template< class _T> struct __ToString_Category<_T, 4>{ // Queue2 J1 l% g  a$ ^" A$ x. V
        template< class _t> static std::string TOstring( _t const& _v){ std::string ANS="Queue(front)[";  auto t = _v;  for( bool first=1; t.empty()==0; t.pop(), first=0){ if(first==0){ ANS+=",";} ANS += ToString(t.front());} ANS+="]"; return ANS;}
0 D4 c8 ]; G! k9 M. e5 Q9 ~, Q4 z    };
( \5 x, Q3 ]) i+ G% K2 E0 P    template< class _T> struct __ToString_Category<_T, 5>{ // Deque
/ N( X: Z  k, l6 C6 }        template< class _t> static std::string TOstring( _t const& _v){ std::string ANS="Deque(front)[";  auto t = _v;  for( bool first=1; t.empty()==0; t.pop_front(), first=0){ if(first==0){ ANS+=",";} ANS += ToString(t.front());} ANS+="]"; return ANS;}
; m) A# Y+ {# m+ F$ I/ D    };
: E7 K: {2 a7 h+ `7 Z6 M2 V
$ N, }/ r4 u& ?7 ?6 c    template< class _t> struct __ToString : __ToString_Category<_t, (IsContainer<_t>::value ? 1:(IsPair<_t>::value ? 2:(IsStack<_t>::value ? 3:(IsQueue<_t>::value ? 4:(IsDeque<_t>::value ? 5:0)))))>{};3 }; c# r* Q8 N% n$ u
  r  r( b' D- |' @" ?
    template< class _t> std::string ToString( _t const& _v){ return __ToString<_t>::TOstring(_v);}
8 ~5 U1 _0 Z# A
6 g7 T& N! ?, w% d    template< class... _H_> std::string ToString_Items( _H_ const&...){ return "";}
( U3 l7 q" S' c  ?    template< class _H_> std::string ToString_Items( _H_ const& _h){ return ToString(_h);}. R5 j8 d) c' i2 d
    template< class _H_, class... _T_> std::string ToString_Items( _H_ const& _h, _T_ const&... _t){ std::string ANS; ANS+=ToString( _h); ANS+=", "; ANS+=ToString_Items( _t...); return ANS;}
, ^" X; ~. s" |/ {}
6 d: A7 m% |7 }//} omipusDebug.hpp  M  x6 J4 g* U
1. M+ S: w! S7 u/ v% G! `
2& A; G$ L7 y' C, u4 e8 @
3
# a" @4 a- w; |' f, }: f4- u8 t) A' f) d$ {/ @0 Z
5
% c6 U$ }1 J# C& G6 p+ N! J61 n! ]7 m; F* {% Y* r$ |$ `
7! U. n$ F4 Z" H# {
8  j& R0 U2 J& t- E) @3 V
9$ V+ B: x' u6 e* T- Y0 J( \. i! J
10: X, n0 T* B, i
11
6 B0 X, k, w, C' V' T7 M8 p0 d126 C/ i$ m3 v! O; B
13
  h6 _, \6 D& g4 U6 H. s6 e+ L6 p14
7 E& n" y1 {' O; G  e15
/ T  Y4 E! j8 q# H' C6 |, E9 e16  L# o$ q: X- h% _
17
! ^" N" `" O9 A18
0 a# i  b5 f2 J8 p, s, P2 J19' b3 S5 c. {8 x# o6 h3 [
204 e# G  }/ ]" K+ W7 F, c  `; Q
21
. [' _/ h/ W# A% Q+ f22
, P# P) j3 _% Z  W. ~23
3 F3 i* ]) o2 O/ P. o4 D24( k. |5 u& P# h: ]+ Q( K
25
9 Y  `4 o7 s( r& w  ?9 w$ e% G26# X1 Q  X& c! O$ C* S# w+ V
27# @, ]' q9 L" N4 L4 C
28
( H+ C) q8 s2 [* Z, l0 t  |29
9 `; r8 N! V  ]" \30, I- g5 \- @% m9 [/ ^; f6 N) j
31
) w1 v/ {/ s# s; P) d; h8 ~; W9 n( F32& T& \6 R6 t; a# J* }* V
33
! v* O7 `1 r5 u$ [2 a2 F0 i3 D34' J- s$ m$ j' o8 @) c
35/ I) i3 i+ n! P3 C: [) C' {0 g! V0 n8 H
365 T6 x6 R5 X  v7 {+ D
37
0 s/ H* K3 G' P38
6 L8 G. U) n$ X) Q  r' j6 @39
: \- u% u) U  b* I+ |5 h: H40# y5 Z/ Z4 x% M( i5 E
41$ j. I( L! R; |% }8 {! A8 X
42
8 A, E2 m2 G1 G' t; p( C43
: F& H9 {+ w9 R% Z3 H# v! R44
1 G  x) p# f+ _451 c8 s4 h& N+ f( Z, K7 Q1 {; m! v
463 \; S, E) ?" V+ I" X2 G! D
47
9 S% I( \5 Y7 {" ~5 S% B1 a48
6 Z% d" d% Q- l: D49: T* x4 h" ?+ J
50+ e& u! |: t4 _2 s3 i
51
6 z1 e2 {" [; u. v- s: ^# M% I52
; O. ?/ F- k; m1 X: l; n' q* ^7 ?" \6 V53" f7 C: `0 G2 |: `; K& Y( P
547 X: r4 u) A- |+ y7 l# F
55, Q) C: _  v! ?  R8 a2 N3 }
56: g" x7 B0 F+ K, [/ _! C# f! I
57
; X8 {0 n8 m' s* Y$ @58
' X$ O  v( Y% B: N, t59+ C# {& d+ A  d2 h' i
60
3 o* S' W; D! J* H0 J+ n61
- u" {5 W# B* H6 A5 a62
9 I0 {: V$ s5 g# G; L" I; I63
: ^) l  a- r, ~, x, ^64
6 n6 F3 o  K" `* r1 V65
" z4 f0 t6 W8 a8 T% {) `66
$ P) U7 v1 q4 l3 L3 U67' V5 H5 T. {0 V. w
68
6 q2 q/ F9 I; J' m& p) |& [. Q69
/ k; ~" d. q) W70
3 G1 |1 V4 C/ [- f71
% E8 p9 `- c: j! w9 k724 {! T4 R" U+ o$ M1 b! e: q
73
5 Z  [1 z& X" Y/ ^5 k74
% S2 C2 Y+ j% |7 y75
$ y% r* H1 z: H" K& A! M  F* n! Y1 c766 g  O& `" C5 d7 D& Q- |( E! \
77
! y8 c; L6 H9 b  I; E787 g, x" t" H5 N1 [# l
79
: b* f3 l) L) r* L, ]* F7 X80
3 u3 F* Q/ I: X5 o0 s81* d9 R5 Z' e) ^0 G1 [
82; M& o' N' K1 A
835 ^9 q+ D, e# J1 E, K
84* k% U) |* z$ V( M  b& k/ [
852 w+ M: g# Y1 O" i$ u( C' q" A% u
算法競賽配置& X0 d$ J9 R. \' O! V( x1 m: O8 o
QT_Creator
! ]: n5 I5 Z, ]( j/ d  R8 ]+ M創建一個控制臺應用, 然後在Pro文件裏 添加CONFIG += c++17 (原來是c++11 修改成17);, o3 l! n8 P2 o6 f6 Z

9 n5 |5 [5 H8 P+ I( I$ Q對拍文件
% a5 I4 ~  o! I% R! L* ]+ p2 X`compare.cpp`
1 J7 ~2 d$ J3 _7 T8 J8 I* D; F7 ~
$ T, |3 i% x4 jint main(){. W3 ?' v! [5 t& L
    vector< const char *> Init{"build.bat  generate_data",
* E: S- V1 D' {2 |& L7 ^                              "build.bat  supimo"," C$ U! k/ A% `: E1 y' E+ H, D% F
                              "build.bat  correct"};/ N# g% k5 h) k0 }# h. O: U
    for( auto order : Init){; T# g' x- }2 q; t& H9 m! U
        auto errorCode = system( order);" {+ ~( m  V5 U' _7 M5 v
        if( errorCode != 0){ EXIT_( order, errorCode);}- n* c2 W  ~. {
    }9 ]) |/ m0 n  ^) H- k* a, q6 @9 m
6 S7 H) g& }% _, |
    while( true){
8 I/ B2 h7 ?% \$ L; k: D( [4 K        static const char * Ords[] = {"generate_data.exe > data.in",
0 r: D0 ]" d1 [3 e/ e4 _3 {! t1 B                          "supimo.exe < data.in > supimoOutput.txt",' q1 [6 A6 {. r0 z
                          "correct.exe < data.in > correctOutput.txt",2 N1 G0 H& m: o. n
                          "fc supimoOutput.txt correctOutput.txt"};
/ J4 _( a4 F9 Y* ]- W/ u        for( auto order : Ords){
1 f, J: m5 d9 A1 S. ^& z) O            auto errorCode = system( order);: H. i- z% V1 c" \1 x" g- C: M6 e
            if( errorCode != 0){ EXIT_( order, errorCode);}$ j% u! ~7 c9 }' r) {
        }; C, o! @# ?$ f5 S4 }
        cout<< "SUCC"<< endl;0 R3 I' G' G) |: _# x2 q( \
    }
4 |, U0 P- }7 G5 [+ C7 ~
$ n0 l7 }$ Q9 j5 L/ n) p. V    return 0;; N6 m7 L3 \, m# f! b
}
  B$ [. Y& ^) P: H$ H1* L2 u9 |8 ?* H
2: i' V2 k$ q$ m; u. A3 C
3  z2 v$ i6 d7 B" L5 @9 E$ r
4
0 m& c$ s: i. F4 m5; I7 H. I" h$ \. S3 R
6
; e6 [: s! G* R- I1 y7
% b" [# U) o* W# D* N3 H8
- D. \' x6 F( [/ Y" b7 Y& X6 t1 C93 E3 f7 }6 x/ Y$ F
10& a6 p: Y4 Y5 z
11& K* c4 k& d# q3 X0 e
12
3 L9 t9 R9 [. d7 H; \13
0 B4 e# }" J+ ?7 X14
/ O" w* P2 @+ Q7 m  V* o! u: l15
9 g0 w0 ~- t* D2 _; e% b16
( r9 k9 N2 f4 u$ Q  s17
9 X* T$ n2 n+ \. m# B0 E5 {: ]/ }180 T8 o- c9 ?9 o" ~3 \4 t. J' D
19
2 S* [7 }: r- }20% k2 U* H  ?. z( _  j: i: }, ~
21
6 Z, l% ^* F3 M22% Y- k/ }2 O0 W2 O0 @# r
23& i, e. h7 |: ?' d+ f5 c/ G
24
* P1 w* m; a, [& i5 A258 E" m, _7 T$ k7 |/ a9 g$ B
Bat代碼
4 Q, c' ^) ]6 T" j+ e, m8 {build.bat* ~% j# j1 C/ n: d, H) P* T4 z
@echo off
8 g5 g1 k2 i" g$ J  o) M* S% Adel  %1.exe! M8 k( {: ^3 {3 K) k) q4 n
g++.exe  %1.cpp  -o  %1.exe  -std=c++17  -O2  -Wall -Wl,--stack=268435456 -D"__ISsupimoENVIR_"
! M" E. F% H0 v) J7 ?& c. Y$ [
$ T' o4 g3 H. L9 v, k5 q@DELI;
- j# g4 X/ y, d- m3 [% [2 i5 a# E/ X: \; a. G! ^7 }$ D, q5 Q; g
run.bat0 T: @# h) L9 ^7 n3 A1 ^: c9 q/ l' F
@echo off6 S) s" _- A2 d1 `9 ?& x
%1.exe  <  input.txt4 i1 G: r% G# f3 o5 h* X

) L" ~3 A& h$ M6 w0 r; M9 [- k@DELI;; a4 u- C5 p! X6 k9 Z

7 c% I- {7 `" ?% Q9 C- p- t/ gbuild_and_run.bat- M; K+ ?7 L0 e4 |4 J# d6 O
@echo off6 L) f, w$ O! `( |5 n
call  build.bat  %1
( s$ R) m: K+ y: m0 l1 j# |0 t) gcall  run.bat  %1  %2
( W' u: O; v- |: i. ]& v0 l11 Z5 @5 {  o8 N' ~
23 z4 f# v( X9 m: S- o: V7 R/ M
3
& a7 g1 R3 ^  @* @( m9 ?4, _. [8 i) b0 j; s
5
. M5 @; J+ q) ?3 m" f6
; M. C1 C) H# Q8 ?7
4 B8 C: M5 t# I! M& |8
7 Z2 K+ e/ X6 }2 G; |$ g9( Q- p, l7 h9 E1 z9 Z1 y. z* S
10
7 \/ t# l/ V' c0 t, Z112 {$ m. _' X( r, O7 v+ c: f
123 q1 U+ a! ~2 O1 o6 z% @& ?  M" }
13
. l- S# P* Q" `9 x2 `$ @14
4 g6 Q2 d7 n/ W- v9 t- a' m# o15
0 B+ |* c4 y1 Y8 L' Z: L; k2 r16
1 \, k6 ?1 v7 U+ y- j172 l& h1 a+ c5 u6 K/ _! Y
源文件
; P$ l8 C+ Y1 \$ _: y1 I#include <bits/stdc++.h>+ G% ?& |  E' ]0 ~
using namespace ::std;
0 ^. M1 U+ ~, y. G6 ]
6 Z: x/ D( [* a" w3 G4 ?; ]0 Q' B//{ ___SUPIMO9 g! w) A8 {  I
namespace ___SUPIMO{
+ c) j0 h5 z: c9 R//{ Macro) A+ h! q# ^- J' }
#define  ASSERT_CUSTOM_( _op, ...)   if( !bool(_op)){ std::cout<<"Assertion_Failed(Custom):["<< #_op<< "],    Hint:["<< ___SUPIMO::Debug_::__ToString_items( __VA_ARGS__)<< "]("<< #__VA_ARGS__<< ")\n"; EXIT_;}3 l3 o. h6 g9 T- G6 C, S
#define  ASSERT_SYSTEM_( _op, ...)   if( !bool(_op)){ std::cout<<"Assertion_Failed(System):["<< #_op<< "],    Hint:["<< ___SUPIMO::Debug_::__ToString_items( __VA_ARGS__)<< "]("<< #__VA_ARGS__<< ")\n"; EXIT_;}
1 T- G) R$ a- r#define  ASSERT_MSG_( _msg)3 j. j2 N1 t( B& v* M
#define  TODO_RunTime_( _msg)  ASSERT_SYSTEM_( 0, "@TODO: " _msg)# H! `/ g4 i: G
#define  EXIT_  std::cout<< "EXIT: Line("<< __LINE__<< ")";  std::exit(1);
1 N3 s  g, y+ _5 n6 Z4 X; C#define  EXIT_COUNTER_( _max)  { static int cont = 0; ++ cont; if( cont == _max){ string str = "EXIT_COUNTER(" + to_string(_max) + ")"; DE_(_str); EXIT_;}}, k1 x, Y2 D9 m
#define  FOR_( _i, _l, _r)  for( int _i=int(_l); _i<=int(_r); ++_i)
8 n) M# r; c/ t* ~& M9 b' u#define  FOR_R_( _i, _l, _r)  for( int _i=int(_l); _i>=int(_r); --_i)
! N5 q3 ^! M# M0 n5 ?5 ?#define  DE_( ...)  if( ___SUPIMO::Debug_::___IsInDebug){ std::cout<< ___SUPIMO::Debug_::__ToString_items( __VA_ARGS__)<< "    {Line: "<< __LINE__<< ", Msg: ["<< #__VA_ARGS__<< "]}\n";}
7 X) f7 ~7 ]. ^  E% G#define  NOTE_( _str)0 X3 Y% _% h) n/ J4 d: W
//} Macro
; [! i1 ^( j9 m; ?2 p+ f% Q  y$ @+ c
namespace Debug_{
6 ?3 }! X5 ?; |% r    static constexpr bool ___IsInDebug = 1;0 N; R5 l; R2 E+ r( x( d# J7 Q
    template< class _T> string __ToString( const _T &);   string __ToString( unsigned __int128);   string __ToString( __int128);    string __ToString( bool);    string __ToString( char);   string __ToString( const char *);   string __ToString( const string &);  template< class _T1, class _T2> string __ToString( const pair< _T1, _T2> &);  template< class _T, int _N> string __ToString( const _T (&)[ _N]);  template< class _T> string __ToString( const vector< _T> &);  template< class _T> string __ToString( const set< _T> &);  template< class _T> string __ToString( const unordered_set< _T> &);  template< class _Key, class _Val> string __ToString( const map< _Key, _Val> &);  template< class _Key, class _Val> string __ToString( const unordered_map< _Key, _Val> &);    template< class _T> string __ToString( const multiset< _T> &);  template< class _T> string __ToString( const unordered_multiset< _T> &);    template< class _T1, class _T2> string __ToString( const tuple< _T1, _T2> &);  template< class _T1, class _T2, class _T3> string __ToString( const tuple< _T1, _T2, _T3> &);  template< class _T1, class _T2, class _T3, class _T4> string __ToString( const tuple< _T1, _T2, _T3, _T4> &);  template< class _T1, class _T2, class _T3, class _T4, class _T5> string __ToString( const tuple< _T1, _T2, _T3, _T4, _T5> &);
  m* L  \' g, h) D. _    string __ToString_items(){ return "";}  template< class _H, class... _T> string __ToString_items( const _H & _h, const _T & ... _t){ string ANS; ANS+=__ToString( _h); if( sizeof...( _t) > 0){ ANS+=", ";} ANS+=__ToString_items( _t...); return ANS;}# X3 b" G: u" C( l1 i; a# U
} // namespace Debug
& U! B9 u5 F' J- u2 q4 D* i( \
# ^/ d& V: \5 _# s/ A//{ Type. n1 N, V  r& _. v
template< class _T_> using Heap_small_ = std::priority_queue< _T_, std::vector<_T_>, std::greater<_T_> >;2 j0 L" q' t2 A& U( ^2 ~% X

5 h6 L$ Q! R7 S: P* o+ s0 Sstruct Double{  n2 ?/ G* Y; v
    using __Type = long double;  __Type Value;  static constexpr __Type __epsilon = 1e-12;
, x1 j  k+ A5 q    constexpr Double():Value(){}  template< class _T_> constexpr Double( const _T_ & _a):Value(_a){}  friend std::istream& operator>>( std::istream & _cin, Double & _a){ return _cin>> _a.Value;}  friend std::ostream& operator<<( std::ostream & _cout, const Double & _a){ return _cout<< _a.Value;}
  @3 q$ m  t$ Q0 t    bool operator==( const Double & _b)const{ return (Value<_b.Value? _b.Value-Value : Value-_b.Value)<=__epsilon;}  bool operator!=( const Double & _b)const{ return (0==(*this==_b));}  bool operator<( const Double & _a)const{ if(*this==_a){return 0;} return Value<_a.Value;}  bool operator<=( const Double & _a)const{ if(*this==_a){return 1;} return Value<_a.Value;}  bool operator>( const Double & _a)const{ return !(*this<=_a);}  bool operator>=( const Double & _a)const{ return !(*this<_a);}0 J( s5 ]8 u% g( o
    Double operator-()const{ return -Value;}  Double operator+( const Double & _b)const{ Double ANS = *this; ANS += _b; return ANS;}  Double operator-( const Double & _b)const{ Double ANS = *this; ANS -= _b; return ANS;}   Double operator*( const Double & _b)const{ Double ANS = *this; ANS *= _b; return ANS;}   Double operator/( const Double & _b)const{ Double ANS = *this; ANS /= _b; return ANS;}  void operator-=( const Double & _a){ Value-=_a.Value;}  void operator+=( const Double & _a){ Value+=_a.Value;}  void operator*=( const Double & _a){ Value*=_a.Value;}  void operator/=( const Double & _a){ Value/=_a.Value;}
2 w# b" I. J! M" B0 `}; // class Double
- q: k( A2 Z8 V! ]7 `5 z3 g
& \  |4 Z  Y/ f# b" ?- q* i0 {8 jtemplate< class _ModType_, __int128 _Mod> struct Modular{" s0 p9 j4 b/ J+ ^2 K8 s8 P
    ASSERT_MSG_( "_ModType_必须是{int/int64_t/__int128}");8 F' @. }6 ?$ H' P" Q
    using __UnsignedModType_ = std::conditional_t< std::is_same_v<_ModType_,__int128>, unsigned __int128, std::make_unsigned_t<_ModType_> >;
) ~# [; u" F& F) j9 c4 y: \    inline static conditional_t< _ModType_(_Mod)<=0, __UnsignedModType_, std::add_const_t< __UnsignedModType_> > __Modular = _Mod;  __UnsignedModType_ Value;
0 c8 w" Z7 G- ]- b1 q8 S    Modular():Value(0){}  template<class _T> Modular( _T _v){ _v %= (_T)__Modular; if( _v<0){ _v+=__Modular;} Value = _v;}
: d3 L& ^; D1 [4 x& E- c, ?: u    inline static void Set_mod( _ModType_ _mod){ static_assert( ! std::is_const_v<decltype(__Modular)>); ASSERT_SYSTEM_(_mod > 0);  __Modular = _mod;}
7 V( Y1 i9 R' T4 G# e1 U" l0 G    Modular operator-() const{ return Modular(0) - *this;}  void operator++(){ ++Value; if(Value==__Modular){Value=0;}}  void operator++(int){ ++Value; if(Value==__Modular){Value=0;}}  void operator--(){ if(Value==0){Value=__Modular-1;} else{--Value;}}  void operator--(int){ if(Value==0){Value=__Modular-1;} else{--Value;}}   Modular operator+( const Modular & _b) const{ Modular ANS = *this; ANS += _b; return ANS;}  Modular operator-( const Modular & _b) const{ Modular ANS = *this; ANS -= _b; return ANS;}   Modular operator*( const Modular & _b) const{ Modular ANS = *this; ANS *= _b; return ANS;}   Modular operator/( const Modular & _b) const{ Modular ANS = *this; ANS /= _b; return ANS;}  bool operator==( const Modular & _b) const{ return Value == _b.Value;}  bool operator!=( const Modular & _b) const{ return (0==(*this == _b));}  bool operator<( const Modular & _a) const{ return Value < _a.Value;}  bool operator<=( const Modular & _a) const{ return Value <= _a.Value;}  friend ostream& operator<<( ostream & _cout, const Modular & _a){ return _cout<< "Modular("<< Debug_::__ToString(_a.Value)<< ")"; return _cout;}  void operator-=( const Modular & _a){ if( Value < _a.Value){ Value = (__Modular - (_a.Value - Value));}else{ Value -= _a.Value;}}   void operator+=( const Modular & _a){ Value += _a.Value; if( Value >= __Modular) Value -= __Modular;}  void operator*=( const Modular & _a){ if( std::is_same_v<_ModType_,int> || std::is_same_v<_ModType_,int64_t>){ using __MultiplyType_ = std::conditional_t< is_same_v<int, _ModType_>, uint64_t, unsigned __int128>; Value = __MultiplyType_(Value) * _a.Value % __Modular;} else{ Modular ANS = 0; Modular a = *this; auto b = _a.Value; while( b != 0){ if( b & 1) ANS += a; a += a; b >>= 1;} *this = ANS;}}  void operator/=( const Modular & _a){ ASSERT_MSG_( "`Mod`為質數"); ASSERT_SYSTEM_( _a.Value != 0); *this *= _a.Power( __Modular - 2);}  template< class _T> Modular Power( _T _p) const{ Modular t = *this; Modular ANS(1); while(_p!=0){ if(_p&1) ANS*=t; _p>>=1; t*=t;} return ANS;}
5 h8 c+ A5 u! B# Z  i$ E}; // class Modular
; |1 ]7 f5 O+ h' X: @$ A$ e2 W//} Type
5 n/ V1 w2 ^+ A& Q1 Z' @% Q; }6 ^; C: [' p/ X, A1 D, B  l+ d4 F$ E
namespace Integer_{
/ V4 {7 n# D' K' I! ^    template< class _T_> _T_ Get_divideFloor( _T_ _a, _T_ _b){ ASSERT_SYSTEM_( _b != 0); _T_ ANS = _a / _b; if( _a%_b!=0 && ANS<=0){ if( ANS == 0){ if( (_a<0&&_b>0) || (_a>0&&_b<0)){ -- ANS;}} else{ -- ANS;}} return ANS;}% J, ~5 P  `/ u4 _( r/ O* a- P9 L9 G
    template< class _T_> _T_ Get_divideCeil( _T_ _a, _T_ _b){ ASSERT_SYSTEM_( _b != 0); _T_ ANS = _a / _b; if( _a%_b!=0 && ANS>=0){ if( ANS == 0){ if( (_a>0&&_b>0) || (_a<0&&_b<0)){ ++ ANS;}} else{ ++ ANS;}} return ANS;}+ E4 x: o' i6 J
    template< class _Type_> _Type_ GetPowerRoot( _Type_ _a, int _p){ NOTE_("a^(1/p)的下取整");  static_assert( std::is_integral_v<_Type_>);  ASSERT_SYSTEM_(_a>=1 && _p>=1);  _Type_ ANS = std::pow<Double::__Type>( _a, (Double(1)/_p).Value);  while( 1){ auto t = ANS;  for( int i=1; i<_p; ++i){ t *= ANS;}  if(t>_a){ -- ANS;} else{ break;}}  while( 1){ auto t = ANS+1;  for( int i=1; i<_p; ++i){ t *= (ANS+1);}  if(t>_a){ break; } else{ ++ANS;}}  return ANS;}
4 Z# h- K4 _) u8 z+ c+ ~0 C    template< class _TypeRadix_, class _TypeNum_> struct Radix{ // `TypeRadix: 每个进制的类型;  TypeNum: 所能表示的最大十进制数的类型`;5 y4 ~& F7 L' t: _
        std::vector<_TypeRadix_> __Radix; // 比如`Radix=[2,4,3]`, 那么所有的数为`([0-2), [0-4), [0-3))` 即表示的十进制数范围为`[0, 2*4*3)`; (Radix累乘值的大小 就决定了`TypeNum`);$ }  s4 B8 n7 h9 K$ ?- O
        std::vector<_TypeNum_> __SuffixProduct; // `SuffixProduct[i] = Radix[i]*Radix[i+1]*...`;1 z* k2 w) c% C: H& h
        void Initialize( std::vector<_TypeRadix_> const& _radix){ __Radix = _radix; __SuffixProduct.resize(_radix.size()); __SuffixProduct.emplace_back(1);  for( int i=int(_radix.size())-1; i>=0; --i){ __SuffixProduct[i]=__SuffixProduct[i+1]*_radix[i]; ASSERT_SYSTEM_(__SuffixProduct[i]/__Radix[i]==__SuffixProduct[i+1]);}}& f) h! ^6 o+ x0 \
        _TypeNum_ VectorToInteger( vector<_TypeRadix_> const& _v){ NOTE_("`v.front()`是*高位*"); ASSERT_SYSTEM_( _v.size()==__Radix.size()); _TypeNum_ ANS = 0;  for( int i=0; i<int(_v.size());++i){ ASSERT_SYSTEM_( _v[i]>=0 && _v[i]<__Radix[i]); ANS*=__Radix[i]; ANS+=_v[i];} return ANS;}8 K" j, ]+ w: g7 z
        std::vector<_TypeRadix_> IntegerToVector( _TypeNum_ _a){ NOTE_("`返回值.front()`是*高位*;"); ASSERT_SYSTEM_( _a>=0 && _a<__SuffixProduct.front());  std::vector<int> ANS;  for( auto it=__Radix.rbegin(); it!=__Radix.rend(); ++it){ ANS.emplace_back(_a % (*it)); _a/=(*it);}  std::reverse(ANS.begin(), ANS.end());  return ANS;}
+ Y( E* S8 n0 y        int GetBit( _TypeNum_ _num, int _ind){ NOTE_("`ind==0`是最高位");  ASSERT_SYSTEM_( _ind>=0 && _ind<int(__Radix.size())); return _num / __SuffixProduct[_ind+1] % __Radix[_ind];}
, l* }; C4 e1 n' _        void SetBit( _TypeNum_ & _num, int _ind, int _v){ NOTE_("`ind==0`是最高位"); ASSERT_SYSTEM_( _ind>=0 && _ind<int(__Radix.size()) && _v>=0 && _v<__Radix[_ind]);  _num += (_v - GetBit(_num,_ind)) * __SuffixProduct[_ind+1];}
; u; K$ j. Y! G3 R$ i    };6 B7 Q8 _- J# T; I
    namespace Binary_{& k, F5 F1 h$ X" g. T& K
        template< class _T_> std::vector<int> GetBits( _T_ const& _a, int _len){ NOTE_("a的低len位, @IF(len=-1){a的全部位}"); if( _len == -1){ _len = 8*sizeof(_T_);} std::vector<int> ANS(_len); for( int i = 0; i < _len; ++i){ ANS[_len-i-1] = (_a>>i)&1;} return ANS;}) ~4 ^' ]4 q0 ~5 M6 U. j
        template< class _T_> _T_ Get_sufixOnes( int _len){ NOTE_("返回值形如[0...01...1] 末尾有`len`"); ASSERT_SYSTEM_( _len>=0 && _len<=8*(int)sizeof(_T_)); if( _len == 0){ return _T_(0);} using Tu_ = std::make_unsigned_t<_T_>; return (((Tu_(1)<<(_len-1))-1)<<1)|1;}( ~7 V3 _# c9 e1 o, ]+ Q/ q7 ^
        template< class _T> void SetBit( _T & _num, int _ind, bool _v){ if( _v){ _num |= ((_T)1 << _ind);} else{ _num &= (~( (_T)1 << _ind));}}
9 k5 h; x& C8 r8 h7 g  G& P        template< class _T_> void RemoveBit( _T_ & _a, int _ind, bool _v){ NOTE_("删除[ind]位 高位下移 且最高位补`v`");  ASSERT_SYSTEM_( _ind>=0 && _ind<8*(int)sizeof(_T_));  using Tu_ = std::make_unsigned_t<_T_>;  _a = (_a&Get_sufixOnes<Tu_>(_ind)) | ((_a&(~Get_sufixOnes<Tu_>(_ind+1)))>>1);  SetBit( _a, 8*sizeof(_T_)-1, _v);}
& ]- p, T4 p) r+ ~        template< class _T_> int Get_lowBit( _T_);  template<> int Get_lowBit<int>( int _a){ if( _a==0){ return -1;} return __builtin_ctz(_a);}    template<> int Get_lowBit<int64_t>( int64_t _a){ if( _a==0){ return -1;} return __builtin_ctzll(_a);}
; [4 u, Q' l2 Q- e* m        template< class _T_> int Get_higBit( _T_);  template<> int Get_higBit<int>( int _a){ if( _a==0){ return -1;} return 31-__builtin_clz(_a);}    template<> int Get_higBit<int64_t>( int64_t _a){ if( _a==0){ return -1;} return 63-__builtin_clzll(_a);}
1 U. R; [: b/ u" [        template< class _T_> int Get_bitCount( _T_);  template<> int Get_bitCount<int>( int _a){ return __builtin_popcount(_a);}    template<> int Get_bitCount<int64_t>( int64_t _a){ return __builtin_popcountll(_a);}+ H: Y5 b6 t4 b8 x( ^* t* |+ p4 \. Z
        // #枚举二进制子集#: `for( auto subST = st; ; subST=(subST-1)&st){ @MARK(0); if(subST==0){ break;}}`遍歷`st`中所有`1`的選/不選的方案; (比如`st=1101`, 則在`@MARK(0)`处你会得到`subST=[1101,1100,1001,1000,0101,0100,0001]` 一定*严格递减*);4 J# s1 P9 P1 [) ]; V/ m% f( a5 z
    } // namespace Binary9 d+ o- g3 t: {2 [9 R7 i; z
} // namespace Integer0 {7 N" n" O. N& R" d

+ v8 M3 n6 K+ c* C& _& Anamespace String_{3 @" j8 Y/ L& J+ q1 v$ P$ t
    void Replace( string & _cur, int _l, int _r, string const& _new){ ASSERT_SYSTEM_( _l>=0 && _l<=_r && _r<(int)_cur.size()); _cur.replace( _l, _r-_l+1, _new);}
7 C$ U3 P/ \: q. d" L$ d! o# l    void Replace( string & _cur, const string & _raw, const string & _new){ int m = _raw.size();  for( int i = 0; i < (int)_cur.size();){  if( i+m<=(int)_cur.size() && _cur.substr(i,m)==_raw){  _cur.replace( i, m, _new);  i += _new.size();  continue;}  ++ i;}}2 A% p; \; m1 V' B; y
    vector<string> Split( const string & _s, const string & _split){ vector<string> ANS;  string cur;  int n = _s.size(), m = _split.size();  for( int i = 0; i < n;){  if( i+m<=n && _s.substr(i,m)==_split){  if( cur.empty()==false){ ANS.push_back(cur);}  cur.clear();  i += m;  continue;}  cur += _s[i];  ++ i;}  if( cur.empty()==false){ ANS.push_back(cur);}  return ANS;}/ u% {  R, D- t9 H3 l9 A
} // namespace String
9 X! ?9 n$ ~5 R. ]* ]4 [, B, w
6 c" [: t% X2 |; ]5 s& m3 K3 _namespace Random_{
# a8 s2 J/ T1 K+ w9 [2 E+ t& C2 }0 K5 s) X    std::mt19937 MT32( std::chrono::steady_clock::now().time_since_epoch().count());    std::mt19937_64 MT64( std::chrono::steady_clock::now().time_since_epoch().count());
' z; s' J9 [! W, ^( Z  v9 o    int GetInt32( int _l, int _r){ return (int64_t)(MT32() % ((uint32_t)_r - _l + 1)) + _l;}  int64_t GetInt64( int64_t _l, int64_t _r){ return (MT64() % ((uint64_t)_r - _l + 1)) + _l;}  Double GetDouble32( Double _l, Double _r){ return _l + (_r - _l) * ((Double)MT32() / (Double)UINT32_MAX);}  Double GetDouble64( Double _l, Double _r){ return _l + (_r - _l) * ((Double)MT64() / (Double)UINT64_MAX);}! y) d, s% P* N+ z
} // namespace Random1 y7 J/ U: E" d( X- p  ~9 j4 m
' k; [( V, M  J+ Q" l
namespace Object_{
$ C4 T' o3 j5 o5 e  A    const Double Pi = std::acos((long double)-1);2 v8 `9 C& f# K# B: N) n* h( ]
    template< class _T_> struct __Int_0x80;  template<> struct __Int_0x80<int8_t>{ static constexpr int8_t Data = 0x80;};  template<> struct __Int_0x80<int16_t>{ static constexpr int16_t Data = 0x8080;};  template<> struct __Int_0x80<int32_t>{ static constexpr int32_t Data = 0x80808080;};  template<> struct __Int_0x80<int64_t>{ static constexpr int64_t Data = 0x8080808080808080;};
8 r6 u, X% z7 D8 s$ ?( t7 l. ^& J    template< class _T_> constexpr std::decay_t<_T_> Int_0x80 = __Int_0x80<std::decay_t<_T_> >::Data;& t$ O2 E1 s2 |/ `4 h' x
    template< class _T_> struct __Int_0x7F;  template<> struct __Int_0x7F<int8_t>{ static constexpr int8_t Data = 0x7F;};  template<> struct __Int_0x7F<int16_t>{ static constexpr int16_t Data = 0x7F7F;};  template<> struct __Int_0x7F<int32_t>{ static constexpr int32_t Data = 0x7F7F7F7F;};  template<> struct __Int_0x7F<int64_t>{ static constexpr int64_t Data = 0x7F7F7F7F7F7F7F7F;};
8 u( d- [3 X' _8 O; O) l# C    template< class _T_> constexpr std::decay_t<_T_> Int_0x7F = __Int_0x7F<std::decay_t<_T_> >::Data;6 r, I9 q& j- Z( ^' Q9 G4 ]& L
} // namespace Object
3 r# I6 Y$ i7 t8 H" F# j: m3 N2 h" l8 c7 ~; [1 C" ]
namespace Function_{
7 z9 q3 m" y" [/ u% o    std::clock_t ClockSplit(){ static std::clock_t __ANSTime = -1; if(__ANSTime != -1){ auto pre = __ANSTime; __ANSTime=std::clock(); return std::clock()-pre;} __ANSTime = std::clock(); return 0;}
7 g2 y( M0 \: O6 _% I9 S    template< class _T> _T Get_GCD( _T _a, _T _b){ ASSERT_SYSTEM_( _a!=0 || _b!=0); while( _b != 0){ _a %= _b;  std::swap( _a, _b);} return std::abs(_a);}
. O& F1 }1 P% Y% f) h8 Y    template< class _T> bool IsInInterval( _T _c, _T _l, _T _r){ return (_c>=_l && _c<=_r);}
( w3 L6 B. l. q2 `1 A    template< class _T_> bool IsInSegment( const pair<_T_,_T_> & _c, const pair<_T_,_T_> & _p1, const pair<_T_,_T_> & _p2){ static_assert( std::is_integral_v<_T_>); bool ANS = 0; if( _p1.first==_p2.first){ if( _c.first==_p1.first && _c.second>=std::min(_p1.second,_p2.second) && _c.second<=std::max(_p1.second,_p2.second)){ ANS = 1;}} else if( _p1.second==_p2.second){ if( _c.second==_p1.second && _c.first>=std::min(_p1.first,_p2.first) && _c.first<=std::max(_p1.first,_p2.first)){ ANS = 1;}} else{ auto gcd = ___SUPIMO::Function_::Get_GCD( _p2.first-_p1.first, _p2.second-_p1.second); auto dx = (_p2.first-_p1.first)/gcd, dy = (_p2.second-_p1.second)/gcd; auto cx = (_p2.first-_p1.first)/dx, cy = (_p2.second-_p1.second)/dy; auto dx1 = _c.first - _p1.first, dy1 = _c.second - _p1.second; if( (dx1%dx==0) && (dx1/dx>=0) && (dx1/dx<=cx) && (dy1%dy==0) && (dx1/dx==dy1/dy) && (dy1/dy>=0) && (dy1/dy<=cy)){ ANS = 1;}} return ANS;}0 M' ~9 r; M8 U7 I
} // namespace Function
# a) c: _  y) d/ y- G
6 Y- j! A6 p" ~3 s} // namespace ___SUPIMO  p9 W7 A. D' A8 g! c
* b0 Z7 S3 E5 }: N' H
namespace std {* j5 b) Y* h0 D7 n$ d
    template<> struct numeric_limits<___SUPIMO::Double> : public numeric_limits<___SUPIMO::Double::__Type>{};
5 }6 P2 w, Z2 Y" M* q, Z) X    template<> struct __is_floating_point_helper<___SUPIMO::Double> : public true_type{};
& v' ?/ p( D% A, n! x& S( B0 _    template<> struct make_unsigned<__int128>{ using type = unsigned __int128;};' [8 i+ m: c4 ^2 R! Q
    ___SUPIMO::Double abs( ___SUPIMO::Double const& _d){ return (_d>=0 ? _d:-_d);}( I2 d4 o2 X' F6 e5 y7 x  ]$ F  t
}
& B  Y7 x" f3 F+ f//} ___SUPIMO& u0 H6 [' A9 x4 i3 \" S# o1 u" c

  K- {( |" Y; _7 g  i; Xusing namespace ::___SUPIMO;0 |8 H' }+ e7 i  j- _" B6 l
+ T1 j) H1 P. N% x  d' `# ~
void ___Solve_oneTest(){
# D5 E; \8 I/ p4 }: u
: h1 W. H1 f* c7 c}
9 v3 P6 |- Q8 Xint main(){, ?& H9 N' K+ l/ r8 W
    std::ios::sync_with_stdio(0);  std::cin.tie(0);  std::cout.setf( std::ios::fixed);  std::cout.precision( 9);
) r8 _' ?/ p( B  j4 c- e9 b
$ e2 z2 d/ @6 _  W    auto ___Work = [](){ // 必须严格与*题目*的录入格式对应;. h/ M' o8 o- v: n+ [
        constexpr int8_t mode = 0;
0 c3 v& h/ o. Z5 a        int testsCount;
! M) Q9 F6 ?+ t5 u* j        if( mode == 0){ testsCount = 1;}  else if( mode == 1){ cin>> testsCount;}  else if( mode == 2){ testsCount = 1e9;}' O5 j4 {% |8 X) K6 \. |
        for( int id = 0; id < testsCount; ++id){3 }# ^( b, c* _) I. J2 w
            if( id == 0){ // Global_Initialize
0 S4 F& B, M7 x! S! X! D! p: m6 P+ ?7 H$ j
            }8 W) d4 T- C  u# K2 f6 z
            ___Solve_oneTest();
0 w+ @% T+ c. D0 b8 b6 U        }
" d& U4 D5 m# P. ^* ?    };/ M* U) R$ X" W: E; Y
    if( ___SUPIMO::Debug_::___IsInDebug){
2 i  d9 @0 B0 B; u' Q  A% d        for( int id = 0; id < 100000008; ++id){
! _( L: ~  i' V' a( q* K            string flag;  cin>> flag;  if( flag == "___INPUT_-1"){ break;}  ASSERT_SYSTEM_( flag == (string("___INPUT_")+char('0'+id)), flag);& I+ H- n* x! |9 b5 f
            ___SUPIMO::Function_::ClockSplit();, a! v* W/ {& F
            std::cout<< flag<< ":\n";) L7 l) E7 N5 d. r
            ___Work();
: R- ]* K% V- Y- y            std::cout<< "\nTimeElapsed: "<< ___SUPIMO::Function_::ClockSplit()<< "\n\n";' g: v1 i3 \0 F/ p4 a/ Y! r
        }
8 f/ _) t7 x5 M: {* K    }
# L7 M$ c' m! N: v1 D0 `, T    else{ ___Work();}
& N9 N- r4 x3 s2 O8 p' w: `8 p6 k7 ~9 d; a9 i* N! O3 Q
    return 0;* _" z( Q. _* W
} // main
# d3 q' Y$ J) P+ q8 a7 K, F& E2 J/ D. u
$ Z( q4 `" T" m( dnamespace ___SUPIMO {
6 Q2 v% }! D( y5 g& B    namespace Debug_ {
8 c  @) p! D0 K        template< class _T> string __ToString( _T const& _v){ ostringstream ANS; ANS.precision(cout.precision()); ANS.setf(cout.flags()); ANS<<_v; return ANS.str();}
0 `0 g# o3 R; m6 P/ A        string __ToString( unsigned __int128 _v){ string ANS; if(_v==0){ ANS="0";} else{ for(;_v!=0;_v/=10){ ANS+=('0'+_v%10);}  reverse(ANS.begin(), ANS.end());}  return "UInt128("+ANS+")";}# ]' N9 \! Q4 p. t
        string __ToString( __int128 _v){ string ANS; if(_v==0){ ANS="0";} else{ if(_v<0){ ANS+="-"; _v=-_v;}  for(;_v!=0;_v/=10){ ANS+=('0'+(_v%10));}  reverse(ANS.begin()+(ANS[0]=='-'?1:0), ANS.end());}  return "Int128("+ANS+")";}
. J8 c1 i$ |7 |" y        string __ToString( bool _b){ return (_b?"true":"false");}
* m$ O9 E$ {4 ]5 _; H        string __ToString( char _t){ string ANS="'?'"; ANS[1]=_t; return ANS;}
5 K- @% R) ~# R. B        string __ToString( char const* _s){ return string(_s);}
# Q0 i1 |# M* s& U+ F! E+ W        string __ToString( string const& _t){ string ANS="\""; ANS+=_t; ANS+='\"'; return ANS;}
# b0 ?) s0 u* k9 B/ L        template< class _T, int _N> string __ToString( const _T (& _v)[ _N]){ string ANS; ANS+="Array["; bool first=1; for(int ind=0; ind<_N; ++ind){ if( 0==first){ ANS+=",";} else{ first=0;} ANS+=__ToString(_v[ind]);} ANS+="]"; return ANS;}
0 P8 z! C- W; R8 S7 \% e        template< class _T1, class _T2> string __ToString( const pair< _T1, _T2> & _v){ string ANS; ANS+="Pair("; ANS+=__ToString( _v.first); ANS+=","; ANS+=__ToString( _v.second); ANS+=")"; return ANS;}
) @5 U) E7 E$ ]2 O) w1 i        template< class _T> string __ToString( const vector< _T> & _v){ string ANS; ANS+="Vector["; bool first=1; for( const auto & i : _v){ if( 0==first) ANS+=","; if( first) first=0; ANS+=__ToString(i);} ANS+="]"; return ANS;}
/ m1 J* J5 F# \5 p9 @        template< class _T> string __ToString( const set< _T> & _v){ string ANS; ANS+="Set["; bool first=1; for( const auto & i : _v){ if( 0==first) ANS+=","; if( first) first=0; ANS+=__ToString(i);} ANS+="]"; return ANS;}7 D! L' }  z" Y/ Q$ Q3 H
        template< class _T> string __ToString( const unordered_set< _T> & _v){ string ANS; ANS+="UnorderedSet{"; bool first=1; for( const auto & i : _v){ if( 0==first) ANS+=","; if( first) first=0; ANS+=__ToString(i);} ANS+="}"; return ANS;}
* I$ J  C  K6 Y% q8 `7 v- O        template< class _Key, class _Val> string __ToString( const map< _Key, _Val> & _v){ string ANS; ANS+="Map["; bool first=1; for( const auto & i : _v){ if( 0==first) ANS+=","; if( first) first=0; ANS+="("; ANS+=__ToString( i.first); ANS+=":"; ANS+=__ToString(i.second); ANS+=")";} ANS+="]"; return ANS;}/ U' l0 y' s$ R$ G& z% w( F% [5 H& Y
        template< class _Key, class _Val> string __ToString( const unordered_map< _Key, _Val> & _v){ string ANS; ANS+="UnorderedMap{"; bool first=1; for( const auto & i : _v){ if( 0==first) ANS+=","; if( first) first=0; ANS+="("; ANS+=__ToString( i.first); ANS+=":"; ANS+=__ToString(i.second); ANS+=")";} ANS+="}"; return ANS;}
9 P5 X& S2 W3 H        template< class _T> string __ToString( const multiset< _T> & _v){ string ANS; ANS+="MultiSet["; bool first=1; for( const auto & i : _v){ if( 0==first) ANS+=","; if( first) first=0; ANS+=__ToString(i);} ANS+="]"; return ANS;}3 x& ~8 p. @4 t9 @0 y" J
        template< class _T> string __ToString( const unordered_multiset< _T> & _v){ string ANS; ANS+="UnorderedMultiSet{"; bool first=1; for( const auto & i : _v){ if( 0==first) ANS+=","; if( first) first=0; ANS+=__ToString(i);} ANS+="}"; return ANS;}! `( k& D& K  ?# C
        template< class _T1, class _T2> string __ToString( const tuple< _T1, _T2> & _v){ string ANS; ANS+="Tuple2("; ANS+=__ToString(std::get<0>(_v)); ANS+=","; ANS+=__ToString(std::get<1>(_v)); ANS+=")"; return ANS;}2 N5 a8 P' @7 d# Y. b! K
        template< class _T1, class _T2, class _T3> string __ToString( const tuple< _T1, _T2, _T3> & _v){ string ANS; ANS+="Tuple3("; ANS+=__ToString(std::get<0>(_v)); ANS+=","; ANS+=__ToString( std::get<1>(_v)); ANS+=","; ANS+=__ToString(std::get<2>(_v)); ANS+=")"; return ANS;}4 }% l3 _( c* g1 ~, p  Y
        template< class _T1, class _T2, class _T3, class _T4> string __ToString( const tuple< _T1, _T2, _T3, _T4> & _v){ string ANS; ANS+="Tuple4("; ANS+=__ToString(std::get<0>(_v)); ANS+=","; ANS+=__ToString(std::get<1>(_v)); ANS+=","; ANS+=__ToString(std::get<2>(_v)); ANS+=","; ANS+=__ToString(std::get<3>(_v)); ANS+=")"; return ANS;}
  I% N8 m) f! f        template< class _T1, class _T2, class _T3, class _T4, class _T5> string __ToString( const tuple< _T1, _T2, _T3, _T4, _T5> & _v){ string ANS; ANS+="Tuple5("; ANS+=__ToString(std::get<0>(_v)); ANS+=","; ANS+=__ToString(std::get<1>(_v)); ANS+=","; ANS+=__ToString(std::get<2>(_v)); ANS+=","; ANS+=__ToString(std::get<3>(_v)); ANS+=","; ANS+=__ToString(std::get<4>(_v)); ANS+=")"; return ANS;}. ^, e% Y& x2 H+ @8 S1 H4 w  [+ n
    }' F! s2 l) s9 A3 P) x6 e# A6 N
}3 X' d/ y( p6 r" R# v$ ^( L
13 z' H5 z  V* N! b; ^
21 U+ s( p7 U+ b
3
2 U8 {7 Q  r9 n7 c0 y* E4  `$ w0 M! M* ~9 _; H# T
55 }# D0 A* v- u% n: w) G* w
69 e- P2 G7 V  ^
79 Y  }6 [2 K2 y" y1 _* f5 L+ S. y
8
$ e. E; x0 }: T9
+ E9 C% ~  Y8 g8 I10
7 F4 r! ]2 u7 {9 {/ P11
6 n8 K3 K9 x% S# ^12
  D, G3 |7 _) N; k, m" O! [13
3 x  A: `& n% |. n1 y# b; I6 ]140 Z4 n! u  e& c$ ?$ M
15
/ _5 F  [0 l# ]% _  \2 w7 C8 R16* A- N, @3 H1 k% L1 s
17
" l' F' C0 D: J8 F0 @18
6 l4 b/ V6 N0 q6 t0 T. g19( j3 [! _% [4 {. P- r# q
20
6 c" y: h% q: @2 x21
! d+ W  K0 i! l7 d4 R- a5 w4 |225 F4 [% |2 [1 P7 H2 B
233 R# s% i; l5 i
24
* W: A8 {! q7 m2 ~25
' ~. Q% r, Z3 l7 `5 l% k" z: }2 b26
+ j. }( n* ~& v1 @271 m4 m/ U& b& p& E, d. C
284 X' c3 F! @! i9 E: m+ t6 x
29! Q5 ^6 }7 Y7 k3 X0 B5 m2 x3 c/ F
30
9 \) _+ e2 X/ W: W2 a31/ ~/ e3 ?8 W( ?4 K: c# h9 s
32# ~+ Q+ f* Y- Y' P
33
8 A! ]) V7 X( v1 [! Y. M34: }& D# c) x/ b9 j$ K' R4 f
35  j7 w( z( i2 D
36
4 C$ O: T. }5 |7 j# e" u" g( Q37: i' L. b  S9 p7 v% u: g2 T/ L4 p
38
9 Y; w2 K" G1 {$ _  m) T  B& a396 L# o) D9 V' E9 N% z4 a9 g2 W
40
7 E* F( T# T; Q3 @" ~: ?41
2 ~* p0 f0 O. }3 g8 r42
4 G) S' A: D% m2 i43
5 ~: H! D  J$ Q2 l1 w44  |3 `. W9 ]( ]7 H# Z6 A9 |7 z$ Z2 S
45
9 J$ O3 E1 Z* K46
4 C8 r! U6 Y4 M8 J47
9 c7 n: b4 A8 B# @: J2 ?4 g48
" l- V5 j/ R; O6 `" |49& S/ H# c: p3 c$ ~* k; _2 }
50+ n3 {5 U. R, S5 l: r5 l7 X
510 M0 g; z0 I0 Y8 W9 l7 y4 f
52
! |6 G2 w6 n1 x53
5 E* U$ v/ Z9 P9 t2 Q54
" b. k, s6 v# T# s4 ^0 [: ?55
' I3 e' }4 J1 h2 k$ k7 x9 U56
# E! \+ R; s0 z! y1 Q57* G- Y( F7 F( B; z) y6 k9 g; R
58
' d* q# W9 f( Y. c" a" \5 W8 l59
9 ~0 v0 E" W  O% S60* n4 j5 U. X' g) Q' [- P
61
1 \* }  D: o' x& R( q4 r6 ?5 h62
0 S6 w0 M& g+ x0 X& l$ G63
# o2 Z: X- V( N6 N1 n1 u6 e& E64, V9 v$ @, x, A) I
65
/ U5 k8 v% _/ [; g66
3 M! U2 t+ g4 p# x- g* d4 t67% ~$ i, v% A3 F) k3 p  k& k
68
/ q$ W( k7 ^& U& t8 e$ A6 J693 l1 u  U4 h: J* ?; Y2 X, v
70
! o* U1 ^2 {! h% G71
5 ]8 {; G- v* Q  O725 _( W/ |  r1 p3 K' E$ h% i
73
2 n8 y: B$ w' i( c74
- J* d; W3 O* e# h, f75
; `9 s8 `4 |- W+ [76
1 V" v  ?. H3 z5 n+ ?77
) V  k/ c# X- z4 g$ m/ g783 F; P* y7 I" i  x# M
79
; @/ H1 h/ ~" S* F801 w9 ^; e% g0 L: K% [
81
. g2 v  J5 Z; S) ?  y82
' l4 W0 q) z7 S/ h+ D, w833 m9 r$ @) D9 U* b; R7 R
84
2 R; ^* J. _; z- A1 f3 \85  u4 q3 j& M4 j. j
864 F. m! _0 O5 `1 k7 @/ w
87. k. p: X  \1 e+ W5 {
881 s, n1 K0 I2 z( Z
89  g. F( J' g" q3 \
90
5 t: ~% t. g1 o% Y! ^. \: i7 O91# M3 M! `( e9 U2 _
92$ ?/ v0 U4 R7 `* B
93& k$ K8 m8 n+ Y+ A1 @
94: j8 S$ `" V9 g. C+ y  U
95: ]& U' H1 X4 D& E3 \4 K4 m
96
/ s" W5 l3 D, R( H97) X6 h3 k' g# d+ ]+ p0 N
98* t: P% ]$ R- B. |) @& T
99
% l" A8 A0 x' w( ]) o' Q. y100
* w0 ?' J4 U9 H8 |101
* D( K! k0 D$ |. _102
2 g2 f, J  j; Y$ F+ N/ m! n) X# S103- d: Y" O: q2 [# _2 a4 }8 s
104
! h/ n- Y" O9 _105
5 ]! k3 D$ b5 U6 \7 ?6 i# `106
3 X2 V' U  R* X$ O5 [107
( g; I$ u, t* n6 l, y- a1084 _$ E% P0 A5 T; J0 n
109
0 N  ]$ @2 D  ]- m# l9 a110: i( S( F' D$ I) M2 b- u) c. ?/ i
111. v! L6 ^) q; z, S, t, c
112$ P, {% @( E: M9 Z
113
6 v( l$ Y3 O1 A9 _- D: `1144 h0 t4 p- B7 P* C& c
115- J0 V' m  D( U
1162 X2 q, X, S9 |9 T7 o
117
( J7 ~9 C6 R1 O3 x; c" o% N118
+ y' c3 U  `6 i& w119- R/ t/ L/ _/ V/ Y8 b& s3 l
1207 q3 u) v" N: W
121
) q8 z1 s- w* y* r2 B* C$ h3 E122/ Z/ C- Z, J+ E: n
123
* Q5 h- q* _8 V+ e, @- i( m+ d* W: M# m124
0 n. E! C  l% j5 w5 q125+ v4 _/ Q' {% N8 d2 U, ?
1261 X, `' n, a) P
127; U- F0 D# f$ b! v' S( h" J/ C
128) B0 U5 e$ Y5 G* F* E( K! n
129& E* z2 ~$ N2 o5 G5 Z  y
130( [( ?3 s9 X+ R. R
131
% s  o3 T0 v' w1321 B$ W" Q; v. A  E# m
133
5 T# X4 ]  S* _; z; O! @! T) [' K134' }) z$ d) l  B; ?, P7 [0 l
135
' S" \1 n* e" j" i" K) L+ c1368 @0 J2 N1 i; P0 X4 Q/ O! t. }
137
! f# G3 \" n$ x3 x- h  \138( ~( a- c' ~1 G; D
139
% a/ R0 z2 w' y5 t/ `$ }140
2 b8 m" ~& f& J( L* B7 D141+ {! T4 q' f: e+ V
142
  Y/ }$ {; [$ i5 e( W* C0 Y9 u1433 s  T, e: _& @0 C+ F! D% |8 o
144
9 r( G) Q+ Y' H145
8 f: z. r, G7 i! e: N5 J146
6 c5 v  Q1 Z2 `5 X% r1 W. M147
7 U# n" J) |# e8 q148) b) z, A& h# l5 o( W
149) ^5 ^' ]# }* I/ Y
150
4 k$ O  E" f4 c0 s: {: u" C7 a151! d0 g9 M; K. M
152" Q; }* `1 V) [
153
, V4 P$ Q: j+ o0 Q. _/ S0 O$ Z154- E6 d: d. a! x- k* A! z
155( A  u3 M' _/ R$ W. v9 _1 A% e: ?6 K
156) c1 y& |/ H  M( w' J9 q
157
! d& W7 k6 Z7 C. K9 w6 e158
$ a; Y- k, V/ B1 a159
: y. N2 |, b) M9 n. W0 }2 V0 n160
: M6 B  U7 D% \6 o161
/ {) \- W+ l# G$ @9 G* {6 ]162! l7 L3 p3 G. `
之所以把___Solve_oneTest()單獨寫成一個函數 而是放到main函數的for循環裡面, 因為: 當我們要進行特判 比如if( N==0){ cout<<"YES"; return;} 這裡的return 就是結束當前測試, 可是 如果你放到for循環裡面 你可能認為 那用continue不就可以了? 錯誤, 因為如果你內部還有for循環 這就出錯了 即此時continue不是對*外部的for循環*生效; 所以 必須要寫成函數形式;
, p$ a4 N# Q# h# ]" j: ]! `/ f+ l; r/ W4 T
Global_Initialize2 W5 ^4 d; m5 q- w- v' G" D
专为力扣设计的, 即全局(多组测试数据所共用的)数据的初始化;# O4 v; n) S9 w% [, Y
/ D$ k0 _2 w7 }0 A' w) w" }  A
String
% W% c& c: }+ f4 D3 F$ qSplit的答案 一定不会有空字符串;
  X1 v3 m. j+ c3 w他是从前往后贪心进行的, 比如"xxx" 以xx分隔, 那就是[xx] x 即答案是最后的那个x; 比如"xxxx" 以xx分隔 那就是[xx] [xx] 即答案是空的;
0 u3 e5 K; j$ B' ^3 I
6 z9 L. }/ X2 J% o@DELI;$ L- I8 e( r: \5 l. e

2 k. J( o, M% ^" y: k6 @- A+ PReplace的本质 就是Split函数, 即比如你Split得到的是? X ? X ? (将X替换为Y) 则答案就是? Y ? Y ?;
# H4 t9 q. V5 w" c$ N2 [. 比如S="xxxx", raw="xx", new="x", 那么答案是xx, 即先是[x] xx 然后[x] [x]; (并不是[x] xx 然后[x] x 然后x);' a* a- c- D* M! U9 C

5 J5 `* |4 Y$ |: A' vDebug- l& f% ~" z2 h3 Y7 ?& W' S
if( ?){ Debug::__IsOpenedDebug = 1;} 和 Debug::__IsOpenedDebug = (?); 这两个 是不同的!$ i" r/ w5 w( A( v, ^6 C0 K+ R
前者: 他是在特定情况下 打开调试, 但是他不会关闭调试; 而后者: 他要么会打开调试 要么就关闭;
. T) [+ H& J( x/ U; K. v前者 通常用于 针对某个子流程而调试, 比如... [T] ... 最开始我们关闭调试, 然后到[T].入口时 打开调试, 然后到[T].出口时 关闭调试; 即整个过程 我们就调用了三次IsOpen = ?命令; 这通常在DFS时 使用的较多, 即符合某种条件时 进入某个DFS分支时 打开, 然后回溯回来时 关闭;
! b+ p$ x% \* m) v- b6 j1 s而后者这种方式(即不停的根据条件 打开/关闭调试), 一般在非DFS的场景(比如FOR循环)里 会使用, 比如只对所有奇数进行调试;
1 P, l- \5 T, p8 k4 L* j$ f即前者 他是针对一个连续的子段, 而后者是针对一个序列里 满足某条件的若干元素;* l0 |3 y+ ]8 g: j
% p) u$ g( r; t" M
@DELI;
; j  S$ U( l3 M+ D, [5 {; h5 Y) V: E
7 _! ?$ M6 Z* C有個疑問: 為什麼要把他轉換成string 而不是直接cout輸出呢?
: ~: E$ B- v$ f3 k% f. 可能是多了一层封装? (但毕竟你这个模块 就只复杂Debug输出啊 有必要再多封装一层吗?
% B' h/ ?- B8 G. l- M( R. A$ ^
! z4 x/ A8 Y2 {- U" ^@DELI;. J) [% \( l2 u3 H+ \: k

% P! j* B/ B0 }INFO_里, 不可以对#__VA_ARGS__直接用,逗号分隔, 因为他可能是INFO_( F(a,b), 3), 所以你还得判断括号;8 C# Q5 y5 A  S2 @3 q6 ^

# m# @" S! J3 b. {5 w4 n- B@DELI;1 e- l" w7 r5 J0 ]: h
: j0 B% g- U0 c4 y
T A[10];數組類型, 你可以直接輸出DE_(A);
! f- K" y3 A  ^) w+ ZDE_( (T(&)[5])A); 這是輸出A[0,1,2,3,4];- \8 \, t( J- y9 H! \
& d8 Q( J3 q9 L3 [/ ]' k" V' N& P
auto A = new T[2][3] (此時auto == T(*)[3]);, t6 C9 ^: v% D1 w+ c$ ?* e
. 要輸出他的所有元素, 此時直接DE_(A)是錯誤的(他是個指針地址), 正確語法是DE_( (T(&)[2][3])*A), 注意 *A的類型是T(&)[3], 但你把他強轉給T(&)[2][3]是可以的;" s% R+ ~/ B# n' P1 ~4 [8 p

5 R' K8 t2 o( H$ R0 L7 n4 y, g- O@DELI;
' S( Q* B& j% {: {- S" U4 F: Z
3 S! [* q& I& k% W1 y__Debug_list的參數 必須是const _H & _h, const _T & ... _t引用 不能是值傳遞;
6 G' o7 v0 q0 m" G  I  w比如對於對象很大的情況(圖 本身都已經1e6級別的大小), 那麼 這已經不僅僅是效率問題了, 因為參數用的是棧空間 這是會爆棧的;. P  F- _  M0 S- E# ?

$ ]' A+ X5 y  b: Z; b: E@DELI;; \! f8 l$ Y) w1 |0 Z# y
1 e3 k5 }% f7 d$ b! s' K
我们使用__Cout自己的重载函数 而不是去重载operator<<, 一个原因是 对于char/string基本类型的重载 此时和系统的就冲突了 (你需要再单独写个函数使用is_same去特判) 所以 不如就不使用系统重载符了 直接自己定义函数; 第二个原因是 其实把 两者本质都一样 我们自己写个__Cout函数 等于多了一层封装;
  t9 h3 ]" k9 j9 D' s* [4 g# E
" h; o# O' G# Q4 Z) C你必须要声明/定义分开 這是為了實現對嵌套的輸出, 比如对于vector< map<int,int> >的输出 他使用了Cout( map<int,int>) 因此 你必须要有其声明在vector實現函數的前面;
! f. \  W7 J# R/ A/ q1 v
6 ^. ~( W/ v7 Z) p$ p如果是自定义类型 他会进入到Cout( T) 然后调用cout<< T, 即你的自定义类型 需要有重载运算符;
' N1 W2 Z1 Q  \& r) h7 a
( K9 ~4 Y8 Y6 }9 p7 Y2 q@DELI;
+ d+ m' a" M! N; R; i! a& V1 |& s7 `2 s. y
__Cout你不需要寫成 像ostream& operator<<( ostream&, T)那樣, 直接寫成void __Cout( T)即可, 這是因為: operator<<之所以要那樣寫 他是要實現cout<<a<<b<<...這個操作; 而__Cout 不會調用__Cout(a) << b這種操作;
. [( Z& y/ k  ?. }0 b, e  R. [0 G  |1 M' @) n$ J
ASSERT報警宏
: {$ B1 w- Q% |: T. x& I; h#如何关闭某个子模块的ASSERT$
) ~/ |( D7 l/ v  C; H8 y, v对于算法模板A, 他里面有很多ASSERT_SYSTEM, 为了优化效率 如何把他们给关闭掉呢?
; _$ G7 ]4 Z: t7 |! D
+ O+ }/ t5 {% L5 e8 p; [$ Y  v#undef  ASSERT_SYSTEM_
9 V' o& }4 Y& \2 u# V* c4 n7 ?#define  ASSERT_SYSTEM_( _op, ...)
1 x+ W. l5 m( n1 J        namespace A{' z6 N3 ?4 ]& w
        }
7 p6 L3 f  N$ J" M8 j6 c) e#undef  ASSERT_SYSTEM_    5 R6 I+ l% b: j. s8 z/ t) g/ L9 H
#define  ASSERT_SYSTEM_( _op, ...)   if( !bool(_op)){ std::cout<<"Assertion_Failed(System):["<< #_op<< "],    Hint:["<< ___SUPIMO::Debug_::__ToString_items( __VA_ARGS__)<< "]("<< #__VA_ARGS__<< ")\n"; EXIT_;}
2 M* z9 b4 V9 ?% ^+ a7 {% c- C1
- {( i/ M9 }; _. T; ]# b2 G7 G2
9 V' t$ i0 L9 \2 f, L3 r3
9 @, H; F6 [3 D8 I* F5 G" @4
) i  S" c9 Y0 i2 y! Y( d0 E! P52 c  {: U! n6 y
6
8 J9 Z1 v4 {# x7 \9 y5 R3 p8 T. 也不可以不写#undef, 但他会有警告warning: 'ASSERT_SYSTEM_' macro redefined;! D' x3 V+ _/ Z

0 S. u2 Q, }: {8 u9 q@DELI;- I. h- ?1 T& K" l& I. j8 z9 ~
. ?/ {8 a  k! a" ^9 a
ASSERT_CUSTOM_: 用戶自己的程序裏面 使用這個宏;/ e2 |2 P7 C% {5 r2 k
ASSERT_SYSTEM_: 算法模板裏面的報警 都使用這個;
8 \6 _5 r+ f; R; n0 Z4 h7 C- u" d2 B4 W
& D; E0 j6 q7 J, l, s, j7 U
為什麼FOR_的宏定義是 (int)_r呢?
" m4 t8 P0 V6 \9 [/ Z對於uint32 a = 0, (a-1)的值 是111...111, 於是for( int i=0; i < (uint32)-1; ++i) 這會死循環的;
1 x3 c8 Z9 g4 K; X6 P+ V% f但是 把111....111 強轉為int, 她就是-1, 即int i = 0; i < (int)-1; ++i) 這是正確的;
* L& d! i5 [  D
% l& ~7 d3 A5 K@DELI;/ E% v' N) M4 v/ ~- E* @, k

# v0 \" `6 ^' M$ C這3個報警宏 都有2個模式:$ A$ J; v8 ]* W' C
1(默認模式):[如代碼所示];
1 b1 Y9 ?, Z0 @2 W* [- r, [2(優化模式):[你自己把他注釋掉, 這主要是為了(提高程序效率/便於找到程序BUG)];- t2 {" d. Z6 s5 w# a9 n1 R
. 比如默認版本是#define A x, 那麼你就把他改成#define A (void)0 // x, (注意後面的注釋// x是不生效的 預編譯時會被清除掉 即到時候是(void)0; 而不是(void)0 // x;)1 n% U4 w6 q' ~8 ^, b& b
& @* r! z' H4 u( D
ASSERT_MSG的優化版本 即static_assert(false), 此时在开发阶段就會報錯 也就是你會發現所有的調用ASSERT_MSG的位置, 就可以发现有可能存在的错误;% @+ C2 H9 m7 r1 k# o& g- u

" t9 f! Z5 V- l! K: d$ n@DELI;
% j( |8 h7 F$ V; _" j# D7 Z' M) O$ \& V9 ]% j4 p" @7 |& a
#ASSERT_MSG_( _msg)#) Y; s9 C" }7 U- g, ?* z: b7 X" S
这是完全给用户提示的 程序无法测试其正確性 但你自己必须保证他是true; 比如取模除法 mod必须为质数, 就可以是ASSERT_MSG_( "mod必須是質數");
4 g+ Y7 e1 q; r8 S5 s" ?+ u( @1 W0 c0 p5 T
@DELI;
  h+ s6 ~! Z# ~' f; Q& y, ?  g, r4 V0 o% `- P
#ASSERT_WEAK_(op) (void)0#
! W0 x* \* B. l4 k  @) n/ a; l5 a  c即使op为假 也不会报警, 但你自己要保证他一定是true 这是为了效率;
# B5 A1 I* @4 m+ {: R
! c/ e$ A- s- QModular& i& D" G6 ?% V  i& ~( Q
Modular的設計思想是這樣的, 她有2個模式: 對於using MOD = Modular< T, X>, T必須是有符號int/int64/128;
9 y% [% \& E& }$ m0 o1: 你的Mod模數 是不變的const常量, 此時 這個X是常數, 即在編譯期 模數就固定了;# }! Y6 q3 Q2 }) f0 V6 a+ [" r
2: 你的模數 是可以改變的, 此時這個X <= 0(你任意設置一個值即可), 此時到了運行期 你可以動態的通過MOD::Set_mod( m)去設置他的值 且這個m參數的值 即模數 她必須是在T的正數範圍;/ m- q# |7 ]  f7 t; w/ ~) z7 d0 t1 U- O* D
不管哪個模式 假設你的T=int 你最終的模數 一定是在[0, 2147483647]的範圍內的 (而不是uint32的範圍), 而且你的值Value 一定是unsigned T類型, 為什麼要這樣設計? 因為 當你進行加法運算 此時 你不需要轉換為int64 她的加法結果 一定是在uint32範圍的;5 [+ O) d9 r) g# }; ]

1 y$ |5 g" w! \- ~@DELI;( }; E( F0 o6 O0 M( M

+ T3 ~6 T6 i7 d對於乘法操作, 如果是int32/int64 則直接轉換為int64/int128來進行乘法, 否則對於int128 則執行二進制乘法(她會調用取模加法 是不會溢出的 這就是為什麼你的模數 必須是有符號範圍);
1 f0 u2 Z6 W2 h5 Z7 U" @" e/ O% J
$ v0 x. h/ a% ^% C. w5 h$ [@DELI;
9 ?6 K# ]" {% v% [! U0 K- E3 f9 a  E* O. U1 a% I
template<class _T> Modular( _T _v)這個構造函數裡 你不能對他進行is_integeral的判斷, 因為對於__int128 他不滿足條件(可能未來編譯器會支持 但現在他的返回值是false);( \8 J7 p3 k  W: e; ]7 T) a& ?

0 a8 x& p) x- B4 [! |@DELI;
0 {/ [2 X/ S$ A% R! u
8 S* B  Z3 z+ Q基本使用! u( n+ i5 \) J
( q3 ^( a6 [  U5 W3 V: L' z
using M1 = Modular<int, (int)1e9 + 7>;; K# V: w) I( g9 }
所有`M1`的對象 他的`Mod`都是*int常量*;" w; @2 x/ j$ X8 l6 C

# D4 g. A" z2 w/ _2 ^  D$ i, @, qusing M2 = Modular<long long, (long long)1e15 + 7>;
5 n4 W4 F- G+ {9 F% C3 C0 A/ a所有`M2`的對象 他的`Mod`都是*long long常量*;
" J* g) S4 H. v5 P$ h; r* `6 H% f5 W4 V2 L' ~& d9 ^
using M3 = Modular<int, -1>;
% ]; _( K4 b* J% t, mM3::Mod = ?; // 由用戶錄入 (這行代碼必須在*運行時* 即放到函數域裡): k3 ^* y, w' D- V) U$ n9 v
所有`M3`的對象 他的`Mod`都是int類型 且等於`?`;: {- d& y. o* ]9 A
( e* |" F5 Y, t& R$ p. P
using M4 = Modular<long long, -2>;
% ~2 N( o) M  U# d+ L9 ~M4::Mod = ?; // 由用戶錄入 (這行代碼必須在*運行時* 即放到函數域裡)
" S0 x7 n0 M" {: S. Y6 ]: N+ |4 k所有`M4`的對象 他的`Mod`都是long long類型 且等於`?`;3 I5 C) _# Q" w# L, R3 d
. i6 c1 u5 l7 V* S/ S' }3 G4 C
using M5 = Modular<int, -2>; // 注意此時要和`M3的<int,-1>`區分開來 即不能寫成`-1`, 否則`M3,M5`就共用同一個`Mod`了;
6 o+ s% `( e" l8 _) N7 T& Z6 W/ Z1 B: h  {9 @

9 R) D) b9 f& f1 p% h" a/ S. s( d@DELI;
+ U( m3 B  _2 F7 k
8 U* V& w) s: S( s7 A' rT_ Value; // 一定是[0, Mod)范围; 不要调用`obj.Value = xx`(他不是规格化的) 而是使用`obj = xx`;
5 z- ^( k2 [% U# {- g1" |- M" x0 J2 `7 o7 o
#除法#0 u7 D4 R8 d8 X7 {$ H( o) B
调用a / b的前提是: (1: Mod是质数), (2: b != 0);
: B" d3 {- O6 H. N/ l% `5 K, b% b4 Q% |% W: F3 p0 r
@DELI;3 z$ {/ g) F, N1 U. A

1 r( V, s1 i' D1 n8 E#BinaryMultiply#* J9 i5 F! \- C. n* [' A8 a
使用a*b(重载乘法)的前提是: Mod * Mod <= INT64_MAX; 如果是Mod+Mod <= INT64_MAX 就不能使用重载乘法了 可以使用当前的二进制乘法;* |' g# \% C  n9 w' D

& O/ c, G9 _7 o! R4 e6 b( Z@DELI;
; ~# w5 P! y9 W3 Y2 U
- u: x& W) |% f5 G. |* t#__Cout#' L8 P( L* p/ E, T3 {1 c
这个函数的目的是: 特判, 即对char/string/const char *的输出 重载, 之所以不是放到<<重载运算符函数里, 是因为 如果是<<重载 这些基本类型 就和系统cout的内置重载函数 冲突了;$ m( x1 I% Q; ]7 W2 u. K: [
也就是, 比如对于vector的重载 是放到operator<<里的, 而对char的重载 是在__Cout里;
0 {# f0 e1 Q& {; `5 D" r
, B  P7 l4 }5 _  b% P, |0 i函數
! e, l/ `% J3 f" `4 i#IsInInterval_#% z6 |8 O' H4 K6 i: p% I
. IsInInterval_(c,l,r, true): 判斷是否滿足`c>=l && c<=r`, 即在這個區間裡;8 s' i# Q0 [+ H% w9 l8 o
. IsInInterval_(c,l,r, false): 判斷是否不滿足`c>=l && c<=r`, 即在這個區間外;
% a( }2 L9 f- s% ^' X1 I1* T, V# [' B; a$ ^1 p
2, h: ^; h& f. m4 ]# r" c
3
! K/ G" o/ o6 mInteger6 w& J6 H3 @; g. ?* J
GetPowerRoot( a, p), 比如令T = a^{1/p}, 则返回值为T的下取整;
" I& Z, \% t# ~6 F9 D( o: M+ x! K6 [6 S
@DELI;
1 j# E8 R+ \0 @1 W% l& R& J4 u
% l1 k4 E3 I+ F1 s* L' TVectorToInteger和IntegerToVector是互逆的;
! s; M. @# a% o- I# B4 v數字的高位 就對應 Vector的開頭; 這樣設計是因為: 對於一個整數321 我們通常是從高位開始閱讀 因此高位對應vector.front();
1 A% O0 Z0 s$ r$ x# P" g. 比如, 整數321 (3是高位 1是低位) 她對應的Vector是[3,2,1] (3是開頭元素);
9 g: x. T; S' E# D5 a* P/ C
+ N1 Y" d; f- Q* G4 ~. Y; S@DELI;
+ F/ t7 E: {/ i8 C0 _5 x( |! ?- Q0 x
使用该模块里的任何函数 都是谨慎, 最好就是在调试期间调用, 你要充分考虑好他的实际效率问题;
* x1 Q3 f/ K( s比如VectorToInteger( {a,b,c}, 5)这个函数, 其实 你可以自己手动写成a*5*5 + b*5 + c, 没必要去调用这个函数, 因为此时你已经得到了{a,b,c} 他的长度是明确的 去调用这个函数 反而效率非常低;
! e; |4 F8 w2 k- A8 J# ^
1 f% V1 k! z; ~; d' ]@DELI;
5 g8 B7 x# b7 f) y1 T, t4 n
4 c& ]; `2 q' ]6 C' evector<int> IntegerToVector( _T _a, int _len, const int _radix);
% r" \- ?; f0 h0 m' R7 z  p5 a) M5 f比如a=10, radix=2, 他對應的2進制表示為1010, 那麼此時你必須保證len>=4 (否則會報警);4 M% y, _0 p% t3 P; \4 L
. @IF(len==-1):[答案為[1,0,1,0]], @ELSE(len!=-1):[答案為[0...0,1,0,1,0](即前面補充前導零 答案長度為len)];  e' Z8 M6 x' s( S
- n, S4 I" ~1 W  A
@DELI;: w- y+ U9 k9 q# s- r, C/ w

+ ^: _. |% C$ L/ \5 h2 q* `+ ZSqrt( a, p)5 F- R2 l6 }3 Y3 F6 N0 q4 c
要確保a>=1, p>=2, 假設答案是浮點數b 且返回值是b的下取整;
0 a+ U9 p+ X8 J/ g這個函數的主要目的是 判斷a是否是p次冪 如果是則返回其p次根;
% ?# |3 K3 r4 t8 {1 e  N1 J. 由於b = pow( a*a*a, 1/3), 此時b可能是a-1/ a, 而答案是a, 所以要判斷 是否b+1 == a;
5 K7 E0 v& r0 P* [3 Y2 C. a
& }2 `* Q/ U' s# ?6 L  g@TODO
7 V( h; l% U( N4 ?, _* _3 jModular里面, 我们用unsigned T来存储结果, 但实际上 你的取模值 一定是[0, T)范围的, 即只使用了一半, 这是因为 当涉及到+-时 此时不会溢出;1 `; _" T% m: `1 l) R7 r7 g9 c
. 但这有缺点, 当你Modular a = -2时, 此时构造函数是-2 % 5 他会变成int % uint -> uint%uint 即-2会变成uint 这就出错了!!! 因此要写成int%int;- h+ Y+ k% _  g
最好是, 你就用T来存储结果, 当相加时 他虽然会溢出 但其实他还是正确的! a += b; if(a<0){ a -= Modular;}就可以了;
& I! n& k0 u+ o) w; b! n" z9 M
/ i6 d2 q# s" q错误  Y6 Z8 X# N8 f6 j
is_floating_point_v< Double> 他是等于0的! 因为Double是我们自己的自定义类型;
; N: c% `6 \8 |3 n0 w# I% T  I) |你可以写以下代码后, namespace std{ template<> struct __is_floating_point_helper<Double>:public true_type {};}, 此时 就可以了;7 ^+ A1 h" Y) h- m  {
7 \0 J: S  M1 C% m! B
算法模板编写规范/ a% C. p; r7 o9 m+ m0 X2 P7 ^
错误5 p. p* m7 @: `" E# y
模板类 不要写构造函数, 因为我们可能写到全局域里 ST s(而不是ST s(??) 此时不能有参数;# g1 b* H% U, y/ H# p# M

2 I/ b; U8 E1 z( V8 q@DELI;
8 Y7 D( `2 ^9 ~* F  X! H* h, c3 v" k3 F% S) ]7 ]
不要写namespace ST{ using T = ?; vector<T> DP; void Work(){}}这种代码; 这样会导致ST是一次性的 即T是唯一的; 然而namespace不能加模板;/ q1 r& ^+ k$ x/ F
一种做法是: template<T> struct ST{ static vector<T> DP; static void Work(){} };, 但这样有2个缺点: (DP需要在类外定义 因为他是static), (由于ST是类 而实际上 他里面都是static的 不会用到他的对象 这就违背了类的初衷了);" R0 F0 Q+ O3 @' B
最优做法是: namespace ST{ template<T> vector<T> DP; template<T> void Work(){ 使用DP<T>;};
  D* T9 d8 b5 s8 i; N
) |2 d5 B, X. j* Q+ T* w性质
7 G3 f; A+ O( r8 o# b. S8 E模板类里放大数组constexpr int N = ?; int Arr[ N]; 等你用到时 再把?赋值, 这种方式 他确实是效率比vector<int> Arr要高, 但有个缺点是 你到时候的类对象 就不能放栈空间了 需要是static ST s 否则大数组就爆空间了;
- p, t" o$ w2 T( @% n& ]: E
  u5 [, |# G( y& c5 E4 P@DELI;
% g; Y0 b4 K8 e: n- J0 w
8 Q$ t$ ~( S( r5 T不需要寫一個TODO_STATIC_的宏, 對於靜態的@TODO, 你直接寫成注釋即可: @TODO: xxx, 然後實際使用時 再把他給注釋掉即可;
. s3 m+ B/ R$ g5 ]' i4 s8 ]4 K! \- q% U( I2 B4 `8 y
@DELI;! ?' f! v! R; e  x4 O/ V

! K( l- B9 G; D  w. n* h8 @#讓某個函數 必須在程序開始後執行一次 且只能執行一次#
& o, N! U0 r( f$ D8 C" u% y4 Q( A, ~% Z) R
void Init(){
$ s: |& h7 k* c0 }$ b7 A+ D8 d        EXIT_COUNTER_(2);. V9 U  p# V0 Q6 m
}
% `# b/ C6 r; x! P@TODO: Init();
! w4 {" R# u4 u- {; x% g  ?13 m" o. t) |+ X/ C, w0 c7 G6 b
20 C$ o6 l$ d: F9 }6 o
3
" b- y* \' J) H8 |6 v6 d4
) d* ?2 }: X6 v& L這類函數 通常是不可以有函數參數的 (比如篩質數函數), 也就是 她的參數 是根據題目的最大數據範圍 而不是錄入的值;
; N0 [, [+ x* W! x; v+ H1 s7 w
* E; ]7 s8 F' H+ G不要用__attribute__((constructor)), 她是報錯的, 因為他不是在運行時執行的, 而我們的需求是在運行時執行;9 l, N6 X' x% R1 j# n
- z- b' E" Y9 F% q9 e0 D/ t
@DELI;7 M: }0 G. q' o! M
. J# Z2 W/ F" H7 |$ z7 g; [1 Q
#類/命名空間的Debug調試#
+ U. i, y% d3 r) z9 o2 Z; F- L( H8 u; H' _: @( Z
class ___X{4 j# a. x6 W4 m- U( O5 V* o
        friend ostream& operator<<( ostream & _cout, const ___X & _a){
6 j, L: E" z8 x  ]                _cout<<"\n";
' v* k3 k: X3 {/ Z& u! o        DE_( "___X-Debug-Begin");, c# s# H, {; O/ M2 X/ B6 \4 ~

' r( w* W" U7 }# {4 u8 o$ x. C        cout<< ?; // 此時不可以使用`DE_(?) 或 `Debug::__CoutItems(?)`, 必須使用原生的`cout`;6 Y- ]0 y, h* M, ~

0 N+ [; q' V. Z1 o        DE_( "___X-Debug-End");/ G! J, i* Q1 ~2 w. }
        }. q$ {1 g! a# |+ f7 |
}) P& G, M+ E. }- T; {; q  N6 q

8 m( v; j( N" p8 knamespace ___X{: a+ O5 x3 ~+ a$ ?7 f
        void Debug(){
5 V( s2 ^0 o+ Z1 ?) T, x( d1 G                DE_( "___X-Debug-Begin");
7 s5 o: q1 p- `) J  M1 @; C# I. x. R) D  Z* P& q+ V
        cout<< ?; // 此時不可以使用`DE_(?) 或 `Debug::__CoutItems(?)`, 必須使用原生的`cout`;
, f* X; `: X# J0 Z, @( j1 e; B, l% w, o3 M% }6 C" E- N
        DE_( "___X-Debug-End");
; Z  I4 S0 [) n0 u5 l5 K        }
4 ^8 _5 t& L1 E/ q& |6 O+ |}; `4 E  ]( L& h4 w

3 y! _9 c. b; g% X$ B8 E6 o" w@DELI;
9 o  \6 |: H3 B
, l1 Q( N- |3 J4 `$ l8 O$ @#嵌入模板的全局变量#$ @; e. K9 x* u1 @, ?
) q0 v: L! ]# M2 M4 R1 h0 Q
{ // ___XX8 a% d7 i8 a" O+ T
        const int ___Number = ?; // 这里就叫做全局变量; 要以三个`___`开头
3 |" \+ F8 U0 K1 N' l! k& L        int ___N = ?;
! h; J% N7 {" E3 F        for( int i = 1; i <= 5; ++i){% X; {0 Q0 R, i# x- ~* _7 b$ u
                int a = ?; // 像`i,a`这种*临时变量* 可以不用写`___`开头;) v3 P% c0 S& A. i- q- J8 u
        }
# k3 @$ E2 k5 @+ L3 h4 \        $ o4 R" Z  ?6 w2 ~- @
} // ___XX/ K0 r* n; |. _; v
4 {# x6 U% l0 `+ g
@DELI;
1 \0 p  H& ]: M! \5 e: H6 D- q. z/ `' L1 z1 l
#Initialize函数, 强制的放到构造函数里#; G; V' K1 q1 h0 P
最经典的例子是(建图)$ P) _3 t  B, F: o: C! e
, l! q, H: q! g( n# H
Graph( int _points_count_maximum, int _edges_count_maximum){}- o1 I) \9 e& R) G6 p; ~  {
void Initialize( int _points_count){}- B& |; H, \6 I2 x- c3 t6 K0 W, P
12 J8 }8 ?* K: O# h2 m: g6 v
2
* N! C( u. Q/ D1 ~& s( ^* }这样分来 会导致, 每次使用时 必须是: Graph G( 100005, 200005); G.Initialize( n), 也就是两个代码行 (两个操作, 两个步骤)
% B& }3 U$ K: {* D. ~  T. f$ \* E$ `一旦忘记手动的调用Initialize函数, 虽然会报警, 那你还需要再去写代码 补上调用这个函数;
! s8 `$ N2 L7 T4 X% x1 V8 w9 _, @3 Q2 B
当我们将Initialize函数, 嵌入到 构造函数 里
5 E4 h+ C" R0 Z
& k) b* M  K& U6 u: c, F8 c& z- ?Graph( int _points_count_maximum, int _edges_count_maximum, int _points_count){4 A& z2 s" w% H" N; c
        ...* g% ]# D& j# R+ t- W7 |
        //--; s& Q0 x2 i& [' y7 z5 N! Y
        Initialize( _points_count);) i9 e6 E9 O' {: Y& Y0 H  R3 t: ?
}8 q2 j4 W1 A! S) {8 F
void Initialize( int _points_count){}
% W5 s7 v2 J1 W3 L. L# m" X2 Q
7 N( w- @+ s- r  y' H3 E注意, Initialize函数和原来是一样的, 只是做了两个事情:
2 G- g; q% O4 ]1 将Initialize函数的参数 接到构造函数参数的后面 (比如, 原来构造函数参数是a,b,c, Initialize函数参数是x,y,z, 那么现在变成构造函数参数变成了a,b,c, x,y,z)% v" S' s! {/ C1 x5 c( U4 ~! {2 h
2 在构造函数的最最结尾, 调用Initialize( x, y, z)函数;* e  D7 u* w4 B

  j5 z6 v: V$ z# ?5 j6 K@DELI;
! D; c- O: ^$ `0 O0 Q
* K9 O4 V: M+ n! E6 N6 G1 o' |1 U#数组长度用函数传参来指定#
) W5 l4 j. ], m. e4 ?2 R: ~6 V: H
template< int _Maximum>
9 u. c6 F8 Z+ Dclass ST{
& f; ~8 O) x- I9 G* b( Q2 G4 C, C        ST(){2 ^% e) G1 [* b! \
                array = new int[ _Maximum];
! S8 g+ R8 Y8 w1 E7 C        }
8 q7 A* Y# O6 z2 Fprivate:# M# r0 C0 l/ Y/ O
        int * array;
2 Z+ b7 t7 o1 n, _};! ?2 ~. O8 s* M  ~, E' z* i( [
! y: l0 b# y7 P* Y0 w$ R
The above code should be replaced to:
5 w  e( L( _. Z; v, S; y' w4 w
1 h+ Y* U; q' t1 Bclass ST{' ~7 I/ p! Z5 q
        ST( int _maximum)& ]& X. l$ z6 P" r2 V
                        :5 P. m' c  r: J  T+ [
                        maximum( _maximum){5 I9 E/ ?) {3 t0 B* i* s" V
                array = new int[ maximum];6 e, u: y4 k+ E0 p$ _6 e2 d
        }
" M3 F/ V5 J; W6 ^private:
7 y7 ^2 n7 }8 T0 L1 h8 O        int * array;
( p7 k6 C  k/ x. I        const int maximum;7 P5 e3 _% g2 k$ ~! m" E( [
};
" c  {- q; ?. r; i4 u+ |8 f( Z+ V0 s' j; A! G
@DELI;( b% |: ~1 r$ Z+ i& r& E# s
笔记
  }/ C/ n6 c: m有向无环图DAG9 \" q4 Q; n* o; ?
最小路径点覆盖0 S2 N: L6 x: \, A3 l
//{ @Snippet, `ZuiXiao LuJing DianFuGai (最小路径点覆盖)`! x* J, Z' M6 F2 p8 `7 W( ]( a
{
8 w3 {3 h  h1 d& V    int n = `the points-range in the DAG`;# p, ^- ~) t; K
    //--
1 i1 r+ q; b' x1 q    BipartiteGraph B( n * 2, `the edges-count in the DAG`);
1 B* e3 `8 ]$ ~    B.Initialize( n * 2);' u" A1 i% j1 g2 C
    for( int i = 0; i < n * 2; ++i){
1 h6 R2 @1 O/ p" n        if( i < n) B.Set_pointBelongingness( i, true);; z5 e: A' N5 w3 d# M" P4 M
        else B.Set_pointBelongingness( i, false);' B( a! M; u. l  @) o+ A7 ~
    }
* T9 o1 i, I& F- B) q' f    for( `s -> t` : all edges in the `DAG`){
/ I( m$ i8 K: v/ c) P5 R% x        B.Add_edge( s, t, 0);
# C9 B) ~+ H5 i( u    }  q% G, k& t* ~% O
    //--' \! Z% x- J) [: m. e
    Bipartite_MaximalMatch M( &B);
1 g) K9 Q$ s  s8 v' Y" m    M.Initialize();3 J' S' \$ g. t3 G$ M
    $(n - M.Get_maxMatch()) is the answer;7 p, G1 [7 u$ E6 C7 i, G
}
7 @8 t, B0 b. F' S/ z//} @Snippet, `ZuiXiao LuJing DianFuGai (最小路径点覆盖)`
; n* {: N. z) b5 h& b" z! q& m/ k+ P1 V- [- l8 q
最小路径重复点覆盖, 最大路径独立集
% }  I; _0 e6 i, V% E//{ @Snippet, `ZuiXiao LuJing ChongFu DianFuGai (最小路径重复点覆盖)` `ZuiDa LuJing DuLiJi (最大路径独立集)`; Q! G2 @0 r0 t0 E) _: {
{# G& m, p" C, V$ o2 l8 R
    int n = `the points-range in the DAG`;( _2 A- T! m3 }0 s$ t
    bool * edges[ @PlaceHolder] = $(edges[a][b] means a edge `a->b` in the DAG`;
5 ^1 j  x& j0 w/ j. t$ n    //--
. k/ i3 ^. a2 n9 P2 R    $(perform the `Floyd-Boolean` on @Var(edges));
4 [$ M+ k6 p  g% P# F! J    //--3 \% N% v1 q. k& e
    BipartiteGraph B( n * 2, n * n);
/ T; Q! s$ ~8 |0 w  C2 ^1 _) h    B.Initialize( n * 2);
7 N/ W! K# e- F    for( int i = 0; i < n * 2; ++i){
5 X6 b; C# d( \/ B/ N+ e& ^        if( i < n) B.Set_pointBelongingness( i, true);/ y, `4 H1 Q! e$ m' q* @3 _
        else B.Set_pointBelongingness( i, false);
# c8 o5 @" F. D2 H% A! t, |    }7 Q' U- C- m/ G6 d" h
    for( int a = 0; a < n; ++a){, ], X5 j5 \, k# l- E% T6 O7 Q
        for( int b = 0; b < n; ++b){
' \, E. C6 h5 O* D' j- `# Q            if( false == edges[ a][ b]){ continue;}
9 ?1 X6 {* {8 ~+ a6 o& T5 Y. ^            B.Add_edge( a, b + n);9 H1 D8 `' ^; u) N+ V
        }
" x; w2 Q8 `4 t! b; ^$ S    }' Y! {$ q; n3 }+ t' P
    //--- F/ c" Y3 U  Z
    Bipartite_MaximalMatch M( &B);
$ B/ ^1 |+ t2 q    M.Initialize();
! A3 v; T: B* r' K: i. W1 ?3 ?* ?    $(n - M.Get_maxMatch()) is the answer;9 C1 ]0 ~8 w3 ^
}
1 b! ?/ v! i$ e% \" C/ y//} @Snippet, `ZuiXiao LuJing ChongFu DianFuGai (最小路径重复点覆盖)` `ZuiDa LuJing DuLiJi (最大路径独立集)`0 L' H; |, `9 I" i) E
+ d0 `2 B6 ~& \8 W! M: N4 W
DAG的终点2 h' E0 ~: f9 S
//{ @Snippet, `EndPoints of a DAG`2 A$ D* ]. V5 v8 p. z* [
{) o: X* u+ f) a1 @$ H
    int n = `the points-range of the DAG`;$ O4 ~* r0 Q+ P
    int * departure = `int ?[ >= n]`; //< the departure-degree of a point;4 W( C% |# u: u6 Z" x
    memset( departure, 0, sizeof( int) * n);5 t# X" N3 l; O: O+ }
    for( `a -> b` : $(all edges in the DAG)){% W+ v4 U3 B9 A$ [: t. i
        ++ departure[ a];# @& t) \: [, g! V) ]  Y
    }' X5 C: f2 p2 u4 `7 F" e2 `
    for( int i = 0; i < n; ++i){' p) f/ }# C$ k, t9 v- B
        if( departure[ i] == 0){
' e2 k9 \! [! L+ `4 n0 ~" u! }//< `i` is a End-Point in DAG
) w5 e3 ~" L6 I+ T2 c0 F        }
( |6 e- D, h% _" B    }- g$ x+ b# f+ u& m" V
}2 l; L0 Y  {9 J! \2 K3 S% b/ C
//} @Snippet, `EndPoints of a DAG`
' l1 ], Y; O8 ]9 B- G$ K8 H2 [+ b  d- K1 f' ^  ]
DAG的起点' ^3 m) d6 y) \& @6 l& n5 W  ]1 h1 i% m
//{ @Snippet, `StartPoints of a DAG`
) n& }) I0 L! v3 {8 p5 N" g: R2 X{! x  l" a9 ?! Z( N: R
    int n = `the points-range of the DAG`;" P' ]: E4 ^: f% s: J) W
    int * incidence = `int ?[ >= n]`; //< the incidence-degree of a point;: b1 ?) w* Q9 X3 ~' ]4 {
    memset( incidence, 0, sizeof( int) * n);
) C0 K9 _+ s( v2 }    for( `a -> b` : $(all edges in the DAG)){  |$ J' Y$ k) Y1 D, p
        ++ incidence[ b];! [' z7 O! j: E* [1 I8 Y
    }
; m7 k+ D# k+ P- c6 E' {$ X    for( int i = 0; i < n; ++i){
9 h1 c9 \" I+ K# j4 l        if( incidence[ i] == 0){
4 E$ E" X6 V7 M+ H                //< `i` is a Start-Point in DAG
  z6 Q* B) n+ a! L        }& G; m6 w6 W+ F  a# k
    }
7 g5 B& p3 e: u8 }2 G6 s4 h}
) A) ~% F, J- ^8 D3 I# W$ J//} @Snippet, `StartPoints of a DAG`6 N  \! p2 a# F5 A4 u
9 H! H8 @0 `% T& ^3 X( _! t
判断一个图是否为DAG, 求拓扑序: q8 h) ^8 T: v" e
bool Work(){. y- B# H1 O# f" X6 h2 [# e
//< `1` Check whether a Graph is a DAG; `2` Get TopologySequence;: X3 Q, q. t; D2 M8 v* Y9 K0 O
    int points_range = @Unfinished;* o0 R# p5 u, N  S% A% t/ ^
    int * topological_sequence = @Unfinished(an outside array whose length must `>=` @Var(points_range));9 J2 h# V) W7 A- v3 v7 h, n
    int * incidence = @Unfinished(an outside array whose length must `>=` @Var(points_range));
0 u' e& s' B' }% r3 l    memset( incidence, 0, sizeof( int) * points_range);: _0 _( l- G1 d
    for( `a -> b` : $(all edges in the DAG){6 K7 U5 X; G2 e+ s- D* n" L4 S- A3 a) J
                ++ incidence[ b];
" I' L8 b; _" L' S2 I* s/ T        }
" Y" |5 o0 }* J; ?, G3 i: ]    int size = 0;, Z% }, l# J$ o. D, ^
    for( int s = 0; s < points_range; ++s){
7 j/ H& R( G2 S# f- W- ~  j/ h        if( incidence[ s] == 0){
; q) r* J( c( ]& Y* K0 Y            topological_sequence[ size] = s;
& b. ^# U8 P0 _7 J; R; c$ x0 h            ++ size;; U- C8 C! \$ L  c
        }
8 n; ^  C$ d1 W* [/ r    }, a0 f' ]3 f6 _2 Z
    int head = 0;  G4 K# z$ \* m" [. H
    while( head < size){- l% T8 v7 u. C, j
        int cur = topological_sequence[ head];
7 m+ s. x5 p. h, \6 Q        ++ head;
% Z: l( o; ]- E/ K4 y                for( `a` : $(all adjacent-points of `cur`){
- d$ ^0 o! d, S2 }            -- incidence[ a];
/ t; q7 w* B+ Y- L# l6 G            if( incidence[ a] == 0){2 p3 K* b5 Z# S( L, G3 v
                    topological_sequence[ size ++] = a;1 i6 n8 U1 ]8 x8 n) Q
            }
0 @& C# k  h5 ~/ G- }8 y        }
- y2 ]% ]8 Q1 j. a; P    }
: g" n" B* F, x5 O4 k' v    if( size != points_range){8 j  P  h: Z( P9 ]1 V! S6 m. [$ Q
        return false;! y+ z( m1 Q9 z4 ~. j1 u. d
    }) F+ ?% q0 X0 D+ X! j- z$ S
    //>< The answer Topological-Sequence has been stored in @Var(topological_sequence)# \6 T) e% `4 W# S* X! r1 b# J0 x1 o
    return true;. E4 W1 `% ~/ F3 C0 ]1 w
}
0 \8 O  b6 Y0 {# b4 r; l4 \8 d0 s/ @2 G& L8 C' b9 x
图论
7 k* y2 V9 f0 M8 G8 Y, A最短路. X+ Z, \3 Z' X/ f; v" e9 `7 O
TARJAN6 O; ~+ M0 T' l) U) @4 B9 i
无向图-PBCC点双连通分量2 }) ]- e' M* ?: U0 @# _7 y
+ 割点
0 d2 j6 o  u3 f+ k, B6 ]
  e6 G# q6 W/ v7 x9 f5 g1 Q//{ Tarjan_PBCC-Declaration$ E8 f  k- J" s; S2 f2 S
template< class _Edge_Type>9 @, l8 \7 q2 n8 p' @' t( q8 f
class Tarjan_PBCC{
0 O* c5 v/ v1 `public:
* K: a- ^) z) a  _- j- l    const vector< int> * Pbcc;" E( n$ U% b- M
    const bool * Is_cutPoint;* |7 G( L. Y& ~# P0 H
    //-- variable ends
  J7 o) D& R; u2 C/ T: z6 e    Tarjan_PBCC( const Graph< _Edge_Type> *);
& j) }( n  @0 Y    void Initialize();5 J+ x5 x% l/ I& c  o* }
    int Get_pbcc_count() const;
* N* a2 M: h$ u/ n- Xprivate:* \5 `+ U( b4 J2 k- L$ M
    const Graph< _Edge_Type> * graph;4 a+ W3 k8 H5 w
    int * stack_;( _  y- }/ @" A+ ]
    int stack_top;
4 f) w3 A. r  c$ k3 e3 C% p; ?    int * dfs_id;
: D- g9 ^  s- M& e& v0 W8 q: `    int dfs_idCounter;
: O0 N4 B* {* \2 n& y2 I    int * low_id;
1 @- e7 M9 ?  M5 R7 ^- u3 a    vector< int> * pbcc;
: E+ s2 I! B6 N; ~& e7 I    int pbcc_count;1 r" ]* q! n: g9 @* ~+ q; p
    int dfs_startPoint;9 V& z2 I' h  E$ W( B* J
    bool * is_cutPoint;& \( M! b+ N9 x$ K$ L
    int cutPoint_count;
7 L1 P  j$ [( M    //-- variable ends
% r  h9 z# X5 [! \3 H    void dfs( int);
8 f' _: N" z" M1 [- R. K3 y, l};
2 f: [3 h7 {* R3 @//} Tarjan_PBCC-Declaration0 a0 }" B0 e: Z) x! ~

0 ^* T$ W; B: ^: s$ X6 _( s+ _//{ Tarjan_PBCC-Implementation1 S, |3 y: S4 m4 Q, b; a& \+ R- I
        //{ Variable-Annotation
, R" |- i5 C) N( q1 D; A                //{ @Var(pbcc)
. y  Z; p, `- g, P2 z8 v+ Q& q$ h                // + `pbcc[i]={a1,a2,...}` means that the PBCC with id `i` consists of these points {a1,a2,...}5 I( O$ v% H5 q8 c; m  n. v
                //} @Var(pbcc)
0 }& z9 B2 N7 G8 A/ O# _% f2 ^0 p                //{ @Var(graph)$ D9 q! _( Y# O4 F7 L! K2 j) o
                // + must be a undirected-graph, i.e., Edge[i] = Edge[i^1]
8 |1 v, V6 ~: ~) m! u, t                //} @Var(graph)
9 |* \' s1 B' y        //} Variable-Annotation
% m8 e5 U5 l: c5 Itemplate< class _Edge_Type> int Tarjan_PBCC< _Edge_Type>::Get_cutPoint_count() const{ return cutPoint_count;}
( Z5 ?* E; s- P$ u) c+ Ctemplate< class _Edge_Type> int Tarjan_PBCC< _Edge_Type>::Get_pbcc_count() const{ return pbcc_count;}
9 p; _  I9 L! T! v- d8 M; E, |# Ltemplate< class _Edge_Type> Tarjan_PBCC< _Edge_Type>::Tarjan_PBCC( const Graph< _Edge_Type> * _graph)
, n' ~; s) ]' K+ v& Q        :, S* K) q& g. j5 K- c! _
        graph( _graph){/ |( i2 O$ T7 z2 U
    stack_ = new int[ graph->Get_pointsCountMaximum()];# q8 l8 s! j! O) x; a7 o* S
    dfs_id = new int[ graph->Get_pointsCountMaximum()];
- |/ d2 [1 R+ f2 m2 I1 t    low_id = new int[ graph->Get_pointsCountMaximum()];% X1 N4 z' v" }7 \# N* l
    pbcc = new vector< int>[ graph->Get_pointsCountMaximum()];+ U7 H! P. o* N  Q7 E. g
    is_cutPoint = new bool[ graph->Get_pointsCountMaximum()];) e7 h) c' Z: P; `" d8 {
    //--
8 _9 N% S2 V) u. {4 O3 T  p    Pbcc = pbcc;! [7 y$ q9 F' v* r$ e
    Is_cutPoint = is_cutPoint;
: T$ C! V3 `, S; I3 r+ u+ W+ O}' ~9 d) f9 O0 ?6 t$ v$ m" x
template< class _Edge_Type> void Tarjan_PBCC< _Edge_Type>::Initialize(){1 a7 i0 R6 Y, H2 z7 d9 `
    stack_top = 0;
5 W6 f, p* C/ V- Y  h    dfs_idCounter = 0;
, V2 n( j" X" X. c/ f    pbcc_count = 0;
6 `7 [& G* y& z; [! r' t    cutPoint_count = 0;
. b  }0 t2 l+ ]6 Q. k4 `0 o  T    for( int i = 0; i < graph->Get_pointsCount(); ++i){ pbcc[ i].clear();}
3 E9 |4 ?5 b5 |, ~+ v    memset( is_cutPoint, false, sizeof( bool) * graph->Get_pointsCount());; ~. U8 b0 p, g4 R
    memset( dfs_id, -1, sizeof( int) * graph->Get_pointsCount());! x$ |- b1 n& t* Z6 Z
    for( int i = 0; i < graph->Get_pointsCount(); ++i){
! I# k; e/ R( g% h/ Y. t        if( -1 == dfs_id[ i]){
: N7 L0 k! F( F            dfs_startPoint = i;
  `9 ]7 p/ b6 f; ]" c* K            dfs( i);
. Q9 ^5 H2 h9 p8 t. |* k2 q        }7 c- H5 l- Q  G0 d  m+ T
    }7 u/ U( ]4 n2 b  [( Y" |* _
}
7 L& E4 P/ Y( K- V; Y) V( j/ Itemplate< class _Edge_Type> void Tarjan_PBCC< _Edge_Type>::dfs( int _cur){- l0 E, J, _  a; S7 w
    stack_[ stack_top ++] = _cur;( T- f1 E6 A4 B0 {
    low_id[ _cur] = dfs_id[ _cur] = dfs_idCounter ++;
) u( J4 }, N4 u    //--
2 `$ \% O- l+ p# ^9 p    int cc_count = 0;
5 I, I+ e* ], q* }! h    if( _cur != dfs_startPoint){ ++ cc_count;}
6 S) p7 K$ W: D, w    for( int nex, edge = graph->Head[ _cur]; ~edge; edge = graph->Next[ edge]){
4 m: T- m# N" K* p( s        nex = graph->Vertex[ edge];
# }+ V% ]( e! a; Z" Z- h2 j, L( V& |        if( -1 == dfs_id[ nex]){- q% [6 u5 h  Q9 Q0 j2 e5 n* l
            dfs( nex);
: A8 L$ ?2 C* ]8 {( U( }  q0 d# l+ C            //>< `low_id[nex]` always `<= dfs_id[_cur]`/ J3 v  X% N3 p2 M& O  o
            if( low_id[ nex] == dfs_id[ _cur]){
! {; K9 Y8 }& }- o8 n                ++ cc_count;
& Q* b$ g# u7 t- E# _4 a                if( cc_count >= 2){
$ r8 z! }4 {3 z: w5 Q                    is_cutPoint[ _cur] = true;
* J8 j3 l, s/ @                    ++ cutPoint_count;
# O; n8 h  K. J2 ~2 `6 x/ K% C! e                    while( true){
) n0 G4 d# Y0 Z3 x! G; \+ v9 ^# \3 H! ~4 r                        int c = stack_[ stack_top - 1];
- P4 M9 {, U0 |2 m8 H1 h. g# Y$ c                        -- stack_top;
1 [: P% o& D: z* M                        pbcc[ pbcc_count].push_back( c); //< the pbcc_id of `_cur` is not only `pbcc_count` if `_cur` is Cut-Point; i.e., any Non-Cut-Point must belongs to a unique Pbcc, while a point must belongs to `>=2` Pbcc when it is Cut-Point.
1 g, F, \* e% q4 T  l( C                        if( c == nex){ break;}( k, q4 p2 J# |: O, S. F- D3 f
                    }4 A( h7 ]9 n" D7 F& p( K5 W
                    pbcc[ pbcc_count].push_back( _cur);0 [9 u+ {8 G! S
                    //>< `pbcc[ pbcc_count].size()` >= 2
- @) o4 p( A$ D+ s                    ++ pbcc_count;7 p' ^1 r7 b& a8 ~0 Q
                }
( c5 g$ E# n  _            }
; A" G2 v3 P5 o/ C% {. l- O            low_id[ _cur] = min( low_id[ nex], low_id[ _cur]);
! |) ]) C: t+ r7 D: ^7 e        }" M0 T/ e3 T, ?; q
        else{ //< `nex` must on the `stack` due to the graph is Undirected( o: D+ h+ U% T& [' ^) K
            low_id[ _cur] = min( dfs_id[ nex], low_id[ _cur]);
/ E3 J( Q. H; Z        }
, t8 P2 o) f& C1 A7 L. s% {    }
5 A" I: Y1 E  N! {7 C* O3 f  e    //--
7 ?* c# H% L" f' p* f* Y    if( _cur == dfs_startPoint){2 D* p! a9 k2 w" o9 A: J  A7 \
        while( true){* O0 E7 o* W2 h. J0 B
            int c = stack_[ stack_top - 1];9 Y; f  a4 m: [6 p3 a7 Z; g8 _
            -- stack_top;4 q1 i4 g+ V3 ]. ^+ G
            pbcc[ pbcc_count].push_back( c);
9 y; W8 F! \$ l            if( c == _cur){ break;}! _2 d) b; K4 D0 V3 T& w# Y
        }
" H0 W3 }6 P) h% k3 U" N. e        ++ pbcc_count;
" d8 _: \% z& o9 {/ u    }- D+ j3 T5 [% f! s+ k" q1 p
    //>< `cc_count` means the number of Connected-Component when `_cur` was removed from the current Connected-Component (whatever `cur` is Cut-Point or not);
2 b! N+ ]% z, D2 B. I: z}4 o+ J2 _# _# U7 k; V& R" M5 M
//} Tarjan_PBCC-Implementation3 g; c& `+ T: A- ~) v( A) }

) y4 z8 V! y1 a8 v9 M) Y1 r4 n无向图-EBCC边双连通分量: A- u8 |, _4 U: w
+ 桥
4 m5 m; P: ]3 ?3 q4 j7 ?  z8 M% `' D3 {2 C1 n& {
//{ Tarjan_EBCC-Declaration
9 D. E0 x4 ]! N  m6 n0 [6 Q! Ttemplate< class _Edge_Type>
( A" A% q5 e7 l0 L- b6 _& jclass Tarjan_EBCC{
8 ~* s4 f5 ]3 z5 P5 V  Npublic:
( w. z/ i( A# d' ^    const int * Ebcc_id;4 C) i6 x( [% X" ?+ |8 ]
    const int * Ebcc_size;
# k1 ?* V# {% v/ R8 i& S! L    //-- variable ends
: v# @  y, `0 g+ @% I& V    Tarjan_EBCC( const Graph< _Edge_Type> *);
# @* F# ^+ V) N4 A$ ?    void Initialize();
  q' m. E5 u6 i8 \    int Get_ebcc_count() const;* R6 x& q0 _  T8 |" }+ t$ w
    const Graph< _Edge_Type> * Build_tree() const;
6 s5 F3 @1 h/ Pprivate:
2 H# _. Y' [; _5 `    const Graph< _Edge_Type> * graph;$ g# k! b% u3 @9 H$ L7 a% s+ i
    int * stack_;5 a5 B8 B- x6 T9 Z+ k3 v4 V
    int stack_top;
& C+ f' Q( M) K5 v    int * dfs_id;4 r: Y6 I/ o5 @9 p& b
    int * low_id;* N1 A2 l# g2 h
    int dfs_idCounter;" u# q0 X, ^' h4 }& k: I
    int * ebcc_id;( `2 z! I% p/ q* U
    int * ebcc_size;
+ \. X% e3 ]9 X" e! e& G    int ebcc_count;
% G7 |; g- s6 Z" m- f8 V! W5 G    //-- variable ends
% {+ q; K6 s, A% n6 `- r    void dfs( int, int);9 p2 D+ g7 O, u9 I: X4 P' ?) M& A( \
};
* J! ~! L7 d- ~//} Tarjan_EBCC-Declaration! m6 D7 O4 D4 D1 z6 p$ V; L

" M: E! c0 Z3 J2 ?, F  f//{ Tarjan_EBCC-Implementation$ A+ p1 t& Y9 E
        //{ Variable-Annotation2 ~; L# g5 i' J5 }* b
                //{ @Var(graph), t; A, [& s' h# q# ?
                // + must be a undirected-graph, i.e., Edge[i] = Edge[i^1]+ k/ ~9 C: q7 i5 w
                //} @Var(graph)
( ]- H7 ~# j0 x                //{ @Var(Ebcc_id)# B4 i1 T  z+ U" V: a7 e, [
                // + `y=Ebcc_id[x]` where `x` is a point of @Var(ptrRef_graph) and `y` belongs to `[0, @Func(Get_ebcc_count)-1]`
" }1 \* [) T; I7 `: Y) k3 S                //} @Var(Ebcc_id), b9 Z5 ~$ P6 c: R
                //{ @Var(Ebcc_size)
+ _) K; \) R# E9 q1 b% G$ A1 N/ v. Q7 R                // + `y=Ebcc_size[x]` where `x` belongs to `[0, @Func(Get_ebcc_count)-1]`, the sum of `Ebcc_size[0,1,...]` equals the points-count of @Var(ptrRef_graph)
$ A! S' w; P+ x1 p6 V0 s                //} @Var(Ebcc_size)" J' v' z' b& E8 Y9 u
        //} Variable-Annotation
% x/ h# f/ r* q/ w. @0 T- Y/ ltemplate< class _Edge_Type> Tarjan_EBCC< _Edge_Type>::Tarjan_EBCC( const Graph< _Edge_Type> * _graph)8 g- Z, r; u2 m" i+ c9 R
        :! _3 @2 P5 n- N# N( n, D
        graph( _graph){
8 q' i6 p) I) p( T, z, K3 j    stack_ = new int[ graph->Get_pointsCountMaximum()];
9 q% H$ q. f3 P' A    ebcc_id = new int[ graph->Get_pointsCountMaximum()];
- z+ {& K2 E; [( X0 _4 q    ebcc_size = new int[ graph->Get_pointsCountMaximum()];# _+ s( ^8 G1 S# ^( u! T
    dfs_id = new int[ graph->Get_pointsCountMaximum()];, V3 R" Y7 N8 u0 |; n$ d0 _
    low_id = new int[ graph->Get_pointsCountMaximum()];2 V: Y% K  ]) h; w4 s  T8 l. n
    //--5 O* Z+ d( y; L% h! m
    Ebcc_id = ebcc_id;$ t" k- v+ w' o
    Ebcc_size = ebcc_size;, d( F. i% I6 k9 e- [) n) b, `
}4 {9 L( J/ P6 i- l; v, n" W
template< class _Edge_Type> void Tarjan_EBCC< _Edge_Type>::Initialize(){& _. S1 n3 u; I1 G! [( m+ N
    stack_top = 0;) S: A4 B1 H2 C) s
    dfs_idCounter= 0;- E, `7 p6 @  [+ W
    ebcc_count = 0;$ c8 x9 V) U8 U$ @4 ~
    memset( dfs_id, -1, sizeof( int) * graph->Get_pointsCount());
# ]' b+ `/ `. ?5 d' ?6 a3 |: W    for( int i = 0; i < graph->Get_pointsCount(); ++i){$ l! \. ]1 O7 G1 M( u
        if( -1 == dfs_id[ i]){, ]. g" A: I! Y
            dfs( i, -1);" Q# ~' ^$ w& f! a; s0 L1 v& x3 H% _
        }
) F& H8 y) f+ g4 B/ i    }6 _* w/ D' K" J6 _8 D+ F
}
2 V2 ~8 z$ K1 k+ I4 c, o7 ntemplate< class _Edge_Type> const Graph< _Edge_Type> * Tarjan_EBCC< _Edge_Type>::Build_tree() const{; c! ^0 n2 }( ]: P, W; ~; x& O
//< + Make sure @Func(Initialize) has been called* h: a( ~- \# @- [. b& R
//< + There is at most one undirected-edge between any two points in the Tree (i.e., @Ret)
, m& I4 w5 B* f6 P; O& G( m    Graph< _Edge_Type> * Tree = new Graph< _Edge_Type>( ebcc_count, graph->Get_edgesCountMaximum());
9 n( [7 w" g# v% M% R    Tree->Initialize( ebcc_count);; y/ y5 m; D! f9 ~( \
    for( int a, b, i = 0; i < graph->Get_pointsCount(); ++i){
% U) z! B  a: [& e        for( int j, z = graph->Head[ i]; ~z; z = graph->Next[ z]){
( j# f# {, n, x. `8 W& E            j = graph->Vertex[ z];) P% J% z! v- c0 f: r  W6 y
            a = ebcc_id[ i];( o$ {0 u; ]0 Z: c1 K5 F- x
            b = ebcc_id[ j];  W% f9 |% z: p+ s* j5 B: B, U
            if( a != b){7 j. i+ ^# z: w- x% |, h% k1 f
                // Now, there must has no edges between `ebcc_id[ i]` and `ebcc_id[ j]`
( ^: B1 y  T7 h3 y+ ?; L' y                Tree->Add_edge( ebcc_id[ i], ebcc_id[ j], graph->Weight[ z]);
* w7 Y2 d5 B6 K/ }$ s6 E- F  o            }
" g/ B. M' ~  ~        }
  B& N% V" }# h% X& K    }% e/ B3 T) o) J/ C3 n  F
    return Tree;
6 o# f7 e- B% ?! t" [* T" p; a}  C4 l2 A8 ~7 s/ N8 n3 T; [
template< class _Edge_Type> void Tarjan_EBCC< _Edge_Type>::dfs( int _cur, int _father_edgeId){
% B9 @' ?1 Z* K+ r# f/ L    stack_[ stack_top ++] = _cur;
. j5 p' P+ S4 h% Z    low_id[ _cur] = dfs_id[ _cur] = dfs_idCounter ++;
, ^& H) v) S. x& X* z1 J# `( \( O    //--3 q1 f$ f& R, A& O
    for( int nex, edge = graph->Head[ _cur]; ~edge; edge = graph->Next[ edge]){' A( `4 C6 M% j9 o/ V/ A
        nex = graph->Vertex[ edge];
$ s  m# ^. j! ~7 e$ Q        if( (edge ^ 1) == _father_edgeId){ continue;}
8 P/ Q9 m) |; P. k- o        if( -1 == dfs_id[ nex]){
& W0 S2 o- e' L8 B4 o/ l, }+ K/ W/ M            dfs( nex, edge);% j0 i8 X- t+ f' b5 p- W
            low_id[ _cur] = min( low_id[ nex], low_id[ _cur]);* V  {( t6 t  `1 q7 A
        }
& A+ p# u' U4 X* i        else{
1 J) w8 S4 F- f+ g3 p            low_id[ _cur] = min( dfs_id[ nex], low_id[ _cur]);
  W/ m, P  _+ Q' N1 W6 r        }6 g6 ^; B; S, z3 v% e: Z+ w
    }
" Q- w- C' z$ `4 P+ }8 p7 c    if( low_id[ _cur] == dfs_id[ _cur]){
* g# b! c( F3 _' ~# o# j5 `, |* n        ebcc_size[ ebcc_count] = 0;( m+ e: G3 q" T
        while( true){* t" H. U: t: E* `- V
            int c = stack_[ stack_top - 1];
" f4 `& `* ^" ^6 {4 i  i            -- stack_top;
6 d: J4 @6 _8 z            ebcc_id[ c] = ebcc_count;6 @; \  _$ m8 M
            ++ ebcc_size[ ebcc_count];
) t) M6 s* H  C& L            if( c == _cur){ break;}+ }- ?' k* b0 {' h( X. S
        }
- l: z; G8 h( f  @8 g        ++ ebcc_count;6 }- p1 d. I+ ?: H
    }
. o9 m8 V+ k5 X1 R& J}$ {- h0 B; Q. V% m' X" z( g: [5 W
//} Tarjan_EBCC-Implementation* V. V2 n" E/ q4 B8 X' e

$ w5 k: F9 J5 L1 eSCC有向图强联通分量" J/ g" w' V* C
//{ Tarjan_SCC
; O$ `5 X: j  `template< class _Weight_Type>4 e$ C3 F! E& L  P8 ^6 {
class Tarjan_SCC{
2 X4 ?' l; u" ]* p: `. U& j7 Upublic:9 j+ H" _& f) p  j( e& L# K' r
    const int * Scc_id;$ Q8 C7 R7 L2 C8 @' X
    const int * Scc_size;7 Q2 M8 X) u& I) X; R% O$ {" \
    //-- variable ends
7 x" W' h7 v) H) E7 S    Tarjan_SCC( const Graph< _Weight_Type> *);! w; \7 n# V/ T( Y. Z) ?3 k% p% Q
    void Initialize();
5 o, C- F5 ^% L  l9 T7 ]! _2 o    int Get_scc_count() const;. u7 A$ o: g! }% h1 Y! J6 |( x
    const Graph< _Weight_Type> * Build_DAG() const;
: m( j; B& Z8 h& B  {- L    const Graph< _Weight_Type> * Build_DAG_uniqueEdges() const;
, k$ t* _; Y5 Q; U4 H+ h& @' b. rprivate:6 y* P6 W: @+ A, D3 b2 |3 I+ M1 t
    const Graph< _Weight_Type> * ptrRef_graph;
# P0 S6 [* o1 D9 t    int * ptrNew_queue;
( L' O4 r4 g, ^/ e6 I) ^    int queue_tail;
  p/ ]; |) f- b; O    bool * ptrNew_isInQueue;
5 U, ^' f, R( K    int dfsOrderId_counter;
. v5 G( D6 s" b( {, \7 y    int * ptrNew_sccId;
0 @/ |5 P: N; D& S    int scc_id_counter;
) l, R  ~& H  r8 @+ m! x( _! r) ^    int * ptrNew_sccSize;
+ w0 d$ e- W- g2 a7 ?8 I+ J    //-- variable ends) i8 E+ S% Y5 F: i
    void dfs( int);
& [7 G& X$ N* G$ W! c( L3 P7 C  U! l};& X- l. C- Y2 A0 @
//{ Variable-Annotation
! t0 _, x: R1 M! v  y// + @Var(Scc_id)* |1 o, w0 {4 y3 v
// . `y=Scc_id[x]` where `x` is a point of @Var(ptrRef_graph) and `y` belongs to `[0, @Func(Get_scc_count)-1]`% I) E& o9 r" f( p  h6 q
// + @Var(Scc_size)
4 H6 ]# e& m8 W// . `y=Scc_size[x]` where `x` belongs to `[0, @Func(Get_scc_count)-1]`, the sum of `Scc_size[0,1,...]` equals the points-count of @Var(ptrRef_graph)
5 R& U+ t# p5 X//} Variable-Annotation0 \  D: X- T( n- Q' M, y
template< class _Weight_Type> Tarjan_SCC< _Weight_Type>::Tarjan_SCC( const Graph< _Weight_Type> * _graph)$ w+ ^, d) Y3 W0 w4 s  \
        :) @' A# U3 S' j9 K6 m
        ptrRef_graph( _graph){5 e$ L- k) \2 V4 C3 [
    ptrNew_queue = new int[ ptrRef_graph->Get_pointsCountMaximum()];8 o0 W& H- Z" x# i
    ptrNew_isInQueue = new bool[ ptrRef_graph->Get_pointsCountMaximum()];0 N% w: ]( N+ P, B4 @& K
    ptrNew_sccId = new int[ ptrRef_graph->Get_pointsCountMaximum()];
8 @6 ~/ S% ]: S$ _4 P0 h& q: M    ptrNew_sccSize = new int[ ptrRef_graph->Get_pointsCountMaximum()];
' u) c* ^, q5 X, w0 B    //--
; l, J: M- m" o+ v( s3 f2 A    Scc_id = ptrNew_sccId;* S8 K% D6 z! A1 [" g
    Scc_size = ptrNew_sccSize;7 S# F+ I8 r& S- G# L' x
}3 ~+ h$ n7 t# _
template< class _Weight_Type> void Tarjan_SCC< _Weight_Type>::Initialize(){) D. c; ?; l7 v' J! r8 o
    queue_tail = 0;4 Q; I: F* C) ^0 d# M( ?) c$ c
    dfsOrderId_counter = 0;
) W( a1 i/ {0 s: d/ j* Z    memset( ptrNew_sccId, -1, sizeof( int) * ptrRef_graph->Get_pointsCount());
& }  I' p1 Z* x4 v( g2 m    scc_id_counter = 0;
7 V7 r0 G4 I& W! m0 b    for( int i = 0; i < ptrRef_graph->Get_pointsCount(); ++i){
. Q* Q  t8 f1 {; Z* E  D) Z        if( -1 == ptrNew_sccId[ i]){
: H0 d3 G6 A  d6 i: `, `# C            dfs( i);$ p* d5 l! q6 @' O* t  y( ?+ J
        }
/ l( r/ m! Y! V    }2 L% E1 Z" @( I3 L! B  [+ w( M
}- ?2 s* i' P( L. n4 ~' D
template< class _Weight_Type> const Graph< _Weight_Type> * Tarjan_SCC< _Weight_Type>::Build_DAG() const{
8 W- A- R- h4 R" Y//< + Make sure @Func(Initialize) has been called5 z3 z' M& f& {7 t$ V* k6 o3 L4 u
    Graph< _Weight_Type> * DAG = new Graph< _Weight_Type>( scc_id_counter, ptrRef_graph->Get_edgesCountMaximum());3 L4 d5 O! ?  A* p
    DAG->Initialize( scc_id_counter);
2 u6 x4 e7 Z4 t' ^    for( int a, b, i = 0; i < ptrRef_graph->Get_pointsCount(); ++i){
- y/ s- m3 r# p& w# V, }) `        for( int j, z = ptrRef_graph->Head[ i]; ~z; z = ptrRef_graph->Next[ z]){
6 \0 _$ [1 Q( C$ d3 F: p9 N8 ~, ^            j = ptrRef_graph->Vertex[ z];$ v* X! g- \7 G, [
            a = ptrNew_sccId[ i];
8 v4 d/ ^, J2 W1 U8 N            b = ptrNew_sccId[ j];
- T; y- g1 t: u0 ]# V            if( a != b){$ x0 f) A8 k. [& l8 D6 ~; M  w+ ?6 [
                DAG->Add_edge( ptrNew_sccId[ i], ptrNew_sccId[ j], ptrRef_graph->Weight[ z]);) A$ G* \( J% R9 g, y; \
            }! Q, S' p1 x: ?) a2 k
        }
3 n6 f0 @- P7 Q    }9 q( q. |7 v7 y+ z, F' z# C/ m" u  w
    return DAG;" q1 e  d( P7 m6 {
}) x! t! d* A- T% z0 H9 x6 o9 B. q5 B
template< class _Weight_Type> const Graph< _Weight_Type> * Tarjan_SCC< _Weight_Type>::Build_DAG_uniqueEdges() const{
; a& Q2 {0 H3 F0 e//< + Make sure @Func(Initialize) has been called. r* [' G; w7 T: F! T' p0 P9 ^
//< + There is at most one edge between any two points in the DAG (i.e., @Ret)
6 {, e: L! f! h2 }+ N' W    unordered_set< long long> hash_edges;+ n: m! B" ]3 T% m1 `0 O: v
    Graph< _Weight_Type> * DAG = new Graph< _Weight_Type>( scc_id_counter, ptrRef_graph->Get_edgesCountMaximum());0 G9 b: E  q! }- p) I
    DAG->Initialize( scc_id_counter);* R# [+ ?( |! q% G8 U
    for( int a, b, i = 0; i < ptrRef_graph->Get_pointsCount(); ++i){
. x# D. Q) t7 G        for( int j, z = ptrRef_graph->Head[ i]; ~z; z = ptrRef_graph->Next[ z]){
3 ]/ F- O: j* Y0 ~+ N' \, `% R            j = ptrRef_graph->Vertex[ z];
/ O6 K/ C$ P" y% t! m            a = ptrNew_sccId[ i];
6 ?. Y6 V3 E( Z% y            b = ptrNew_sccId[ j];
% K$ A7 ?# X1 }0 r' Z3 ?            if( a != b){
' P! y! r9 L: r3 }" l                long long hash_val = (long long)a * scc_id_counter + b;# z+ C7 @1 ?7 q6 B
                if( hash_edges.find( hash_val) != hash_edges.end()){
2 O: U7 O! T9 j% [                    continue;7 q' j/ V9 a2 O( L5 d0 X6 T# B9 q
                }
+ ^. s, R* d% ?" A" H1 o& l; ^3 [                hash_edges.insert( hash_val);1 w# J/ t" `4 a; ?: Y& E
                DAG->Add_edge( ptrNew_sccId[ i], ptrNew_sccId[ j], ptrRef_graph->Weight[ z]);0 O, y- G# B4 K. i$ X
            }. d7 |+ [/ M# H$ x2 T$ N
        }
, a/ y% Y0 j" v' ~    }0 ^6 ]$ [: B/ [" L
    return DAG;7 V9 @% C: s+ Y) q+ q# h9 }
}7 l8 e: h5 j) _* |' ?' d
template< class _Weight_Type> void Tarjan_SCC< _Weight_Type>::dfs( int _cur){
! ^  k6 T5 p$ F& F/ L4 b    ptrNew_queue[ queue_tail ++] = _cur;& N0 D6 T+ _, A! J: [
    ptrNew_isInQueue[ _cur] = true;) ^; L8 z' Q; A  E5 B* p
    int current_dfsOrderId = dfsOrderId_counter;
( `: ]) {  k6 }5 K4 r, p5 c# h    ptrNew_sccId[ _cur] = dfsOrderId_counter ++;/ O# \2 O' k: h
    //--& s+ c; O/ }3 c8 v1 I/ b7 r
    for( int nex, i = ptrRef_graph->Head[ _cur]; ~i; i = ptrRef_graph->Next[ i]){
7 u: s- R! Y2 P5 ?+ R        nex = ptrRef_graph->Vertex[ i];
! L" U4 @( l$ s- d7 U: O        if( -1 == ptrNew_sccId[ nex]){
3 }8 x& j# ]1 S# C$ F            dfs( nex);
* F' Z, r5 M) k3 m6 c4 z        }
( q; |$ y3 ]  L0 H        if( ptrNew_isInQueue[ nex]){
; X4 K9 @1 _) ^% U7 u( W5 r& D            ptrNew_sccId[ _cur] = min( ptrNew_sccId[ nex], ptrNew_sccId[ _cur]);, e( Z& f# w$ X! }0 ^& @0 Y! Z% H
        }  a& Y8 g0 {/ ^" I# L
    }
/ K( S: ~: _( Y" b# C    if( ptrNew_sccId[ _cur] == current_dfsOrderId){
( w8 w. N5 v6 m: T& {0 M        ptrNew_sccSize[ scc_id_counter] = 0;3 F) V6 U# M& z1 O" F
        while( true){8 t  b8 y6 i. M/ A3 y
            int c = ptrNew_queue[ queue_tail - 1];
% _  K. G. V3 u9 X            ptrNew_isInQueue[ c] = false;
& ~& j8 {- n3 y8 Y' T4 U            -- queue_tail;
. D- b- I3 }9 f            ptrNew_sccId[ c] = scc_id_counter;
- Y6 `9 _; F, h1 W3 X/ T& B1 K6 x            ++ ptrNew_sccSize[ scc_id_counter];
6 K2 U8 c' h) T            if( c == _cur){ break;}8 c* Z0 T2 G/ B) Y
        }6 @, Z( H* ^' \0 I9 Y
        ++ scc_id_counter;% A6 K; n) F" p: n  g2 J8 k. ?. f
    }
2 b8 E2 {; S4 S+ j* ^" x; L. @. F}; w4 q8 J' |) v7 |8 _- h
//} Tarjan_SCC! S- y" j" R3 [: J
, \% e) v3 z* }, e7 Y  H8 s: |
差分约束系统,不等式组7 @6 z5 H! E6 n* l
//{ Minimize_InequalitiesSystem* S$ o8 t7 W4 e7 c# T$ `) r7 N
template < typename _Edge_Type, typename _Distance_Type>
: h0 L2 y. [7 m& ~! Cclass Minimize_InequalitiesSystem{6 \& v( `, I. `! Y+ _/ Y, \1 a
public:
' R1 K  \/ B" c" y& K' }    const _Distance_Type * Distance;6 E" W; ~2 y/ |4 A4 b
    //-- variable ends; O' z8 n+ X1 A, y( Z
    Minimize_InequalitiesSystem( const Graph_Weighted< _Edge_Type> * _graph)8 n7 I8 v, R  R& w! N
            :- }0 d( ^% d9 M- u; L/ `1 d9 L
            ptrRef_graph( _graph){3 O3 R: J6 @/ J- ^0 _% H
        ptr_distance = new _Distance_Type[ ptrRef_graph->Get_pointsCountMaximum()];+ o0 `: @' p0 V9 U: }
        Distance = ptr_distance;
' @4 w3 ^! U  H% T6 k( H5 {, l        ptr_isInQueue = new bool[ ptrRef_graph->Get_pointsCountMaximum()];) p) @! d% m  h3 E0 c
        ptr_queue = new int[ ptrRef_graph->Get_pointsCountMaximum() + 1];, _0 \$ M+ ?% `8 d6 e6 K% w. c6 H2 z
        points_range = 0;. k8 u* @- C; q% \
        ptrNew_pathLength = new int[ ptrRef_graph->Get_pointsCountMaximum()];
$ G! l2 w5 V- i/ l1 d# A7 k        //--
4 ?" Z% i- x1 H! h  Y% d        Initialize();
- t0 d! r9 D( Y    }
9 q' ?/ s: n+ L( V* n    void Initialize(){  R' G4 C2 w; d. n9 D, S9 K3 J
        points_range = ptrRef_graph->Get_pointsCount();( T) I! ?& l: i, Q
    }* G. H) M- \  B0 v/ t3 ~
    bool Work(){' w% g: y; T0 a! D# a+ l$ l, e
        memset( ptr_distance, 0, sizeof( _Distance_Type) * points_range);
9 L0 u5 |  j! L7 p3 B6 X! @0 o8 p        memset( ptrNew_pathLength, 0, sizeof( int) * points_range);
) W! B$ p! S3 p" E8 H2 g4 d        for( int i = 0; i < points_range; ++i){, F4 Y, J( \' B& l
            ptr_queue[ i] = i;
2 P( R2 |0 e, J/ I' h$ e        }9 {$ U3 O! f- h- {
        memset( ptr_isInQueue, true, sizeof( bool) * points_range);( {. q; a7 X+ n. F1 c
        queue_head = 0;- Q. @" p; A& t! [. P8 K7 O4 Y
        queue_tail = points_range;
  D' R) }" N7 l% W5 _# J        //--( G4 Z, K: J' {1 m8 R" G
        int cur, nex, edge;) ^9 q; U4 R9 s; n  j
        while( queue_head != queue_tail){
! |4 b0 G. Y- @  K' w# W6 F) T            cur = ptr_queue[ queue_head ++];
( m+ @! J8 f8 s# \            ptr_isInQueue[ cur] = false;9 o9 T0 t: C  P
            if( queue_head > points_range){ queue_head = 0;}
6 t4 o: A- n7 ?) W! a  I            for( edge = ptrRef_graph->Head[ cur]; ~edge; edge = ptrRef_graph->Next[ edge]){
$ D" E& y1 _6 M, N3 s                nex = ptrRef_graph->Vertex[ edge];
  A+ O$ h+ W+ `( `                if( ptr_distance[ cur] + ptrRef_graph->Weight[ edge] > ptr_distance[ nex]){' t- q! P  g+ d. z7 z5 X5 R
                    ptrNew_pathLength[ nex] = ptrNew_pathLength[ cur] + 1;+ S% I# B! t9 E$ g2 e8 ]9 o- s
                    if( ptrNew_pathLength[ nex] >= points_range){
  ?* h( S  m8 t, _                        return false;5 ^1 N- S) w1 _
                    }
. o; N* Y' _4 r' x% |2 |                    ptr_distance[ nex] = ptr_distance[ cur] + ptrRef_graph->Weight[ edge];
9 ?1 ~; H( z. r0 r; ^* Q                    if( false == ptr_isInQueue[ nex]){
3 `: e6 @, G: ?7 ^                        ptr_isInQueue[ nex] = true;$ E# m' o$ o  ?( V. a
                        ptr_queue[ queue_tail ++] = nex;
2 S0 S. a& i2 c/ r4 B6 Y                        if( queue_tail > points_range){ queue_tail = 0;}9 q& `% X, J" G+ @3 M: l& i6 G
                    }
  s/ q; ]# E1 v# n8 `* g& n                }# t6 I3 Q) P" i! a
            }
1 n& _  d2 u- u/ p) H8 g1 D- v        }
" L+ A) B* b2 _4 q6 h8 {  Y        return true;
+ M7 v3 e$ P+ u. @* w3 i, W" I    }
! j# P. S# e: m/ V) nprivate:
( N  n4 u) w; `    const Graph_Weighted< _Edge_Type> * ptrRef_graph;: i2 s5 U, C9 Q7 U5 }: I8 b6 U
    int points_range;+ J  l) R! \1 {# n' D
    _Distance_Type * ptr_distance;
: A; |5 f) a2 u8 `    bool * ptr_isInQueue;
# ?1 B9 ^* R- E# K    int * ptr_queue;; K! d7 a/ u3 _- w, p* S5 b' z1 C
    int queue_head, queue_tail;
4 U, J( l! P& l( `4 @. _    int * ptrNew_pathLength;; h; ?- t& T: g0 [
};
" }5 n% A' s* d& j//} Minimize_InequalitiesSystem1 I. Z4 m7 [2 A5 }3 }, q; t
0 Q+ F3 M& g" h. E% y& h
Caution
: J% H  j- w2 P0 v" F2 M) D& u# H
+ m  N2 F- s( E! t5 p! w8 e% U`+` You should never modify the source-code of @Func( Work), otherwise, it means your algorithm must be erroneous.. J+ F2 t1 a1 h+ r. C
1
5 s8 y0 }% D* x* Z5 e5 g" O, j. VAnnotation/ ?; k0 [* f; ~

$ r: j! W2 r: r% w! ^3 B  l  e`+` @Func( Work)
! G& q; d& s2 G: }4 m$ t3 i`1` `@Ret = true` means the Inequality-System is Consistent, otherwise it is Inconsistent (No-Solution).0 u; J& Q: o( G6 B
`2` The effect of this function (if @Ret is true) is calculate the minimal-value for every variable (point) $xi$ Under-The-Condition-Of-All-Varible-Must-Be-`>=0`;
) g7 w$ b9 `% i9 l: Y$ M) J( G`.` In other words, under the premise `all variables xi >= 0`, minimize every variable and also satisfies all relations (i.e., the graph)9 r2 Y# X2 c3 b/ q# t* {0 s
% Y) k, |. }5 {; B# A
`+` @Var( ptrRef_graph)
! C. h4 h1 r3 I`.` A edge `x -> y` with `w` muse always means a inequality `x + w <= y` where `x,y` are both variables and `w` is a constant.
% B0 M. @! N6 T+ c! R; u
$ Q  r% V6 p5 h( W$ N- J- O数论& d8 z- X: a- S1 o; N( _
矩阵乘法% \8 B* G! f" E( n3 _
//{ MatrixMultiplication-Declaration+ N9 c/ }9 G; k. g  d- v
template< class _Type, int _MaximumLength>
! L1 y$ u, L- _4 W( x( Tclass MatrixMultiplication{
8 F0 B5 O2 O/ `) ?* X9 d5 [public:  y+ W' J- e' [. E  P
    MatrixMultiplication( _Type);
% X5 t9 T9 m3 \5 d! u" [" L- f    void Initialize( int, _Type (*)[ _MaximumLength], const _Type (*)[ _MaximumLength], const _Type (*)[ _MaximumLength][ _MaximumLength], long long);, }6 {5 v; v' ]1 V& `
private:
  z/ X: `4 w! z: V4 A    _Type modulus;7 ~4 M( L/ W7 |. J; F- x
    int length;
( Q3 n& n  \  s8 ]6 _    _Type factor[ _MaximumLength][ _MaximumLength];2 ~0 ]( D8 ~. }3 p  n; F. j
    _Type answer[ _MaximumLength][ _MaximumLength];
; p# U$ Z* k. t    _Type temp[ _MaximumLength][ _MaximumLength];' y0 ]/ X+ @' t2 R/ k9 w
    //-- variable ends
. c8 g1 J' |' V  t    void matrix_multiplication( _Type (*)[ _MaximumLength][ _MaximumLength], const _Type (*)[ _MaximumLength][ _MaximumLength], const _Type (*)[ _MaximumLength][ _MaximumLength]);* j1 f1 c" o9 z4 V8 M
};' ?" M) ~1 N  p% Z9 r/ w
//} MatrixMultiplication-Declaration
' l  @2 p4 w* d, T( u; }# ~' x/ d( M' `
//{ MatrixMultiplication-Implementation
* x  n* ^9 q  C6 Y7 rtemplate< class _Type, int _MaximumLength> MatrixMultiplication< _Type, _MaximumLength>::MatrixMultiplication( _Type _modulus)
* G7 G2 T3 s. ~        :
" }3 S$ E8 Z5 J' d6 ]1 `2 Y        modulus( _modulus){3 a/ O3 y2 P& a0 H
}
; [1 x( U$ j' I8 g% Ktemplate< class _Type, int _MaximumLength> void MatrixMultiplication< _Type, _MaximumLength>::Initialize( int _length, _Type (* _result)[ _MaximumLength], const _Type (* _dp)[ _MaximumLength], const _Type (* _factor)[ _MaximumLength][ _MaximumLength], long long _k){, `2 H5 s* g0 h8 W. r, Y2 i' F
//<
+ d' S$ l  d, x# K% v% _; E// @Brief
+ P6 O4 p, _! a" M// . `result = dp * (factor ^ k)`;
+ {; J, E; ~1 M' h% j7 h- z// @Warning
3 }) T. r# _+ i' m8 ~// . Make sure the data of `dp` is `dp[0, ..., _length)`, the data of `_factor` is `[ (0,0) -> (_length-1, _length-1) ]`;. ?- I7 S' G# {& g. r+ j
    ASSERT_( _k >= 0);+ q( ^8 x0 e* N* F4 K) v0 c  n# Y
    ASSERT_( _length <= _MaximumLength);
6 A/ I$ Y, l* i5 A    //----# Z- l/ k) D; E+ q# K2 `- H
    length = _length;1 ]9 V+ ~2 m. A5 e) X% p
    //--# u5 K% C, @, j; k4 p/ o
    memset( answer, 0, sizeof( answer));
$ W5 `3 D* P9 o4 l! Y5 J8 q    for( int i = 0; i < length; ++i){
. q9 K, a6 c9 i, P+ G2 ^        answer[ 0][ i] = (* _dp)[ i] % modulus;  if( answer[ 0][ i] < 0){ answer[ 0][ i] += modulus;}
% }# H: D3 S0 t1 L. U0 t( i    }
. B' L+ ?2 `2 b2 q5 ?4 L3 A: y    for( int i = 0; i < length; ++i){. a: |0 _- W/ N! r8 a
        for( int j = 0; j < length; ++j){0 ?7 |$ c8 {1 l6 }
            factor[ i][ j] = (* _factor)[ i][ j] % modulus;  if( factor[ i][ j] < 0){ factor[ i][ j] += modulus;}
! k8 g' P3 t8 q8 w        }  k0 s! g( a0 r; [
    }
6 Q" ]1 l+ f8 i9 s+ \8 ~% U. U    //--
9 A8 W' j7 B3 v( n    while( _k > 0){) ], l6 w! D9 x0 P. l
        if( _k & 1){6 y/ N2 H3 ]$ F
            matrix_multiplication( &answer, &answer, &factor);
; I: X# h4 |- l7 N) Y        }; x" M# T1 z# H3 X
        _k >>= 1;
: D0 k/ z# {0 A/ p( r- n        matrix_multiplication( &factor, &factor, &factor);- }8 I4 I: s/ k/ v  D0 x8 V
    }! ~! B! X. T1 M, m. s
    //--
" Y$ z3 `8 W+ M5 W; F$ n    memcpy( _result, answer[ 0], sizeof( _Type) * length); // the address of `_result` equals to the address of its first-element;
0 n: Z& n6 Z- W. _}/ c  E# {9 {7 v
template< class _Type, int _MaximumLength> void MatrixMultiplication< _Type, _MaximumLength>::matrix_multiplication( _Type ( * _result)[ _MaximumLength][ _MaximumLength], const _Type (* _a)[ _MaximumLength][ _MaximumLength], const _Type (* _b)[ _MaximumLength][ _MaximumLength]){
# H- U$ s; H+ S! |5 U//<
5 R/ E6 I# {  `' x' F' r! z" H: x+ G// @Brief$ s, n7 v# P. D" b$ a7 [: w
// . `result = a * b`;
+ `1 d( s& G) p5 R    for( int i = 0; i < length; ++i){4 b  a( B4 ^% Q8 W: O. z' L& c
        for( int j = 0; j < length; ++j){
- t7 z+ M! A& D9 i            //>> Cuz `result` maybe equals to `a/b`, you need store the result to `temp` not `result`;1 e7 M2 S% I/ Q: p
            temp[ i][ j] = 0;& W4 p1 k2 m3 W# h
            for( int z = 0; z < length; ++z){
5 v9 f; E8 D/ U* p- W                temp[ i][ j] += (long long)((* _a)[ i][ z]) * (* _b)[ z][ j] % modulus;  if( temp[ i][ j] >= modulus){ temp[ i][ j] -= modulus;}- I6 R5 r. M- q; ^& g
            }
% K$ _0 p# Z- |, x7 k9 E( P        }
: j9 y" v+ I+ k: M# N    }/ C. s! `4 ^2 C) I
    memcpy( _result, temp, sizeof( temp));# ~1 f7 O* v* X
}1 [$ x6 ?+ m# G) ?) ?
//} MatrixMultiplication-Implementation
/ F$ ?- g8 v$ w  G0 V# m3 Y3 k9 i* U; o1 |
@Delimiter5 b- S/ [; T$ Y% I+ `% W, a( P; g

7 \; w2 J9 N& H3 u' A/ ?2 j% l' L示例9 m  j- v) J0 q# E! j# \; ~# {
) H6 w. U/ k* j. m0 C' n
int Dp[ 4] = {1, 2, 2, 1};" {1 T# w# x1 f) \  ?, D
int A[ 4][ 4] = {{0,1,0,0}, {1,1,1,0}, {0,0,1,1}, {0,0,0,1}};
# E# B7 V2 g$ e! w5 Z" V2 @MatrixMultiplication< int, 4> Mat( M);* ^& S, O! t' M2 Y% N# |# Z# O  c
Mat.Initialize( 4, &Dp, &Dp, &A, N - 2);
& i1 \8 i" T  q7 k# R* @! _! \" A. a2 ^) H, h0 N2 z
long long ans = (long long)Dp[ 2] * N % M - Dp[ 3];$ B2 E4 |# |& Y/ E# U+ b0 U
cout<< ans;
  K7 r0 v* g1 {6 C: H1
  }7 h) c9 f4 S' Z1 O" s2: q1 f: @: Y! s
3
$ w. x- d+ k% w9 r  w& r1 t- E4( |! e" i* [* v
5
6 ~! K* ?0 D( v# Z6
/ r% m! N% @0 i% `9 T7
8 H9 \- {7 {6 t! [# r. Z% R1 j  q中国剩余定理8 B* ]: K0 R! _- M$ u
朴素 CRT0 r# f  N: J! z3 ^% f
//{ CRT-Declaration5 R9 }4 w8 o, f( F0 a7 l( J
template< class _Type> pair< long long, long long> CRT( int, const pair< _Type, _Type> *);9 @9 l  H" v* G, q
//} CRT-Declaration
7 d5 w8 U7 E0 A! ~; @: k. r  G+ }7 o% U- U
//{ CRT-Implementation
( `0 p5 K2 _6 X2 b2 ^' u) {template< class _Type> pair< long long, long long> CRT( int _n, const pair< _Type, _Type> * _arr){3 E+ P9 l; Z, ]1 S; [6 {
//<
1 g0 p* C& c; L2 i5 R8 H/ q// @Brief
  w- c9 ~! G  l) v1 k// . Solve the system of `n` Congruence-Equations represented by `arr` (i.e., `? = arr[i].first (% arr[i].second)`);
1 }+ x- @. ]" U  q0 F. X/ W# o//   . Once all `arr[?].second` are Pairwise-Coprime, this system must be Solvable (and Infinite-Solutions);* G& s! H( _/ Z- J# g  Z
//   . @Define( `(a,m)` = @Return), `a` must in the range [0, m), and the Solutons are $a + kk * m, \forall kk \in \Z$;2 p( c1 u# n2 O. B) F6 l( ^, `# j
// @Warning  W) T" i2 L  z) O* Z4 ]* s( W
// . Make sure all `arr[?].second` must be Pairwise-Coprime;
* \) p/ B" h2 t  C+ k4 L; e6 M- T" t// . Make sure the Product of all `arr[?].second` in the range `long long`;
& |0 g0 k$ b+ ^  Z, M// @TimeCost
$ r8 x( c9 r! k' Y// . $n * 60$;% |5 [0 F2 u* K: o
    long long M = 1;
, ^$ s3 l- q; [. M% m/ Q    for( int i = 0; i < _n; ++i){/ l9 `) F0 x4 N9 ?  A
        ASSERT_( _arr[ i].second >= 1);
. l) C+ R$ k) n  O+ s2 w        M *= _arr[ i].second;5 k% \. k+ O9 i1 n3 r, E5 W9 g  S
    }
8 x# Y8 c) n8 V# }1 b    long long answer = 0;
4 H+ X, K2 `5 o2 D2 [7 A8 t  G- t    for( int i = 0; i < _n; ++i){8 F0 C6 H, O8 k, }4 Q6 ~% N. J
        _Type a = _arr[ i].first % _arr[ i].second;  if( a < 0){ a += _arr[ i].second;}
; U+ Q6 t( N6 F6 Q        long long m = M / _arr[ i].second;. ~( l% S/ h" @) I0 Z: Z8 t
        pair< bool, pair< _Type, _Type> > ret = LCE_BezoutE< long long>( m, 1, _arr[ i].second); // m * `ret.second` = 1 (% _arr[ i].second);  e- p2 d" l7 `+ E( K
        ASSERT_( ret.first); // All `arr.second` are not Pairwise-Coprime which rebels the Premise-Of-This-Algorithm (See @Warning);& U* ?& B, p  L  z
        answer = (answer + (long long)a * m % M * ret.second.first % M) % M;2 l6 U$ z1 Q/ V/ i
    }
( z0 k" B, l$ W9 s1 K1 h- e    return {answer, M};
0 ~1 ~5 p& Q9 w% H! K  F}- y8 X1 q3 b" A* r; d. G; ^( _
//} CRT-Implementation8 `3 ?0 k& Q; j: A, _' Y0 |1 l

' D+ j/ `9 k/ S" k. W# d# q) ~- Q拓展 CRT_EX
, c* {4 i6 ]* s$ O' ]  [  ?7 _//{ CRT_EX-Declatation& z7 B0 d$ c: v7 t' ^: g2 @
template< class _Type> pair< bool, pair< long long, long long> > CRT_EX( int, const pair< _Type, _Type> *);
6 Z1 {% n( J5 x$ @- v+ P7 M//} CRT_EX-Declatation$ |2 v7 k& b3 p1 y, ]+ N1 m. `
, c) \% ^3 G. z' d5 ^4 Z
//{ CRT_EX-Implementation/ z" C: c3 d' H2 z! q; }6 h
template< class _Type> pair< bool, pair< long long, long long> > CRT_EX( int _n, const pair< _Type, _Type> * _arr){
0 N  J! h: H$ |//<# S& I/ `0 B) D; ?- n, Z
// @Brief
' w2 Z* l( T: {" w- r) W6 @2 j// . Solve the system of `n` Congruence-Equations represented by `arr` (i.e., `? = arr[i].first (% arr[i].second)`);
) n( K  I8 C! K6 O' }5 P//   . @Define( `(r1, (r2,r3))` = @Return);' W, z* z0 x7 L9 W
//     0( r1=false): There is No-Solution;
0 q1 l& m/ V0 K5 D& [* }8 B//     1( ELSE): The Solutons are `r2 + kk * r3, $\forall kk \in \Z$`, and `r2` must in the range [0, r3);
' v: E4 Z( x4 `- g//   . All `arr[?].second` maybe not Pairwise-Coprime (which differs from `CRT`);
; N1 m8 q5 x6 h/ I& M6 e3 _8 D// @Warning) \* |, ~+ }4 Y, r8 |& Z9 n0 p* n: J
// . Make sure the LCM (Least-Common-Multiple) of all `arr[?].second` in the range `long long`;% ]8 O) K* f9 M: e: P- d
// @TimeCost
9 l/ s! E# z5 H/ Y// . $n * 60$;- H9 R3 ]( V" v) l
    pair< bool, pair< long long, long long> > answer;
; m: W% O5 D9 p' a6 Z    long long A, M;! M/ \. o- W% n0 W+ p; u
    for( int i = 0; i < _n; ++i){
( @  |$ d! n% u( l        _Type a = _arr[ i].first;
5 ?" C( ?/ _4 S3 ?        a %= _arr[ i].second;  if( a < 0){ a += _arr[ i].second;}
7 C( p6 k" D- g/ r3 B        //--
+ w. x" c8 K# n% E9 q        if( i == 0){
6 w1 F* S- e3 H- r& C5 U! E  o* ]            A = a, M = _arr[ i].second;' x, D. N. Q( W1 j5 Y9 o
            continue;
9 B  P5 `9 v8 ^! T. I* `        }
4 ?0 E! w% e( f1 o* B1 j        pair< bool, pair< _Type, _Type> > ret = LCE_BezoutE< long long>( M, a - A, _arr[ i].second);" o8 T' o) N% N  c2 P
        if( false == ret.first){
( L- p; n- T# ?  m7 p  \+ X7 {. {            answer.first = false;
; d- z" g0 D5 @9 _- @& K4 I            return answer;
% ]* j# E: L' G: j( m* h( }        }9 d: O$ M0 p1 J0 {
        _Type gcd = _arr[ i].second / ret.second.second;  if( gcd < 0){ gcd = -gcd;} // The GCD of `M` and `_arr[i].second`;- ^4 L& w; M& o: J2 O4 s/ U0 h: i# B
        long long new_M = M / gcd * _arr[ i].second; // LCM3 N. @* G) p; e8 `# `2 k: D6 q$ k
        A = (A + ret.second.first * M % new_M) % new_M;
$ H2 y- M; n- u" r) T6 K  _        M = new_M;
9 \+ R3 x* M: t* I1 j4 [    }
# B9 b$ M0 G( z- V+ Y    answer.first = true;) _& l1 H" }( v  M: W9 Y
    answer.second.first = A;8 s* }% c# _( B4 g$ i
    answer.second.second = M;
: d8 X5 n% g4 C9 X  W    return answer;
- m6 i- ]" R6 @( I}- X( K/ P3 e/ ]% w; q) p% \1 n  J
//} CRT_EX-Implementation' Y9 O5 C' j$ F2 `9 D" q' M0 [' {" \8 n
1$ i( i+ X7 u' q5 u; i
裴蜀方程 BezoutE% D8 K- ]4 w2 p  W. g5 ~
//{ BezoutE-Declaration  A( o* l& f- p5 |9 H; g
template< class _Type> pair< bool, pair< pair< long long, _Type>, pair< long long, _Type> > > BezoutE( _Type _a, _Type _b, _Type _c);
6 y8 @3 O- q5 U% S; z//} BezoutE-Declaration
7 m: P6 M6 }( k- f! L7 i' ?. N) b& {$ h
//{ BezoutE-Implementation
' \0 D% f$ a' l% D2 B+ Utemplate< class _Type> pair< _Type, pair< long long, long long> > BezoutE_extendedGCD( _Type _a, _Type _b){
( K; h$ M0 l$ V//<  B& S7 Q$ M2 |/ ?
// @Private5 i5 b" }4 J7 X  o% L8 l+ X
// @Warning% y  Q$ @. F' N' V4 \/ _
// . Make sure `a,b >= 0`, Not-Both-Be-`0`;
/ G% f' v" c4 M- X# {8 i    if( _b == 0){# `# \1 [0 ~% }: U$ P
        return {_a, {1, 0}};
  a+ H( x8 i9 d5 ~    }! O- z9 }" v3 y7 W; H- K
    auto pre = BezoutE_extendedGCD( _b, _a % _b);. |& f8 \) Y1 V* @# b
    auto xp = pre.second.first;: D! F) U1 w0 P& V( |
    auto yp = pre.second.second;+ a) ]. Q. h( m. H
    return {pre.first, {yp, xp - yp * ( _a / _b)}};2 A# a" Z0 }) y2 j: Z* E0 m
};/ ^( N' [8 @9 `( O1 O3 N
template< class _Type> pair< bool, pair< pair< long long, _Type>, pair< long long, _Type> > > BezoutE( _Type _a, _Type _b, _Type _c){
% e3 I0 V& j8 K( u( s3 v* w//<
6 C! T2 L  b; f  ~' e) |// @Brief
; s" Q7 H+ j; |. f. m3 [/ w% l// . Solve the equation `xx * a + yy * b = c`, @Define( `(r1, ((a1,m1), (a2,m2)))` = @Return)`;1 H% X2 B4 i) x6 J; I4 @! n
//   0( r1=false): There is no Solution;- ~3 f! U2 j3 ^! n- L0 Y; y
//   1( ELSE): The General-Solutions are `(a1 + k * m1, a2 - k * m2) $\forall k \in \Z$`;
- v  `8 B( ^+ Z. a// @TimeCost
3 f$ n2 F0 `' G' R6 k2 }3 A1 f// . $\ln(a)$;
# K; f* P$ j, ~3 G! B' k// @Warning& E) t: p2 P+ w( v
// . Make sure `a != 0`, `b != 0`;, {! G4 C: L" s: o4 O& ~3 o) t$ i
    ASSERT_( (_a != 0) && (_b != 0));
$ h, d5 U! ^0 f    pair< bool, pair< pair< long long, _Type>, pair< long long, _Type> > > answer;
2 X3 ^  w5 k  [# M+ e% z* s+ f% |( C    bool neg_a = false, neg_b = false;$ O7 e4 A# m9 U# |' T
    if( _a < 0){ neg_a = true;  _a = -_a;} // `x * a + y * b = c` -> `(-x) * (-a) + y * b = c`;
: w4 e* m3 y1 X) C    if( _b < 0){ neg_b = true;  _b = -_b;} // `x * a + y * b = c` -> `x * a + (-y) * (-b) = c`;
/ Z& @0 t! K0 g3 Z    //--1 Q2 n3 c" K7 f6 x
    pair< _Type, pair< long long, long long> > ret = BezoutE_extendedGCD( _a, _b);% ?& ]$ ^8 @" {  T
    if( _c % ret.first != 0){4 F2 x/ o3 c  j: m% a
        answer.first = false;
; \2 J# g1 g$ |3 ]- m- s        return answer;% x$ y& t" ?" i6 f* `% s
    }  n% Z/ h( a3 h6 j
    answer.first = true;" m5 U/ x3 W( w, v! |& B
    answer.second.first.first = ret.second.first * (_c / ret.first);
# ]# W1 x" k: ~5 n    answer.second.first.second = _b / ret.first;
. r' Q4 i2 @- D! o' o+ Z+ B  ^    answer.second.second.first = ret.second.second * (_c / ret.first);- q5 \* Z& ?" x) W5 x9 o) I& h
    answer.second.second.second = _a / ret.first;: |; o  `3 `- z: O
    if( neg_a){ answer.second.first.first = -answer.second.first.first;}
2 c6 Z+ h5 ]% A4 V    if( neg_b){ answer.second.second.first = -answer.second.second.first;}
* x5 c( q: g1 J; {: N& U    return answer;1 H8 v! s. w- N: d1 `7 ?# ~( l
}& [* V" p$ p5 Z- p) l; i) E$ n! W
//} BezoutE-Implementation
  P5 w8 D  p1 e# k' M/ s- o6 y) y6 s8 |6 ^. q7 y
线性同余方程 LCE2 b2 d# ?- [* @8 H; A; R
裴蜀方程法 LCE_BezoutE
) y# o4 L. p4 D, E" M0 t7 D//{ LCE_BezoutE-Declaration5 O5 K8 u' P+ k. z5 V( D6 m
template< class _Type> pair< bool, pair< _Type, _Type> > LCE_BezoutE( _Type _a, _Type _b, _Type _mod);
' t  b! x9 F" |//} LCE_BezoutE-Declaration
& l, ~6 o9 t* b" Q; g/ S
+ d* r6 S8 `. ?1 e2 s6 R//{ LCE_BezoutE-Implementation
% K! P, J& T* Z0 Ftemplate< class _Type> pair< bool, pair< _Type, _Type> > LCE_BezoutE( _Type _a, _Type _b, _Type _mod){
4 T9 |" r' s5 W7 x//<6 s+ C4 o# Q# h  j- p) w0 K
// @Brief+ b* Y, U( s. K; T( i
// . Solve the Congruen-Equation `a * ? = b (% mod)` where `?` is @Return; @Define( `(r1, (a1,m1))` = @Return);+ \9 I0 ~* r* R! S, s2 W8 Y
//   0( r1=false): There is No-Solution;3 E4 D2 a- k/ `+ H8 \+ C" O3 h
//   1( ELSE): The General-Solutions are `a1 + k * m1, $\forall k \in \Z$`, and `a1` always in the range [0, m);+ w2 ~7 [+ b. _
// @TimeCost. O! U/ {! M" X/ @
// . $\ln(_a)$;
/ G' J# N% v% I1 v! k    ASSERT_( _mod >= 1);+ Q! p. }! F% _* I6 s0 {
    pair< bool, pair< _Type, _Type> > answer;$ k& r1 S7 l! c' x" b- E& ^; h
    _a %= _mod;  if( _a < 0){ _a += _mod;}8 a; G, m7 J1 d9 N
    _b %= _mod;  if( _b < 0){ _b += _mod;}
9 ]; j/ G8 X% ~, I8 A    if( _a == 0){$ b, d! R) b$ H2 e
        if( _b == 0){* F1 }* O# b0 ^$ o# N7 k5 W
            answer.first = true;
  n5 v" s) N* n" p9 m# n! G7 R0 s            answer.second.first = 0;
% G6 f  u( P4 ?            answer.second.second = 1;: x5 L: p8 A( C, m0 A# X
            return answer;7 N% {& r# G9 d: s
        }
  c. Q4 G* \$ k4 g: H) y0 Q        else{' n' c/ a( x5 \# g
            answer.first = false;4 ?8 E/ \) K+ M1 G* ]# N
            return answer;+ G& @: Z; H, m& M# o! D
        }
3 x0 M: v8 {% a# m) N6 Z8 E    }
  d2 h" c  |$ S6 U    _Type gcd = GCD< _Type>( _a, _mod);8 t9 S  v) S3 e  ]. A
    pair< bool, pair< pair< long long, _Type>, pair< long long, _Type> > > ret = BezoutE< _Type>( _a, _mod, gcd);6 H0 d" q; \. A. k* \" [) t! a2 x
    ASSERT_( ret.first);
! J8 q8 W+ A5 E    if( _b % gcd != 0){' M# w7 W7 O1 X! [/ a* q
        answer.first = false;9 ]4 S, V9 w; d; ^# ]
        return answer;) R1 M" ~. O7 c( S* q6 G
    }% `' [8 i) @- C. m
    answer.second.second = _mod / gcd;+ C0 B: I5 {' W4 D4 M
    answer.second.first = Binary_Multiplication< _Type>( ret.second.first.first, _b / gcd, answer.second.second);$ [: P  w" u) m
    answer.first = true;
; ]7 J( U9 W, w, @# ]" Q4 f    return answer;: `: y- a# ?! D, j% Z" n& l) |5 o
}5 V% B; C/ [  z$ Q- M/ G5 y
//} LCE_BezoutE-Implementation
2 K: O) _# T, z2 ~- V& |& P) i( `! w6 v  D8 Q" Q$ n  x, R: Y
高斯消元线性方程组
8 I; J8 ^+ o; A( m# B5 V- [' A//{ Gaussian elimination
4 @: S6 h/ Z+ T* E  Sdouble Aug[ 105][ 105]; //< @Abbr( augmented matrix)
4 M2 v0 X. i. A+ v) v$ [1 N. n6 Rint Gaussian_elimination( int _m, int _n){+ {) V4 S& ^7 }4 r& b
//< @Par( _m): the number of equations
1 x# i9 P  v# a' f//< @Par( _n): the number of variables0 ?0 k* N6 w: K  }, z& P. s4 V
//< @Return: (0 is unique solution), (1 is infinitely many), (-1 is no solution)) L* B2 P9 @) r% a7 w
    int rank = 0;9 K& k8 @' C1 \! I8 c& t7 N9 y! Z6 b
    for( int col = 0; ( col < _n) && ( rank < _m); ++col){+ e! S$ T: P0 J8 W1 F" Q* d- L7 k( l
        int max_row = rank;
. b" `, ?9 p# Z1 S$ W: f        for( int row = rank + 1; row < _m; ++row){
  y1 Z8 k8 l/ V! Y! D; G* a            if( fabs( Aug[ row][ col]) > fabs( Aug[ max_row][ col])){. G! O- v) \7 Q) i
                max_row = row;
# Q4 Z/ b6 Z$ K% r            }
4 R4 C' K" k: q, }2 j        }* f% n, w( ~6 j$ I
        if( 0 == Db_cmp( fabs( Aug[ max_row][ col]), 0, Epsilon)){
3 K/ u) s3 C$ b* A$ I! |, w            //* either no solution, or infinitely many.
# ?1 q# `" X1 _  t0 }; E            continue;; d) K2 W' x9 ^! L* x
        }
" z. x4 Q6 r8 W3 R  @        //{ swap two rows& U7 `+ w0 B/ M+ t! P0 c* u
        for( int c = 0; c < _n + 1; ++c){% _# I* D& x; R" |- C1 p, ^. G
            swap( Aug[ max_row][ c], Aug[ rank][ c]);
4 f; y6 O$ }3 W; u8 |4 f        }  Z. O4 Q2 ^, L* O( [9 {+ c: r1 u
        //}7 f0 s1 z7 [6 x
        //{ make current pivot to `1`
. \# ~& I9 L$ N" V* L$ v        for( int c = _n; c > col; --c){
  J: c$ C0 u) B' b( N4 ^) b. O            Aug[ rank][ c] /= Aug[ rank][ col];2 L9 B' K1 e% U2 o. d
        }( T2 w2 \* K0 J
        Aug[ rank][ col] = 1;2 p! c8 {6 O# H4 m% r6 c- M
        //}% m/ j# T; {7 h$ }1 }
        //{ make all rows below current pivot in the same column to `0`: ^& _+ J4 p) n1 F
        for( int r = rank + 1; r < _m; ++r){5 c9 N( y" C  M9 E: I
            if( 0 == Db_cmp( fabs( Aug[ r][ col]), 0, Epsilon)){
2 m  A- c7 U( j5 R5 w' C$ J                continue;+ b1 ^% ^5 o( `% h! t) I
            }
' e7 @& Z9 R- y/ k            for( int c = _n; c > col; --c){
$ _5 [- P" I* U) l+ [& {% h$ J                Aug[ r][ c] -= Aug[ r][ col] * Aug[ rank][ c];0 o0 |0 h8 L+ J( _8 ^( W
            }
3 t/ H. y! L2 n3 b" Q            Aug[ r][ col] = 0;
9 \4 E- d; ?) @$ e# A- x& w* l        }+ ~/ f& a+ R4 X4 o7 E
        ++ rank;
* O5 t; `/ b1 r& {( d    }" B. K1 P3 v' e5 ?# ~0 Q4 d0 S
    //--
2 S/ T# s' ]' ?- i3 S    for( int r = rank; r < _m; ++r){
0 g! K4 }  K8 w' C! \) M. `. A        if( 0 != Db_cmp( Aug[ r][ _n], 0, Epsilon)){
' l; p7 f& e" t  H) d            return -1;% I2 s5 E: g! E9 Y6 N& c3 C! |8 |
        }0 k8 g1 j4 Y, P* v8 p/ ]  F
    }' P# K  D( J# ^9 T2 z8 `
    if( rank != n){
3 k& T* ~* c2 y! [6 b        return 1;! B" s9 w" a$ W% T& Q% g' ]0 }
    }# e5 a: ?" t+ k" k7 @" y
    //> the upper-left `_n * _n` submatrix of `Aug` is a identity-matrix
3 ^  E. m3 L  W3 X: Y    for( int r = rank - 1; r > 0; --r){2 i  V% R* ~4 c7 n0 g5 }% q
        for( int rr = 0; rr < r; ++rr){
' u& D* N( [. H! D            if( 0 == Db_cmp( Aug[ rr][ r], 0, Epsilon)){  o- G9 C* x7 T) [% I6 A
                continue;* q# s( e) f! j0 _
            }$ R, P2 G5 n) U3 g& `' }
            Aug[ rr][ _n] -= Aug[ rr][ r] * Aug[ r][ _n];
+ @4 m; g- C" O2 @( T' ]            Aug[ rr][ r] = 0;
7 `. c8 P2 [# O7 W        }
  y/ ?+ @: _9 B5 q    }/ m: k# }2 j* r: A0 ?
    return 0;
8 Y+ e' N9 L- o; P! S}
; [* k0 m" v5 p. |% h% U0 V//} Gaussian elimination
- \9 Q) w9 v3 |' d9 Z
1 [) L7 ~8 E4 a/ G1 l6 K$ W" L. g2 X3 H! R4 g
您需要登录后才可以回帖 登录 | 注册

本版积分规则

返回首页|Archiver|手机版|小黑屋|易陆发现技术论坛 ( 蜀ICP备2026014127号-1 )

GMT+8, 2026-6-11 22:17 , Processed in 0.028463 second(s), 22 queries .

Powered by Discuz! X5.0

© 2001-2026 Discuz! Team.

快速回复 返回顶部 返回列表