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

admin · 发表于 2025-3-21 10:23:44

算法 {算法代码模板,算法模板编写规范}
supimoTemplate.cpp
代码
#define  ___SUPIMOenvir_

#include <bits/stdc++.h>
using namespace ::std;

#ifdef  ___SUPIMOenvir_
#include "supimoDebug.hpp"
#else
#define  TOstringITEMS_( ...)  ""
#define  DE_( ...)
#define  ASSERTcustom_( _op, ...) assert(_op)
#define  ASSERTsystem_( _op, ...) assert(_op)
#endif

#define  ASSERTregion_( ...)  __VA_ARGS__
#define  ASSERTsentence_( ...)
#define  EXIT_  std::cerr<< "\nExit(2267): Line("<< __LINE__<< ")\n";  std::exit(2267);
#define  EXITcounter_( _max)  { static int cont = 0; ++ cont; if( cont == _max){ string str = "Exit_Counter(" + std::to_string(_max) + ")"; DE_(str); EXIT_;}}
#define  FOR_( _i, _l, _r)  for( int _i=int(_l); _i<=int(_r); ++_i)
#define  FORrev_( _i, _l, _r)  for( int _i=int(_l); _i>=int(_r); --_i)

using Int64_ = long long;

void ___Solve_oneTest(){
}
void ___GlobalInitialze(){
}
int main(){
std::ios::sync_with_stdio(0);  std::cin.tie(0);
std::cerr.setf( std::ios::fixed);  std::cerr.precision( 9);
std::cout.setf( std::ios::fixed);  std::cout.precision( 9);

auto ___Solve = [](){ // Problem-Input
      constexpr char MODEisSINGLE = 1;
      int testsCount;
      if( MODEisSINGLE){ testsCount = 1;} else{ cin>> testsCount;}
      for( int id = 0; id < testsCount; ++id){
         if( id == 0){ ___GlobalInitialze();}
         ___Solve_oneTest();
      }
};
#ifdef  ___SUPIMOenvir_
while( 1){
      std::string flag;  std::cin>> flag;  ASSERTsystem_( flag.substr( 0, 10) == "#___Input[", flag);
      flag.replace( 4, 2, "Out");
      std::cout<< " "<< flag<< "\n";  std::cerr<< " "<< flag<< "\n";
      if( flag == "#___Output[-1]#"){ break;}
//       int timeStart = std::clock();
      ___Solve();
      std::cout<< "\n";  std::cerr<< "\n";
//       std::cout<< "TimeElapsed: "<< std::clock() - timeStart<< "\n";
}
#else
___Solve();
#endif

return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
supimoDebug.hpp
代码
#include <bits/stdc++.h>

#define  VARSandLOCATION_( ...)  std::string(std::string("{File: ")+ __FILE__+ ", Line: "+ std::to_string(__LINE__)+ ", VarName: ["+ #__VA_ARGS__+ "]}")
#define  TOstringITEMS_( ...)  ___DEBUG_::ToString_Items( __VA_ARGS__)
#define  DE_( ...)  std::cerr<< TOstringITEMS_( __VA_ARGS__)<< " "<< VARSandLOCATION_(__VA__ARGS__)<< "\n"
#define  ASSERTcustom_( _op, ...) if( !bool(_op)){ std::cerr<<"Assertion_Failed(Custom): ["<< #_op<< "] {Hint: ["<< TOstringITEMS_( __VA_ARGS__)<< "]("<< #__VA_ARGS__<< ");  Line: "<< __LINE__<< "}";  std::exit(2267);}
#define  ASSERTsystem_( _op, ...) if( !bool(_op)){ std::cerr<<"Assertion_Failed(System): ["<< #_op<< "] {Hint: ["<< TOstringITEMS_( __VA_ARGS__)<< "]("<< #__VA_ARGS__<< ");  Line: "<< __LINE__<< "}";  std::exit(2267);}

namespace ___DEBUG_ {
//>> 所谓`Container`是指可以通过`for( auto i : S)`来进行遍历的;
template< class _t> struct __IsContainer_Unwrap : std::false_type{};
template< class _t> struct __IsContainer_Unwrap<std::vector<_t> > : std::true_type{};
template< class _t> struct __IsContainer_Unwrap<std::set<_t> > : std::true_type{};
template< class _t> struct __IsContainer_Unwrap<std::unordered_set<_t> > : std::true_type{};
template< class _t> struct __IsContainer_Unwrap<std::multiset<_t> > : std::true_type{};
template< class _t> struct __IsContainer_Unwrap<std::unordered_multiset<_t> > : std::true_type{};
template< class _t0, class _t1> struct __IsContainer_Unwrap<std::map<_t0,_t1> > : std::true_type{};
template< class _t0, class _t1> struct __IsContainer_Unwrap<std::unordered_map<_t0,_t1> > : std::true_type{};
template< class _t0, int _t1> struct __IsContainer_Unwrap< _t0[_t1] > : std::true_type{};
template< int _t1> struct __IsContainer_Unwrap< char[_t1] > : std::false_type{}; // 特判，字符串常量"..."不属于容器；
template< class _t> struct IsContainer : __IsContainer_Unwrap<std::remove_const_t<std::remove_reference_t<_t> > >{}; // 不能用`decay` 否则`T[N]`就退化为`T*`了；

template< class _t> struct __IsPair_Unwrap : std::false_type{};
template< class _t0, class _t1> struct __IsPair_Unwrap< std::pair<_t0,_t1> > : std::true_type{};
template< class _T> struct IsPair : __IsPair_Unwrap< std::decay_t<_T> >{};

template< class _t> struct __IsStack_Unwrap : std::false_type{};
template< class _t> struct __IsStack_Unwrap< std::stack<_t> > : std::true_type{};
template< class _T> struct IsStack : __IsStack_Unwrap< std::decay_t<_T> >{};

template< class _t> struct __IsQueue_Unwrap : std::false_type{};
template< class _t> struct __IsQueue_Unwrap< std::queue<_t> > : std::true_type{};
template< class _T> struct IsQueue : __IsQueue_Unwrap< std::decay_t<_T> >{};

template< class _t> struct __IsDeque_Unwrap : std::false_type{};
template< class _t> struct __IsDeque_Unwrap< std::deque<_t> > : std::true_type{};
template< class _T> struct IsDeque : __IsDeque_Unwrap< std::decay_t<_T> >{};

template< class _T> std::string ToString( _T const&);

template< class _T, int _Check> struct __ToString_Category;
template< class _T> struct __ToString_Category<_T, 0>{ // Single
template< class _t> static std::string TOstring( _t const& _v){
      std::ostringstream ANS; ANS.precision( std::cout.precision()); ANS.setf(std::cout.flags()); ANS<<_v;
      return ANS.str();
}
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;}
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;}
static std::string TOstring( bool const& _b){ return (_b?"1":"0");}
static std::string TOstring( char const& _a){
      if(_a==0){ return "'\\0'";} // 否则因为她是*结束控制符* 会导致`ostream<<char(0)<<A;`后面的`A`不输出了;
      std::string ANS="'?'"; ANS[1]=_a; return ANS;
}
static std::string TOstring( char const* const& _s){ return std::string(_s);}
static std::string TOstring( std::string const& _tt){ std::string ANS="\""; ANS+=_tt; ANS+='\"'; return ANS;}
};
template< class _T> struct __ToString_Category<_T, 1>{ // Container
      template< class _t> static std::string TOstring( _t const& _v){
         std::string ANS="["; bool first=1;
         for( auto const& i : _v){ if( 0==first) ANS+=","; if( first) first=0; ANS+=ToString(i);}
         ANS+="]";
         return ANS;
      }
};
template< class _T> struct __ToString_Category<_T, 2>{ // Pair
      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;}
};
template< class _T> struct __ToString_Category<_T, 3>{ // Stack
      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;}
};
template< class _T> struct __ToString_Category<_T, 4>{ // Queue
      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;}
};
template< class _T> struct __ToString_Category<_T, 5>{ // Deque
      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;}
};

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)))))>{};

template< class _t> std::string ToString( _t const& _v){ return __ToString<_t>::TOstring(_v);}

template< class... _H_> std::string ToString_Items( _H_ const&...){ return "";}
template< class _H_> std::string ToString_Items( _H_ const& _h){ return ToString(_h);}
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;}
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
性质
#TOstringITEMS_#
这个宏是为了: 对类进行输出时可以直接_cout<< TOstringITEMS_(成员变量...);
你可能认为, 直接_cout<< ___Debug_::ToStringItems(...)不就行了?
. 错误, 因为在最终文件里是看不见___Debug_的, 所以写成一个宏在最终文件里 #define TOstringITEMS_ "";

笔记
#以前的debug.hpp#

//{ omipusDebug.hpp
#include <bits/stdc++.h>

#define  TOstringITEMS_( ...)  ___DEBUG_::ToString_Items( __VA_ARGS__)
#define  DE_( ...)  std::cerr<< TOstringITEMS_( __VA_ARGS__)<< " "<< "{"<< "Line: "<< std::to_string(__LINE__)<< ", Var: ["<< (#__VA_ARGS__)<< "]"<< "}"<< "\n"
#define  ASSERT_( _op, ...) if( !bool(_op)){ std::cerr<<"Assertion: ["<< #_op<< "] {Info: ["<< TOstringITEMS_( __VA_ARGS__)<< "]("<< #__VA_ARGS__<< ");  Line: "<< __LINE__<< "}";  std::exit(2267);}
#define  ASSERTsystem_( _op, ...) if( !bool(_op)){ std::cerr<<"Assertion(System): ["<< #_op<< "] {Info: ["<< TOstringITEMS_( __VA_ARGS__)<< "]("<< #__VA_ARGS__<< ");  Line: "<< __LINE__<< "}";  std::exit(2267);}

namespace ___DEBUG_ {
template< class _t> struct __IsContainer_Unwrap : std::false_type{};  // 所谓`Container`是指可以通过`for( auto i : S)`来进行遍历的;
template< class _t> struct __IsContainer_Unwrap<std::vector<_t> > : std::true_type{};
template< class _t> struct __IsContainer_Unwrap<std::set<_t> > : std::true_type{};
template< class _t> struct __IsContainer_Unwrap<std::unordered_set<_t> > : std::true_type{};
template< class _t> struct __IsContainer_Unwrap<std::multiset<_t> > : std::true_type{};
template< class _t> struct __IsContainer_Unwrap<std::unordered_multiset<_t> > : std::true_type{};
template< class _t0, class _t1> struct __IsContainer_Unwrap<std::map<_t0,_t1> > : std::true_type{};
template< class _t0, class _t1> struct __IsContainer_Unwrap<std::unordered_map<_t0,_t1> > : std::true_type{};
template< class _t0, std::size_t _t1> struct __IsContainer_Unwrap< _t0[_t1] > : std::true_type{};
template< std::size_t _t1> struct __IsContainer_Unwrap< char[_t1] > : std::false_type{}; // 特判，字符串常量"..."不属于容器；
template< class _t, std::size_t _siz> struct __IsContainer_Unwrap<std::array<_t,_siz> > : std::true_type{};
template< class _t> struct IsContainer : __IsContainer_Unwrap<std::remove_const_t<std::remove_reference_t<_t> > >{}; // 不能用`decay` 否则`T[N]`就退化为`T*`了；

template< class _t> struct __IsPair_Unwrap : std::false_type{};
template< class _t0, class _t1> struct __IsPair_Unwrap< std::pair<_t0,_t1> > : std::true_type{};
template< class _T> struct IsPair : __IsPair_Unwrap< std::decay_t<_T> >{};

template< class _t> struct __IsStack_Unwrap : std::false_type{};
template< class _t> struct __IsStack_Unwrap< std::stack<_t> > : std::true_type{};
template< class _T> struct IsStack : __IsStack_Unwrap< std::decay_t<_T> >{};

template< class _t> struct __IsQueue_Unwrap : std::false_type{};
template< class _t> struct __IsQueue_Unwrap< std::queue<_t> > : std::true_type{};
template< class _T> struct IsQueue : __IsQueue_Unwrap< std::decay_t<_T> >{};

template< class _t> struct __IsDeque_Unwrap : std::false_type{};
template< class _t> struct __IsDeque_Unwrap< std::deque<_t> > : std::true_type{};
template< class _T> struct IsDeque : __IsDeque_Unwrap< std::decay_t<_T> >{};

template< class _T> std::string ToString( _T const&);

template< class _T, int _Check> struct __ToString_Category;
template< class _T> struct __ToString_Category<_T, 0>{ // Single
      template< class _t> static std::string TOstring( _t const& _v){
         std::ostringstream ANS; ANS.precision( std::cout.precision()); ANS.setf(std::cout.flags()); ANS<<_v;
         return ANS.str();
      }
      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;}
      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;}
      static std::string TOstring( bool const& _b){ return (_b?"1":"0");}
      static std::string TOstring( char const& _a){
         std::string ANS="'?'";
         ANS.replace( 1, 1, std::to_string(_a));
         return ANS;
      }
      static std::string TOstring( char const* const& _s){ return TOstring(std::string(_s));}
      static std::string TOstring( std::string const& _s){ std::string ANS="\""; ANS+=_s; ANS+='\"'; return ANS;}
};
template< class _T> struct __ToString_Category<_T, 1>{ // Container
      template< class _t> static std::string TOstring( _t const& _v){
         std::string ANS="[";  bool first=1;  for( auto const& i : _v){ if( 0==first) ANS+=","; if( first) first=0; ANS+=ToString(i);}  ANS+="]";
         return ANS;
      }
};
template< class _T> struct __ToString_Category<_T, 2>{ // Pair
      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;}
};
template< class _T> struct __ToString_Category<_T, 3>{ // Stack
      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;}
};
template< class _T> struct __ToString_Category<_T, 4>{ // Queue
      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;}
};
template< class _T> struct __ToString_Category<_T, 5>{ // Deque
      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;}
};

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)))))>{};

template< class _t> std::string ToString( _t const& _v){ return __ToString<_t>::TOstring(_v);}

template< class... _H_> std::string ToString_Items( _H_ const&...){ return "";}
template< class _H_> std::string ToString_Items( _H_ const& _h){ return ToString(_h);}
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;}
}
//} omipusDebug.hpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
算法競賽配置
QT_Creator
創建一個控制臺應用, 然後在Pro文件裏添加CONFIG += c++17 (原來是c++11 修改成17);

對拍文件
`compare.cpp`

int main(){
vector< const char *> Init{"build.bat  generate_data",
                           "build.bat  supimo",
                           "build.bat  correct"};
for( auto order : Init){
      auto errorCode = system( order);
      if( errorCode != 0){ EXIT_( order, errorCode);}
}

while( true){
      static const char * Ords[] = {"generate_data.exe > data.in",
                        "supimo.exe < data.in > supimoOutput.txt",
                        "correct.exe < data.in > correctOutput.txt",
                        "fc supimoOutput.txt correctOutput.txt"};
      for( auto order : Ords){
         auto errorCode = system( order);
         if( errorCode != 0){ EXIT_( order, errorCode);}
      }
      cout<< "SUCC"<< endl;
}

return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
Bat代碼
build.bat
@echo off
del  %1.exe
g++.exe  %1.cpp  -o  %1.exe  -std=c++17  -O2  -Wall -Wl,--stack=268435456 -D"__ISsupimoENVIR_"

@DELI;

run.bat
@echo off
%1.exe  <  input.txt

@DELI;

build_and_run.bat
@echo off
call  build.bat  %1
call  run.bat  %1  %2
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
源文件
#include <bits/stdc++.h>
using namespace ::std;

//{ ___SUPIMO
namespace ___SUPIMO{
//{ Macro
#define  ASSERT_CUSTOM_( _op, ...) if( !bool(_op)){ std::cout<<"Assertion_Failed(Custom):["<< #_op<< "], Hint:["<< ___SUPIMO::Debug_::__ToString_items( __VA_ARGS__)<< "]("<< #__VA_ARGS__<< ")\n"; EXIT_;}
#define  ASSERT_SYSTEM_( _op, ...) if( !bool(_op)){ std::cout<<"Assertion_Failed(System):["<< #_op<< "], Hint:["<< ___SUPIMO::Debug_::__ToString_items( __VA_ARGS__)<< "]("<< #__VA_ARGS__<< ")\n"; EXIT_;}
#define  ASSERT_MSG_( _msg)
#define  TODO_RunTime_( _msg)  ASSERT_SYSTEM_( 0, "@TODO: " _msg)
#define  EXIT_  std::cout<< "EXIT: Line("<< __LINE__<< ")";  std::exit(1);
#define  EXIT_COUNTER_( _max)  { static int cont = 0; ++ cont; if( cont == _max){ string str = "EXIT_COUNTER(" + to_string(_max) + ")"; DE_(_str); EXIT_;}}
#define  FOR_( _i, _l, _r)  for( int _i=int(_l); _i<=int(_r); ++_i)
#define  FOR_R_( _i, _l, _r)  for( int _i=int(_l); _i>=int(_r); --_i)
#define  DE_( ...)  if( ___SUPIMO::Debug_::___IsInDebug){ std::cout<< ___SUPIMO::Debug_::__ToString_items( __VA_ARGS__)<< " {Line: "<< __LINE__<< ", Msg: ["<< #__VA_ARGS__<< "]}\n";}
#define  NOTE_( _str)
//} Macro

namespace Debug_{
static constexpr bool ___IsInDebug = 1;
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> &);
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;}
} // namespace Debug

//{ Type
template< class _T_> using Heap_small_ = std::priority_queue< _T_, std::vector<_T_>, std::greater<_T_> >;

struct Double{
using __Type = long double;  __Type Value;  static constexpr __Type __epsilon = 1e-12;
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;}
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);}
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;}
}; // class Double

template< class _ModType_, __int128 _Mod> struct Modular{
ASSERT_MSG_( "_ModType_必须是{int/int64_t/__int128}");
using __UnsignedModType_ = std::conditional_t< std::is_same_v<_ModType_,__int128>, unsigned __int128, std::make_unsigned_t<_ModType_> >;
inline static conditional_t< _ModType_(_Mod)<=0, __UnsignedModType_, std::add_const_t< __UnsignedModType_> > __Modular = _Mod;  __UnsignedModType_ Value;
Modular():Value(0){}  template<class _T> Modular( _T _v){ _v %= (_T)__Modular; if( _v<0){ _v+=__Modular;} Value = _v;}
inline static void Set_mod( _ModType_ _mod){ static_assert( ! std::is_const_v<decltype(__Modular)>); ASSERT_SYSTEM_(_mod > 0);  __Modular = _mod;}
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;}
}; // class Modular
//} Type

namespace Integer_{
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;}
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;}
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;}
template< class _TypeRadix_, class _TypeNum_> struct Radix{ // `TypeRadix: 每个进制的类型;  TypeNum: 所能表示的最大十进制数的类型`;
      std::vector<_TypeRadix_> __Radix; // 比如`Radix=[2,4,3]`, 那么所有的数为`([0-2), [0-4), [0-3))` 即表示的十进制数范围为`[0, 2*4*3)`; (Radix累乘值的大小就决定了`TypeNum`);
      std::vector<_TypeNum_> __SuffixProduct; // `SuffixProduct[i] = Radix[i]*Radix[i+1]*...`;
      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]);}}
      _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;}
      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;}
      int GetBit( _TypeNum_ _num, int _ind){ NOTE_("`ind==0`是最高位");  ASSERT_SYSTEM_( _ind>=0 && _ind<int(__Radix.size())); return _num / __SuffixProduct[_ind+1] % __Radix[_ind];}
      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];}
};
namespace Binary_{
      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;}
      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;}
      template< class _T> void SetBit( _T & _num, int _ind, bool _v){ if( _v){ _num |= ((_T)1 << _ind);} else{ _num &= (~( (_T)1 << _ind));}}
      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);}
      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);}
      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);}
      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);}
      // #枚举二进制子集#: `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]` 一定*严格递减*);
} // namespace Binary
} // namespace Integer

namespace String_{
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);}
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;}}
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;}
} // namespace String

namespace Random_{
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());
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);}
} // namespace Random

namespace Object_{
const Double Pi = std::acos((long double)-1);
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;};
template< class _T_> constexpr std::decay_t<_T_> Int_0x80 = __Int_0x80<std::decay_t<_T_> >::Data;
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;};
template< class _T_> constexpr std::decay_t<_T_> Int_0x7F = __Int_0x7F<std::decay_t<_T_> >::Data;
} // namespace Object

namespace Function_{
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;}
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);}
template< class _T> bool IsInInterval( _T _c, _T _l, _T _r){ return (_c>=_l && _c<=_r);}
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;}
} // namespace Function

} // namespace ___SUPIMO

namespace std {
template<> struct numeric_limits<___SUPIMO::Double> : public numeric_limits<___SUPIMO::Double::__Type>{};
template<> struct __is_floating_point_helper<___SUPIMO::Double> : public true_type{};
template<> struct make_unsigned<__int128>{ using type = unsigned __int128;};
___SUPIMO::Double abs( ___SUPIMO::Double const& _d){ return (_d>=0 ? _d:-_d);}
}
//} ___SUPIMO

using namespace ::___SUPIMO;

void ___Solve_oneTest(){

}
int main(){
std::ios::sync_with_stdio(0);  std::cin.tie(0);  std::cout.setf( std::ios::fixed);  std::cout.precision( 9);

auto ___Work = [](){ // 必须严格与*题目*的录入格式对应;
      constexpr int8_t mode = 0;
      int testsCount;
      if( mode == 0){ testsCount = 1;}  else if( mode == 1){ cin>> testsCount;}  else if( mode == 2){ testsCount = 1e9;}
      for( int id = 0; id < testsCount; ++id){
         if( id == 0){ // Global_Initialize

         }
         ___Solve_oneTest();
      }
};
if( ___SUPIMO::Debug_::___IsInDebug){
      for( int id = 0; id < 100000008; ++id){
         string flag;  cin>> flag;  if( flag == "___INPUT_-1"){ break;}  ASSERT_SYSTEM_( flag == (string("___INPUT_")+char('0'+id)), flag);
         ___SUPIMO::Function_::ClockSplit();
         std::cout<< flag<< ":\n";
         ___Work();
         std::cout<< "\nTimeElapsed: "<< ___SUPIMO::Function_::ClockSplit()<< "\n\n";
      }
}
else{ ___Work();}

return 0;
} // main

namespace ___SUPIMO {
namespace Debug_ {
      template< class _T> string __ToString( _T const& _v){ ostringstream ANS; ANS.precision(cout.precision()); ANS.setf(cout.flags()); ANS<<_v; return ANS.str();}
      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+")";}
      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+")";}
      string __ToString( bool _b){ return (_b?"true":"false");}
      string __ToString( char _t){ string ANS="'?'"; ANS[1]=_t; return ANS;}
      string __ToString( char const* _s){ return string(_s);}
      string __ToString( string const& _t){ string ANS="\""; ANS+=_t; ANS+='\"'; return ANS;}
      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;}
      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;}
      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;}
      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;}
      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;}
      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;}
      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;}
      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;}
      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;}
      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;}
      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;}
      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;}
      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;}
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
之所以把___Solve_oneTest()單獨寫成一個函數而是放到main函數的for循環裡面, 因為: 當我們要進行特判比如if( N==0){ cout<<"YES"; return;} 這裡的return 就是結束當前測試, 可是如果你放到for循環裡面你可能認為那用continue不就可以了? 錯誤, 因為如果你內部還有for循環這就出錯了即此時continue不是對*外部的for循環*生效; 所以必須要寫成函數形式;

Global_Initialize
专为力扣设计的, 即全局(多组测试数据所共用的)数据的初始化;

String
Split的答案一定不会有空字符串;
他是从前往后贪心进行的, 比如"xxx" 以xx分隔, 那就是[xx] x 即答案是最后的那个x; 比如"xxxx" 以xx分隔那就是[xx] [xx] 即答案是空的;

@DELI;

Replace的本质就是Split函数, 即比如你Split得到的是? X ? X ? (将X替换为Y) 则答案就是? Y ? Y ?;
. 比如S="xxxx", raw="xx", new="x", 那么答案是xx, 即先是[x] xx 然后[x] [x]; (并不是[x] xx 然后[x] x 然后x);

Debug
if( ?){ Debug::__IsOpenedDebug = 1;} 和 Debug::__IsOpenedDebug = (?); 这两个是不同的!
前者: 他是在特定情况下打开调试, 但是他不会关闭调试; 而后者: 他要么会打开调试要么就关闭;
前者通常用于针对某个子流程而调试, 比如... [T] ... 最开始我们关闭调试, 然后到[T].入口时打开调试, 然后到[T].出口时关闭调试; 即整个过程我们就调用了三次IsOpen = ?命令; 这通常在DFS时使用的较多, 即符合某种条件时进入某个DFS分支时打开, 然后回溯回来时关闭;
而后者这种方式(即不停的根据条件打开/关闭调试), 一般在非DFS的场景(比如FOR循环)里会使用, 比如只对所有奇数进行调试;
即前者他是针对一个连续的子段, 而后者是针对一个序列里满足某条件的若干元素;

@DELI;

有個疑問: 為什麼要把他轉換成string 而不是直接cout輸出呢?
. 可能是多了一层封装? (但毕竟你这个模块就只复杂Debug输出啊有必要再多封装一层吗?

@DELI;

INFO_里, 不可以对#__VA_ARGS__直接用,逗号分隔, 因为他可能是INFO_( F(a,b), 3), 所以你还得判断括号;

@DELI;

T A[10];數組類型, 你可以直接輸出DE_(A);
DE_( (T(&)[5])A); 這是輸出A[0,1,2,3,4];

auto A = new T[2][3] (此時auto == T(*)[3]);
. 要輸出他的所有元素, 此時直接DE_(A)是錯誤的(他是個指針地址), 正確語法是DE_( (T(&)[2][3])*A), 注意 *A的類型是T(&)[3], 但你把他強轉給T(&)[2][3]是可以的;

@DELI;

__Debug_list的參數必須是const _H & _h, const _T & ... _t引用不能是值傳遞;
比如對於對象很大的情況(圖本身都已經1e6級別的大小), 那麼這已經不僅僅是效率問題了, 因為參數用的是棧空間這是會爆棧的;

@DELI;

我们使用__Cout自己的重载函数而不是去重载operator<<, 一个原因是对于char/string基本类型的重载此时和系统的就冲突了 (你需要再单独写个函数使用is_same去特判) 所以不如就不使用系统重载符了直接自己定义函数; 第二个原因是其实把两者本质都一样我们自己写个__Cout函数等于多了一层封装;

你必须要声明/定义分开這是為了實現對嵌套的輸出, 比如对于vector< map<int,int> >的输出他使用了Cout( map<int,int>) 因此你必须要有其声明在vector實現函數的前面;

如果是自定义类型他会进入到Cout( T) 然后调用cout<< T, 即你的自定义类型需要有重载运算符;

@DELI;

__Cout你不需要寫成像ostream& operator<<( ostream&, T)那樣, 直接寫成void __Cout( T)即可, 這是因為: operator<<之所以要那樣寫他是要實現cout<<a<<b<<...這個操作; 而__Cout 不會調用__Cout(a) << b這種操作;

ASSERT報警宏
#如何关闭某个子模块的ASSERT$
对于算法模板A, 他里面有很多ASSERT_SYSTEM, 为了优化效率如何把他们给关闭掉呢?

#undef  ASSERT_SYSTEM_
#define  ASSERT_SYSTEM_( _op, ...)
namespace A{
}
#undef  ASSERT_SYSTEM_
#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
2
3
4
5
6
. 也不可以不写#undef, 但他会有警告warning: 'ASSERT_SYSTEM_' macro redefined;

@DELI;

ASSERT_CUSTOM_: 用戶自己的程序裏面使用這個宏;
ASSERT_SYSTEM_: 算法模板裏面的報警都使用這個;

宏
為什麼FOR_的宏定義是 (int)_r呢?
對於uint32 a = 0, (a-1)的值是111...111, 於是for( int i=0; i < (uint32)-1; ++i) 這會死循環的;
但是把111....111 強轉為int, 她就是-1, 即int i = 0; i < (int)-1; ++i) 這是正確的;

@DELI;

這3個報警宏都有2個模式:
1(默認模式):[如代碼所示];
2(優化模式):[你自己把他注釋掉, 這主要是為了(提高程序效率/便於找到程序BUG)];
. 比如默認版本是#define A x, 那麼你就把他改成#define A (void)0 // x, (注意後面的注釋// x是不生效的預編譯時會被清除掉即到時候是(void)0; 而不是(void)0 // x;)

ASSERT_MSG的優化版本即static_assert(false), 此时在开发阶段就會報錯也就是你會發現所有的調用ASSERT_MSG的位置, 就可以发现有可能存在的错误;

@DELI;

#ASSERT_MSG_( _msg)#
这是完全给用户提示的程序无法测试其正確性但你自己必须保证他是true; 比如取模除法 mod必须为质数, 就可以是ASSERT_MSG_( "mod必須是質數");

@DELI;

#ASSERT_WEAK_(op) (void)0#
即使op为假也不会报警, 但你自己要保证他一定是true 这是为了效率;

Modular
Modular的設計思想是這樣的, 她有2個模式: 對於using MOD = Modular< T, X>, T必須是有符號int/int64/128;
1: 你的Mod模數是不變的const常量, 此時這個X是常數, 即在編譯期模數就固定了;
2: 你的模數是可以改變的, 此時這個X <= 0(你任意設置一個值即可), 此時到了運行期你可以動態的通過MOD::Set_mod( m)去設置他的值且這個m參數的值即模數她必須是在T的正數範圍;
不管哪個模式假設你的T=int 你最終的模數一定是在[0, 2147483647]的範圍內的 (而不是uint32的範圍), 而且你的值Value 一定是unsigned T類型, 為什麼要這樣設計? 因為當你進行加法運算此時你不需要轉換為int64 她的加法結果一定是在uint32範圍的;

@DELI;

對於乘法操作, 如果是int32/int64 則直接轉換為int64/int128來進行乘法, 否則對於int128 則執行二進制乘法(她會調用取模加法是不會溢出的這就是為什麼你的模數必須是有符號範圍);

@DELI;

template<class _T> Modular( _T _v)這個構造函數裡你不能對他進行is_integeral的判斷, 因為對於__int128 他不滿足條件(可能未來編譯器會支持但現在他的返回值是false);

@DELI;

基本使用

using M1 = Modular<int, (int)1e9 + 7>;
所有`M1`的對象他的`Mod`都是*int常量*;

using M2 = Modular<long long, (long long)1e15 + 7>;
所有`M2`的對象他的`Mod`都是*long long常量*;

using M3 = Modular<int, -1>;
M3::Mod = ?; // 由用戶錄入 (這行代碼必須在*運行時* 即放到函數域裡)
所有`M3`的對象他的`Mod`都是int類型且等於`?`;

using M4 = Modular<long long, -2>;
M4::Mod = ?; // 由用戶錄入 (這行代碼必須在*運行時* 即放到函數域裡)
所有`M4`的對象他的`Mod`都是long long類型且等於`?`;

using M5 = Modular<int, -2>; // 注意此時要和`M3的<int,-1>`區分開來即不能寫成`-1`, 否則`M3,M5`就共用同一個`Mod`了;

@DELI;

T_ Value; // 一定是[0, Mod)范围; 不要调用`obj.Value = xx`(他不是规格化的) 而是使用`obj = xx`;
1
#除法#
调用a / b的前提是: (1: Mod是质数), (2: b != 0);

@DELI;

#BinaryMultiply#
使用a*b(重载乘法)的前提是: Mod * Mod <= INT64_MAX; 如果是Mod+Mod <= INT64_MAX 就不能使用重载乘法了可以使用当前的二进制乘法;

@DELI;

#__Cout#
这个函数的目的是: 特判, 即对char/string/const char *的输出重载, 之所以不是放到<<重载运算符函数里, 是因为如果是<<重载这些基本类型就和系统cout的内置重载函数冲突了;
也就是, 比如对于vector的重载是放到operator<<里的, 而对char的重载是在__Cout里;

函數
#IsInInterval_#
. IsInInterval_(c,l,r, true): 判斷是否滿足`c>=l && c<=r`, 即在這個區間裡;
. IsInInterval_(c,l,r, false): 判斷是否不滿足`c>=l && c<=r`, 即在這個區間外;
1
2
3
Integer
GetPowerRoot( a, p), 比如令T = a^{1/p}, 则返回值为T的下取整;

@DELI;

VectorToInteger和IntegerToVector是互逆的;
數字的高位就對應 Vector的開頭; 這樣設計是因為: 對於一個整數321 我們通常是從高位開始閱讀因此高位對應vector.front();
. 比如, 整數321 (3是高位 1是低位) 她對應的Vector是[3,2,1] (3是開頭元素);

@DELI;

使用该模块里的任何函数都是谨慎, 最好就是在调试期间调用, 你要充分考虑好他的实际效率问题;
比如VectorToInteger( {a,b,c}, 5)这个函数, 其实你可以自己手动写成a*5*5 + b*5 + c, 没必要去调用这个函数, 因为此时你已经得到了{a,b,c} 他的长度是明确的去调用这个函数反而效率非常低;

@DELI;

vector<int> IntegerToVector( _T _a, int _len, const int _radix);
比如a=10, radix=2, 他對應的2進制表示為1010, 那麼此時你必須保證len>=4 (否則會報警);
. @IF(len==-1):[答案為[1,0,1,0]], @ELSE(len!=-1):[答案為[0...0,1,0,1,0](即前面補充前導零答案長度為len)];

@DELI;

Sqrt( a, p)
要確保a>=1, p>=2, 假設答案是浮點數b 且返回值是b的下取整;
這個函數的主要目的是判斷a是否是p次冪如果是則返回其p次根;
. 由於b = pow( a*a*a, 1/3), 此時b可能是a-1/ a, 而答案是a, 所以要判斷是否b+1 == a;

@TODO
Modular里面, 我们用unsigned T来存储结果, 但实际上你的取模值一定是[0, T)范围的, 即只使用了一半, 这是因为当涉及到+-时此时不会溢出;
. 但这有缺点, 当你Modular a = -2时, 此时构造函数是-2 % 5 他会变成int % uint -> uint%uint 即-2会变成uint 这就出错了!!! 因此要写成int%int;
最好是, 你就用T来存储结果, 当相加时他虽然会溢出但其实他还是正确的! a += b; if(a<0){ a -= Modular;}就可以了;

错误
is_floating_point_v< Double> 他是等于0的! 因为Double是我们自己的自定义类型;
你可以写以下代码后, namespace std{ template<> struct __is_floating_point_helper<Double>:public true_type {};}, 此时就可以了;

算法模板编写规范
错误
模板类不要写构造函数，因为我们可能写到全局域里 ST s(而不是ST s(??) 此时不能有参数；

@DELI;

不要写namespace ST{ using T = ?; vector<T> DP; void Work(){}}这种代码; 这样会导致ST是一次性的即T是唯一的; 然而namespace不能加模板;
一种做法是: template<T> struct ST{ static vector<T> DP; static void Work(){} };, 但这样有2个缺点: (DP需要在类外定义因为他是static), (由于ST是类而实际上他里面都是static的不会用到他的对象这就违背了类的初衷了);
最优做法是: namespace ST{ template<T> vector<T> DP; template<T> void Work(){ 使用DP<T>;};

性质
模板类里放大数组constexpr int N = ?; int Arr[ N]; 等你用到时再把?赋值, 这种方式他确实是效率比vector<int> Arr要高, 但有个缺点是你到时候的类对象就不能放栈空间了需要是static ST s 否则大数组就爆空间了;

@DELI;

不需要寫一個TODO_STATIC_的宏, 對於靜態的@TODO, 你直接寫成注釋即可: @TODO: xxx, 然後實際使用時再把他給注釋掉即可;

@DELI;

#讓某個函數必須在程序開始後執行一次且只能執行一次#

void Init(){
EXIT_COUNTER_(2);
}
@TODO: Init();
1
2
3
4
這類函數通常是不可以有函數參數的 (比如篩質數函數), 也就是她的參數是根據題目的最大數據範圍而不是錄入的值;

不要用__attribute__((constructor)), 她是報錯的, 因為他不是在運行時執行的, 而我們的需求是在運行時執行;

@DELI;

#類/命名空間的Debug調試#

class ___X{
friend ostream& operator<<( ostream & _cout, const ___X & _a){
_cout<<"\n";
      DE_( "___X-Debug-Begin");

      cout<< ?; // 此時不可以使用`DE_(?) 或 `Debug::__CoutItems(?)`, 必須使用原生的`cout`;

      DE_( "___X-Debug-End");
}
}

namespace ___X{
void Debug(){
DE_( "___X-Debug-Begin");

      cout<< ?; // 此時不可以使用`DE_(?) 或 `Debug::__CoutItems(?)`, 必須使用原生的`cout`;

      DE_( "___X-Debug-End");
}
}

@DELI;

#嵌入模板的全局变量#

{ // ___XX
const int ___Number = ?; // 这里就叫做全局变量; 要以三个`___`开头
int ___N = ?;
for( int i = 1; i <= 5; ++i){
int a = ?; // 像`i,a`这种*临时变量* 可以不用写`___`开头;
}

} // ___XX

@DELI;

#Initialize函数, 强制的放到构造函数里#
最经典的例子是(建图)

Graph( int _points_count_maximum, int _edges_count_maximum){}
void Initialize( int _points_count){}
1
2
这样分来会导致, 每次使用时必须是: Graph G( 100005, 200005); G.Initialize( n), 也就是两个代码行 (两个操作, 两个步骤)
一旦忘记手动的调用Initialize函数, 虽然会报警, 那你还需要再去写代码补上调用这个函数;

当我们将Initialize函数, 嵌入到构造函数里

Graph( int _points_count_maximum, int _edges_count_maximum, int _points_count){
...
//--
Initialize( _points_count);
}
void Initialize( int _points_count){}

注意, Initialize函数和原来是一样的, 只是做了两个事情:
1 将Initialize函数的参数接到构造函数参数的后面 (比如, 原来构造函数参数是a,b,c, Initialize函数参数是x,y,z, 那么现在变成构造函数参数变成了a,b,c, x,y,z)
2 在构造函数的最最结尾, 调用Initialize( x, y, z)函数;

@DELI;

#数组长度用函数传参来指定#

template< int _Maximum>
class ST{
ST(){
array = new int[ _Maximum];
}
private:
int * array;
};

The above code should be replaced to:

class ST{
ST( int _maximum)
:
maximum( _maximum){
array = new int[ maximum];
}
private:
int * array;
const int maximum;
};

@DELI;
笔记
有向无环图DAG
最小路径点覆盖
//{ @Snippet, `ZuiXiao LuJing DianFuGai (最小路径点覆盖)`
{
int n = `the points-range in the DAG`;
//--
BipartiteGraph B( n * 2, `the edges-count in the DAG`);
B.Initialize( n * 2);
for( int i = 0; i < n * 2; ++i){
      if( i < n) B.Set_pointBelongingness( i, true);
      else B.Set_pointBelongingness( i, false);
}
for( `s -> t` : all edges in the `DAG`){
      B.Add_edge( s, t, 0);
}
//--
Bipartite_MaximalMatch M( &B);
M.Initialize();
$(n - M.Get_maxMatch()) is the answer;
}
//} @Snippet, `ZuiXiao LuJing DianFuGai (最小路径点覆盖)`

最小路径重复点覆盖, 最大路径独立集
//{ @Snippet, `ZuiXiao LuJing ChongFu DianFuGai (最小路径重复点覆盖)` `ZuiDa LuJing DuLiJi (最大路径独立集)`
{
int n = `the points-range in the DAG`;
bool * edges[ @PlaceHolder] = $(edges[a][b] means a edge `a->b` in the DAG`;
//--
$(perform the `Floyd-Boolean` on @Var(edges));
//--
BipartiteGraph B( n * 2, n * n);
B.Initialize( n * 2);
for( int i = 0; i < n * 2; ++i){
      if( i < n) B.Set_pointBelongingness( i, true);
      else B.Set_pointBelongingness( i, false);
}
for( int a = 0; a < n; ++a){
      for( int b = 0; b < n; ++b){
         if( false == edges[ a][ b]){ continue;}
         B.Add_edge( a, b + n);
      }
}
//--
Bipartite_MaximalMatch M( &B);
M.Initialize();
$(n - M.Get_maxMatch()) is the answer;
}
//} @Snippet, `ZuiXiao LuJing ChongFu DianFuGai (最小路径重复点覆盖)` `ZuiDa LuJing DuLiJi (最大路径独立集)`

DAG的终点
//{ @Snippet, `EndPoints of a DAG`
{
int n = `the points-range of the DAG`;
int * departure = `int ?[ >= n]`; //< the departure-degree of a point;
memset( departure, 0, sizeof( int) * n);
for( `a -> b` : $(all edges in the DAG)){
      ++ departure[ a];
}
for( int i = 0; i < n; ++i){
      if( departure[ i] == 0){
//< `i` is a End-Point in DAG
      }
}
}
//} @Snippet, `EndPoints of a DAG`

DAG的起点
//{ @Snippet, `StartPoints of a DAG`
{
int n = `the points-range of the DAG`;
int * incidence = `int ?[ >= n]`; //< the incidence-degree of a point;
memset( incidence, 0, sizeof( int) * n);
for( `a -> b` : $(all edges in the DAG)){
      ++ incidence[ b];
}
for( int i = 0; i < n; ++i){
      if( incidence[ i] == 0){
//< `i` is a Start-Point in DAG
      }
}
}
//} @Snippet, `StartPoints of a DAG`

判断一个图是否为DAG, 求拓扑序
bool Work(){
//< `1` Check whether a Graph is a DAG; `2` Get TopologySequence;
int points_range = @Unfinished;
int * topological_sequence = @Unfinished(an outside array whose length must `>=` @Var(points_range));
int * incidence = @Unfinished(an outside array whose length must `>=` @Var(points_range));
memset( incidence, 0, sizeof( int) * points_range);
for( `a -> b` : $(all edges in the DAG){
++ incidence[ b];
}
int size = 0;
for( int s = 0; s < points_range; ++s){
      if( incidence[ s] == 0){
         topological_sequence[ size] = s;
         ++ size;
      }
}
int head = 0;
while( head < size){
      int cur = topological_sequence[ head];
      ++ head;
for( `a` : $(all adjacent-points of `cur`){
         -- incidence[ a];
         if( incidence[ a] == 0){
            topological_sequence[ size ++] = a;
         }
      }
}
if( size != points_range){
      return false;
}
//>< The answer Topological-Sequence has been stored in @Var(topological_sequence)
return true;
}

图论
最短路
TARJAN
无向图-PBCC点双连通分量
+ 割点

//{ Tarjan_PBCC-Declaration
template< class _Edge_Type>
class Tarjan_PBCC{
public:
const vector< int> * Pbcc;
const bool * Is_cutPoint;
//-- variable ends
Tarjan_PBCC( const Graph< _Edge_Type> *);
void Initialize();
int Get_pbcc_count() const;
private:
const Graph< _Edge_Type> * graph;
int * stack_;
int stack_top;
int * dfs_id;
int dfs_idCounter;
int * low_id;
vector< int> * pbcc;
int pbcc_count;
int dfs_startPoint;
bool * is_cutPoint;
int cutPoint_count;
//-- variable ends
void dfs( int);
};
//} Tarjan_PBCC-Declaration

//{ Tarjan_PBCC-Implementation
//{ Variable-Annotation
//{ @Var(pbcc)
// + `pbcc[i]={a1,a2,...}` means that the PBCC with id `i` consists of these points {a1,a2,...}
//} @Var(pbcc)
//{ @Var(graph)
// + must be a undirected-graph, i.e., Edge[i] = Edge[i^1]
//} @Var(graph)
//} Variable-Annotation
template< class _Edge_Type> int Tarjan_PBCC< _Edge_Type>::Get_cutPoint_count() const{ return cutPoint_count;}
template< class _Edge_Type> int Tarjan_PBCC< _Edge_Type>::Get_pbcc_count() const{ return pbcc_count;}
template< class _Edge_Type> Tarjan_PBCC< _Edge_Type>::Tarjan_PBCC( const Graph< _Edge_Type> * _graph)
      :
      graph( _graph){
stack_ = new int[ graph->Get_pointsCountMaximum()];
dfs_id = new int[ graph->Get_pointsCountMaximum()];
low_id = new int[ graph->Get_pointsCountMaximum()];
pbcc = new vector< int>[ graph->Get_pointsCountMaximum()];
is_cutPoint = new bool[ graph->Get_pointsCountMaximum()];
//--
Pbcc = pbcc;
Is_cutPoint = is_cutPoint;
}
template< class _Edge_Type> void Tarjan_PBCC< _Edge_Type>::Initialize(){
stack_top = 0;
dfs_idCounter = 0;
pbcc_count = 0;
cutPoint_count = 0;
for( int i = 0; i < graph->Get_pointsCount(); ++i){ pbcc[ i].clear();}
memset( is_cutPoint, false, sizeof( bool) * graph->Get_pointsCount());
memset( dfs_id, -1, sizeof( int) * graph->Get_pointsCount());
for( int i = 0; i < graph->Get_pointsCount(); ++i){
      if( -1 == dfs_id[ i]){
         dfs_startPoint = i;
         dfs( i);
      }
}
}
template< class _Edge_Type> void Tarjan_PBCC< _Edge_Type>::dfs( int _cur){
stack_[ stack_top ++] = _cur;
low_id[ _cur] = dfs_id[ _cur] = dfs_idCounter ++;
//--
int cc_count = 0;
if( _cur != dfs_startPoint){ ++ cc_count;}
for( int nex, edge = graph->Head[ _cur]; ~edge; edge = graph->Next[ edge]){
      nex = graph->Vertex[ edge];
      if( -1 == dfs_id[ nex]){
         dfs( nex);
         //>< `low_id[nex]` always `<= dfs_id[_cur]`
         if( low_id[ nex] == dfs_id[ _cur]){
            ++ cc_count;
            if( cc_count >= 2){
                  is_cutPoint[ _cur] = true;
                  ++ cutPoint_count;
                  while( true){
                     int c = stack_[ stack_top - 1];
                     -- stack_top;
                     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.
                     if( c == nex){ break;}
                  }
                  pbcc[ pbcc_count].push_back( _cur);
                  //>< `pbcc[ pbcc_count].size()` >= 2
                  ++ pbcc_count;
            }
         }
         low_id[ _cur] = min( low_id[ nex], low_id[ _cur]);
      }
      else{ //< `nex` must on the `stack` due to the graph is Undirected
         low_id[ _cur] = min( dfs_id[ nex], low_id[ _cur]);
      }
}
//--
if( _cur == dfs_startPoint){
      while( true){
         int c = stack_[ stack_top - 1];
         -- stack_top;
         pbcc[ pbcc_count].push_back( c);
         if( c == _cur){ break;}
      }
      ++ pbcc_count;
}
//>< `cc_count` means the number of Connected-Component when `_cur` was removed from the current Connected-Component (whatever `cur` is Cut-Point or not);
}
//} Tarjan_PBCC-Implementation

无向图-EBCC边双连通分量
+ 桥

//{ Tarjan_EBCC-Declaration
template< class _Edge_Type>
class Tarjan_EBCC{
public:
const int * Ebcc_id;
const int * Ebcc_size;
//-- variable ends
Tarjan_EBCC( const Graph< _Edge_Type> *);
void Initialize();
int Get_ebcc_count() const;
const Graph< _Edge_Type> * Build_tree() const;
private:
const Graph< _Edge_Type> * graph;
int * stack_;
int stack_top;
int * dfs_id;
int * low_id;
int dfs_idCounter;
int * ebcc_id;
int * ebcc_size;
int ebcc_count;
//-- variable ends
void dfs( int, int);
};
//} Tarjan_EBCC-Declaration

//{ Tarjan_EBCC-Implementation
//{ Variable-Annotation
//{ @Var(graph)
// + must be a undirected-graph, i.e., Edge[i] = Edge[i^1]
//} @Var(graph)
//{ @Var(Ebcc_id)
// + `y=Ebcc_id[x]` where `x` is a point of @Var(ptrRef_graph) and `y` belongs to `[0, @Func(Get_ebcc_count)-1]`
//} @Var(Ebcc_id)
//{ @Var(Ebcc_size)
// + `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)
//} @Var(Ebcc_size)
//} Variable-Annotation
template< class _Edge_Type> Tarjan_EBCC< _Edge_Type>::Tarjan_EBCC( const Graph< _Edge_Type> * _graph)
      :
      graph( _graph){
stack_ = new int[ graph->Get_pointsCountMaximum()];
ebcc_id = new int[ graph->Get_pointsCountMaximum()];
ebcc_size = new int[ graph->Get_pointsCountMaximum()];
dfs_id = new int[ graph->Get_pointsCountMaximum()];
low_id = new int[ graph->Get_pointsCountMaximum()];
//--
Ebcc_id = ebcc_id;
Ebcc_size = ebcc_size;
}
template< class _Edge_Type> void Tarjan_EBCC< _Edge_Type>::Initialize(){
stack_top = 0;
dfs_idCounter= 0;
ebcc_count = 0;
memset( dfs_id, -1, sizeof( int) * graph->Get_pointsCount());
for( int i = 0; i < graph->Get_pointsCount(); ++i){
      if( -1 == dfs_id[ i]){
         dfs( i, -1);
      }
}
}
template< class _Edge_Type> const Graph< _Edge_Type> * Tarjan_EBCC< _Edge_Type>::Build_tree() const{
//< + Make sure @Func(Initialize) has been called
//< + There is at most one undirected-edge between any two points in the Tree (i.e., @Ret)
Graph< _Edge_Type> * Tree = new Graph< _Edge_Type>( ebcc_count, graph->Get_edgesCountMaximum());
Tree->Initialize( ebcc_count);
for( int a, b, i = 0; i < graph->Get_pointsCount(); ++i){
      for( int j, z = graph->Head[ i]; ~z; z = graph->Next[ z]){
         j = graph->Vertex[ z];
         a = ebcc_id[ i];
         b = ebcc_id[ j];
         if( a != b){
            // Now, there must has no edges between `ebcc_id[ i]` and `ebcc_id[ j]`
            Tree->Add_edge( ebcc_id[ i], ebcc_id[ j], graph->Weight[ z]);
         }
      }
}
return Tree;
}
template< class _Edge_Type> void Tarjan_EBCC< _Edge_Type>::dfs( int _cur, int _father_edgeId){
stack_[ stack_top ++] = _cur;
low_id[ _cur] = dfs_id[ _cur] = dfs_idCounter ++;
//--
for( int nex, edge = graph->Head[ _cur]; ~edge; edge = graph->Next[ edge]){
      nex = graph->Vertex[ edge];
      if( (edge ^ 1) == _father_edgeId){ continue;}
      if( -1 == dfs_id[ nex]){
         dfs( nex, edge);
         low_id[ _cur] = min( low_id[ nex], low_id[ _cur]);
      }
      else{
         low_id[ _cur] = min( dfs_id[ nex], low_id[ _cur]);
      }
}
if( low_id[ _cur] == dfs_id[ _cur]){
      ebcc_size[ ebcc_count] = 0;
      while( true){
         int c = stack_[ stack_top - 1];
         -- stack_top;
         ebcc_id[ c] = ebcc_count;
         ++ ebcc_size[ ebcc_count];
         if( c == _cur){ break;}
      }
      ++ ebcc_count;
}
}
//} Tarjan_EBCC-Implementation

SCC有向图强联通分量
//{ Tarjan_SCC
template< class _Weight_Type>
class Tarjan_SCC{
public:
const int * Scc_id;
const int * Scc_size;
//-- variable ends
Tarjan_SCC( const Graph< _Weight_Type> *);
void Initialize();
int Get_scc_count() const;
const Graph< _Weight_Type> * Build_DAG() const;
const Graph< _Weight_Type> * Build_DAG_uniqueEdges() const;
private:
const Graph< _Weight_Type> * ptrRef_graph;
int * ptrNew_queue;
int queue_tail;
bool * ptrNew_isInQueue;
int dfsOrderId_counter;
int * ptrNew_sccId;
int scc_id_counter;
int * ptrNew_sccSize;
//-- variable ends
void dfs( int);
};
//{ Variable-Annotation
// + @Var(Scc_id)
// . `y=Scc_id[x]` where `x` is a point of @Var(ptrRef_graph) and `y` belongs to `[0, @Func(Get_scc_count)-1]`
// + @Var(Scc_size)
// . `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)
//} Variable-Annotation
template< class _Weight_Type> Tarjan_SCC< _Weight_Type>::Tarjan_SCC( const Graph< _Weight_Type> * _graph)
      :
      ptrRef_graph( _graph){
ptrNew_queue = new int[ ptrRef_graph->Get_pointsCountMaximum()];
ptrNew_isInQueue = new bool[ ptrRef_graph->Get_pointsCountMaximum()];
ptrNew_sccId = new int[ ptrRef_graph->Get_pointsCountMaximum()];
ptrNew_sccSize = new int[ ptrRef_graph->Get_pointsCountMaximum()];
//--
Scc_id = ptrNew_sccId;
Scc_size = ptrNew_sccSize;
}
template< class _Weight_Type> void Tarjan_SCC< _Weight_Type>::Initialize(){
queue_tail = 0;
dfsOrderId_counter = 0;
memset( ptrNew_sccId, -1, sizeof( int) * ptrRef_graph->Get_pointsCount());
scc_id_counter = 0;
for( int i = 0; i < ptrRef_graph->Get_pointsCount(); ++i){
      if( -1 == ptrNew_sccId[ i]){
         dfs( i);
      }
}
}
template< class _Weight_Type> const Graph< _Weight_Type> * Tarjan_SCC< _Weight_Type>::Build_DAG() const{
//< + Make sure @Func(Initialize) has been called
Graph< _Weight_Type> * DAG = new Graph< _Weight_Type>( scc_id_counter, ptrRef_graph->Get_edgesCountMaximum());
DAG->Initialize( scc_id_counter);
for( int a, b, i = 0; i < ptrRef_graph->Get_pointsCount(); ++i){
      for( int j, z = ptrRef_graph->Head[ i]; ~z; z = ptrRef_graph->Next[ z]){
         j = ptrRef_graph->Vertex[ z];
         a = ptrNew_sccId[ i];
         b = ptrNew_sccId[ j];
         if( a != b){
            DAG->Add_edge( ptrNew_sccId[ i], ptrNew_sccId[ j], ptrRef_graph->Weight[ z]);
         }
      }
}
return DAG;
}
template< class _Weight_Type> const Graph< _Weight_Type> * Tarjan_SCC< _Weight_Type>::Build_DAG_uniqueEdges() const{
//< + Make sure @Func(Initialize) has been called
//< + There is at most one edge between any two points in the DAG (i.e., @Ret)
unordered_set< long long> hash_edges;
Graph< _Weight_Type> * DAG = new Graph< _Weight_Type>( scc_id_counter, ptrRef_graph->Get_edgesCountMaximum());
DAG->Initialize( scc_id_counter);
for( int a, b, i = 0; i < ptrRef_graph->Get_pointsCount(); ++i){
      for( int j, z = ptrRef_graph->Head[ i]; ~z; z = ptrRef_graph->Next[ z]){
         j = ptrRef_graph->Vertex[ z];
         a = ptrNew_sccId[ i];
         b = ptrNew_sccId[ j];
         if( a != b){
            long long hash_val = (long long)a * scc_id_counter + b;
            if( hash_edges.find( hash_val) != hash_edges.end()){
                  continue;
            }
            hash_edges.insert( hash_val);
            DAG->Add_edge( ptrNew_sccId[ i], ptrNew_sccId[ j], ptrRef_graph->Weight[ z]);
         }
      }
}
return DAG;
}
template< class _Weight_Type> void Tarjan_SCC< _Weight_Type>::dfs( int _cur){
ptrNew_queue[ queue_tail ++] = _cur;
ptrNew_isInQueue[ _cur] = true;
int current_dfsOrderId = dfsOrderId_counter;
ptrNew_sccId[ _cur] = dfsOrderId_counter ++;
//--
for( int nex, i = ptrRef_graph->Head[ _cur]; ~i; i = ptrRef_graph->Next[ i]){
      nex = ptrRef_graph->Vertex[ i];
      if( -1 == ptrNew_sccId[ nex]){
         dfs( nex);
      }
      if( ptrNew_isInQueue[ nex]){
         ptrNew_sccId[ _cur] = min( ptrNew_sccId[ nex], ptrNew_sccId[ _cur]);
      }
}
if( ptrNew_sccId[ _cur] == current_dfsOrderId){
      ptrNew_sccSize[ scc_id_counter] = 0;
      while( true){
         int c = ptrNew_queue[ queue_tail - 1];
         ptrNew_isInQueue[ c] = false;
         -- queue_tail;
         ptrNew_sccId[ c] = scc_id_counter;
         ++ ptrNew_sccSize[ scc_id_counter];
         if( c == _cur){ break;}
      }
      ++ scc_id_counter;
}
}
//} Tarjan_SCC

差分约束系统,不等式组
//{ Minimize_InequalitiesSystem
template < typename _Edge_Type, typename _Distance_Type>
class Minimize_InequalitiesSystem{
public:
const _Distance_Type * Distance;
//-- variable ends
Minimize_InequalitiesSystem( const Graph_Weighted< _Edge_Type> * _graph)
         :
         ptrRef_graph( _graph){
      ptr_distance = new _Distance_Type[ ptrRef_graph->Get_pointsCountMaximum()];
      Distance = ptr_distance;
      ptr_isInQueue = new bool[ ptrRef_graph->Get_pointsCountMaximum()];
      ptr_queue = new int[ ptrRef_graph->Get_pointsCountMaximum() + 1];
      points_range = 0;
      ptrNew_pathLength = new int[ ptrRef_graph->Get_pointsCountMaximum()];
      //--
      Initialize();
}
void Initialize(){
      points_range = ptrRef_graph->Get_pointsCount();
}
bool Work(){
      memset( ptr_distance, 0, sizeof( _Distance_Type) * points_range);
      memset( ptrNew_pathLength, 0, sizeof( int) * points_range);
      for( int i = 0; i < points_range; ++i){
         ptr_queue[ i] = i;
      }
      memset( ptr_isInQueue, true, sizeof( bool) * points_range);
      queue_head = 0;
      queue_tail = points_range;
      //--
      int cur, nex, edge;
      while( queue_head != queue_tail){
         cur = ptr_queue[ queue_head ++];
         ptr_isInQueue[ cur] = false;
         if( queue_head > points_range){ queue_head = 0;}
         for( edge = ptrRef_graph->Head[ cur]; ~edge; edge = ptrRef_graph->Next[ edge]){
            nex = ptrRef_graph->Vertex[ edge];
            if( ptr_distance[ cur] + ptrRef_graph->Weight[ edge] > ptr_distance[ nex]){
                  ptrNew_pathLength[ nex] = ptrNew_pathLength[ cur] + 1;
                  if( ptrNew_pathLength[ nex] >= points_range){
                     return false;
                  }
                  ptr_distance[ nex] = ptr_distance[ cur] + ptrRef_graph->Weight[ edge];
                  if( false == ptr_isInQueue[ nex]){
                     ptr_isInQueue[ nex] = true;
                     ptr_queue[ queue_tail ++] = nex;
                     if( queue_tail > points_range){ queue_tail = 0;}
                  }
            }
         }
      }
      return true;
}
private:
const Graph_Weighted< _Edge_Type> * ptrRef_graph;
int points_range;
_Distance_Type * ptr_distance;
bool * ptr_isInQueue;
int * ptr_queue;
int queue_head, queue_tail;
int * ptrNew_pathLength;
};
//} Minimize_InequalitiesSystem

Caution

`+` You should never modify the source-code of @Func( Work), otherwise, it means your algorithm must be erroneous.
1
Annotation

`+` @Func( Work)
`1` `@Ret = true` means the Inequality-System is Consistent, otherwise it is Inconsistent (No-Solution).
`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`;
`.` In other words, under the premise `all variables xi >= 0`, minimize every variable and also satisfies all relations (i.e., the graph)

`+` @Var( ptrRef_graph)
`.` 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.

数论
矩阵乘法
//{ MatrixMultiplication-Declaration
template< class _Type, int _MaximumLength>
class MatrixMultiplication{
public:
MatrixMultiplication( _Type);
void Initialize( int, _Type (*)[ _MaximumLength], const _Type (*)[ _MaximumLength], const _Type (*)[ _MaximumLength][ _MaximumLength], long long);
private:
_Type modulus;
int length;
_Type factor[ _MaximumLength][ _MaximumLength];
_Type answer[ _MaximumLength][ _MaximumLength];
_Type temp[ _MaximumLength][ _MaximumLength];
//-- variable ends
void matrix_multiplication( _Type (*)[ _MaximumLength][ _MaximumLength], const _Type (*)[ _MaximumLength][ _MaximumLength], const _Type (*)[ _MaximumLength][ _MaximumLength]);
};
//} MatrixMultiplication-Declaration

//{ MatrixMultiplication-Implementation
template< class _Type, int _MaximumLength> MatrixMultiplication< _Type, _MaximumLength>::MatrixMultiplication( _Type _modulus)
      :
      modulus( _modulus){
}
template< 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){
//<
// @Brief
// . `result = dp * (factor ^ k)`;
// @Warning
// . Make sure the data of `dp` is `dp[0, ..., _length)`, the data of `_factor` is `[ (0,0) -> (_length-1, _length-1) ]`;
ASSERT_( _k >= 0);
ASSERT_( _length <= _MaximumLength);
//----
length = _length;
//--
memset( answer, 0, sizeof( answer));
for( int i = 0; i < length; ++i){
      answer[ 0][ i] = (* _dp)[ i] % modulus;  if( answer[ 0][ i] < 0){ answer[ 0][ i] += modulus;}
}
for( int i = 0; i < length; ++i){
      for( int j = 0; j < length; ++j){
         factor[ i][ j] = (* _factor)[ i][ j] % modulus;  if( factor[ i][ j] < 0){ factor[ i][ j] += modulus;}
      }
}
//--
while( _k > 0){
      if( _k & 1){
         matrix_multiplication( &answer, &answer, &factor);
      }
      _k >>= 1;
      matrix_multiplication( &factor, &factor, &factor);
}
//--
memcpy( _result, answer[ 0], sizeof( _Type) * length); // the address of `_result` equals to the address of its first-element;
}
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]){
//<
// @Brief
// . `result = a * b`;
for( int i = 0; i < length; ++i){
      for( int j = 0; j < length; ++j){
         //>> Cuz `result` maybe equals to `a/b`, you need store the result to `temp` not `result`;
         temp[ i][ j] = 0;
         for( int z = 0; z < length; ++z){
            temp[ i][ j] += (long long)((* _a)[ i][ z]) * (* _b)[ z][ j] % modulus;  if( temp[ i][ j] >= modulus){ temp[ i][ j] -= modulus;}
         }
      }
}
memcpy( _result, temp, sizeof( temp));
}
//} MatrixMultiplication-Implementation

@Delimiter

示例

int Dp[ 4] = {1, 2, 2, 1};
int A[ 4][ 4] = {{0,1,0,0}, {1,1,1,0}, {0,0,1,1}, {0,0,0,1}};
MatrixMultiplication< int, 4> Mat( M);
Mat.Initialize( 4, &Dp, &Dp, &A, N - 2);

long long ans = (long long)Dp[ 2] * N % M - Dp[ 3];
cout<< ans;
1
2
3
4
5
6
7
中国剩余定理
朴素 CRT
//{ CRT-Declaration
template< class _Type> pair< long long, long long> CRT( int, const pair< _Type, _Type> *);
//} CRT-Declaration

//{ CRT-Implementation
template< class _Type> pair< long long, long long> CRT( int _n, const pair< _Type, _Type> * _arr){
//<
// @Brief
// . Solve the system of `n` Congruence-Equations represented by `arr` (i.e., `? = arr[i].first (% arr[i].second)`);
// . Once all `arr[?].second` are Pairwise-Coprime, this system must be Solvable (and Infinite-Solutions);
// . @Define( `(a,m)` = @Return), `a` must in the range [0, m), and the Solutons are $a + kk * m, \forall kk \in \Z$;
// @Warning
// . Make sure all `arr[?].second` must be Pairwise-Coprime;
// . Make sure the Product of all `arr[?].second` in the range `long long`;
// @TimeCost
// . $n * 60$;
long long M = 1;
for( int i = 0; i < _n; ++i){
      ASSERT_( _arr[ i].second >= 1);
      M *= _arr[ i].second;
}
long long answer = 0;
for( int i = 0; i < _n; ++i){
      _Type a = _arr[ i].first % _arr[ i].second;  if( a < 0){ a += _arr[ i].second;}
      long long m = M / _arr[ i].second;
      pair< bool, pair< _Type, _Type> > ret = LCE_BezoutE< long long>( m, 1, _arr[ i].second); // m * `ret.second` = 1 (% _arr[ i].second);
      ASSERT_( ret.first); // All `arr.second` are not Pairwise-Coprime which rebels the Premise-Of-This-Algorithm (See @Warning);
      answer = (answer + (long long)a * m % M * ret.second.first % M) % M;
}
return {answer, M};
}
//} CRT-Implementation

拓展 CRT_EX
//{ CRT_EX-Declatation
template< class _Type> pair< bool, pair< long long, long long> > CRT_EX( int, const pair< _Type, _Type> *);
//} CRT_EX-Declatation

//{ CRT_EX-Implementation
template< class _Type> pair< bool, pair< long long, long long> > CRT_EX( int _n, const pair< _Type, _Type> * _arr){
//<
// @Brief
// . Solve the system of `n` Congruence-Equations represented by `arr` (i.e., `? = arr[i].first (% arr[i].second)`);
// . @Define( `(r1, (r2,r3))` = @Return);
//    0( r1=false): There is No-Solution;
//    1( ELSE): The Solutons are `r2 + kk * r3, $\forall kk \in \Z$`, and `r2` must in the range [0, r3);
// . All `arr[?].second` maybe not Pairwise-Coprime (which differs from `CRT`);
// @Warning
// . Make sure the LCM (Least-Common-Multiple) of all `arr[?].second` in the range `long long`;
// @TimeCost
// . $n * 60$;
pair< bool, pair< long long, long long> > answer;
long long A, M;
for( int i = 0; i < _n; ++i){
      _Type a = _arr[ i].first;
      a %= _arr[ i].second;  if( a < 0){ a += _arr[ i].second;}
      //--
      if( i == 0){
         A = a, M = _arr[ i].second;
         continue;
      }
      pair< bool, pair< _Type, _Type> > ret = LCE_BezoutE< long long>( M, a - A, _arr[ i].second);
      if( false == ret.first){
         answer.first = false;
         return answer;
      }
      _Type gcd = _arr[ i].second / ret.second.second;  if( gcd < 0){ gcd = -gcd;} // The GCD of `M` and `_arr[i].second`;
      long long new_M = M / gcd * _arr[ i].second; // LCM
      A = (A + ret.second.first * M % new_M) % new_M;
      M = new_M;
}
answer.first = true;
answer.second.first = A;
answer.second.second = M;
return answer;
}
//} CRT_EX-Implementation
1
裴蜀方程 BezoutE
//{ BezoutE-Declaration
template< class _Type> pair< bool, pair< pair< long long, _Type>, pair< long long, _Type> > > BezoutE( _Type _a, _Type _b, _Type _c);
//} BezoutE-Declaration

//{ BezoutE-Implementation
template< class _Type> pair< _Type, pair< long long, long long> > BezoutE_extendedGCD( _Type _a, _Type _b){
//<
// @Private
// @Warning
// . Make sure `a,b >= 0`, Not-Both-Be-`0`;
if( _b == 0){
      return {_a, {1, 0}};
}
auto pre = BezoutE_extendedGCD( _b, _a % _b);
auto xp = pre.second.first;
auto yp = pre.second.second;
return {pre.first, {yp, xp - yp * ( _a / _b)}};
};
template< class _Type> pair< bool, pair< pair< long long, _Type>, pair< long long, _Type> > > BezoutE( _Type _a, _Type _b, _Type _c){
//<
// @Brief
// . Solve the equation `xx * a + yy * b = c`, @Define( `(r1, ((a1,m1), (a2,m2)))` = @Return)`;
// 0( r1=false): There is no Solution;
// 1( ELSE): The General-Solutions are `(a1 + k * m1, a2 - k * m2) $\forall k \in \Z$`;
// @TimeCost
// . $\ln(a)$;
// @Warning
// . Make sure `a != 0`, `b != 0`;
ASSERT_( (_a != 0) && (_b != 0));
pair< bool, pair< pair< long long, _Type>, pair< long long, _Type> > > answer;
bool neg_a = false, neg_b = false;
if( _a < 0){ neg_a = true;  _a = -_a;} // `x * a + y * b = c` -> `(-x) * (-a) + y * b = c`;
if( _b < 0){ neg_b = true;  _b = -_b;} // `x * a + y * b = c` -> `x * a + (-y) * (-b) = c`;
//--
pair< _Type, pair< long long, long long> > ret = BezoutE_extendedGCD( _a, _b);
if( _c % ret.first != 0){
      answer.first = false;
      return answer;
}
answer.first = true;
answer.second.first.first = ret.second.first * (_c / ret.first);
answer.second.first.second = _b / ret.first;
answer.second.second.first = ret.second.second * (_c / ret.first);
answer.second.second.second = _a / ret.first;
if( neg_a){ answer.second.first.first = -answer.second.first.first;}
if( neg_b){ answer.second.second.first = -answer.second.second.first;}
return answer;
}
//} BezoutE-Implementation

线性同余方程 LCE
裴蜀方程法 LCE_BezoutE
//{ LCE_BezoutE-Declaration
template< class _Type> pair< bool, pair< _Type, _Type> > LCE_BezoutE( _Type _a, _Type _b, _Type _mod);
//} LCE_BezoutE-Declaration

//{ LCE_BezoutE-Implementation
template< class _Type> pair< bool, pair< _Type, _Type> > LCE_BezoutE( _Type _a, _Type _b, _Type _mod){
//<
// @Brief
// . Solve the Congruen-Equation `a * ? = b (% mod)` where `?` is @Return; @Define( `(r1, (a1,m1))` = @Return);
// 0( r1=false): There is No-Solution;
// 1( ELSE): The General-Solutions are `a1 + k * m1, $\forall k \in \Z$`, and `a1` always in the range [0, m);
// @TimeCost
// . $\ln(_a)$;
ASSERT_( _mod >= 1);
pair< bool, pair< _Type, _Type> > answer;
_a %= _mod;  if( _a < 0){ _a += _mod;}
_b %= _mod;  if( _b < 0){ _b += _mod;}
if( _a == 0){
      if( _b == 0){
         answer.first = true;
         answer.second.first = 0;
         answer.second.second = 1;
         return answer;
      }
      else{
         answer.first = false;
         return answer;
      }
}
_Type gcd = GCD< _Type>( _a, _mod);
pair< bool, pair< pair< long long, _Type>, pair< long long, _Type> > > ret = BezoutE< _Type>( _a, _mod, gcd);
ASSERT_( ret.first);
if( _b % gcd != 0){
      answer.first = false;
      return answer;
}
answer.second.second = _mod / gcd;
answer.second.first = Binary_Multiplication< _Type>( ret.second.first.first, _b / gcd, answer.second.second);
answer.first = true;
return answer;
}
//} LCE_BezoutE-Implementation

高斯消元线性方程组
//{ Gaussian elimination
double Aug[ 105][ 105]; //< @Abbr( augmented matrix)
int Gaussian_elimination( int _m, int _n){
//< @Par( _m): the number of equations
//< @Par( _n): the number of variables
//< @Return: (0 is unique solution), (1 is infinitely many), (-1 is no solution)
int rank = 0;
for( int col = 0; ( col < _n) && ( rank < _m); ++col){
      int max_row = rank;
      for( int row = rank + 1; row < _m; ++row){
         if( fabs( Aug[ row][ col]) > fabs( Aug[ max_row][ col])){
            max_row = row;
         }
      }
      if( 0 == Db_cmp( fabs( Aug[ max_row][ col]), 0, Epsilon)){
         //* either no solution, or infinitely many.
         continue;
      }
      //{ swap two rows
      for( int c = 0; c < _n + 1; ++c){
         swap( Aug[ max_row][ c], Aug[ rank][ c]);
      }
      //}
      //{ make current pivot to `1`
      for( int c = _n; c > col; --c){
         Aug[ rank][ c] /= Aug[ rank][ col];
      }
      Aug[ rank][ col] = 1;
      //}
      //{ make all rows below current pivot in the same column to `0`
      for( int r = rank + 1; r < _m; ++r){
         if( 0 == Db_cmp( fabs( Aug[ r][ col]), 0, Epsilon)){
            continue;
         }
         for( int c = _n; c > col; --c){
            Aug[ r][ c] -= Aug[ r][ col] * Aug[ rank][ c];
         }
         Aug[ r][ col] = 0;
      }
      ++ rank;
}
//--
for( int r = rank; r < _m; ++r){
      if( 0 != Db_cmp( Aug[ r][ _n], 0, Epsilon)){
         return -1;
      }
}
if( rank != n){
      return 1;
}
//> the upper-left `_n * _n` submatrix of `Aug` is a identity-matrix
for( int r = rank - 1; r > 0; --r){
      for( int rr = 0; rr < r; ++rr){
         if( 0 == Db_cmp( Aug[ rr][ r], 0, Epsilon)){
            continue;
         }
         Aug[ rr][ _n] -= Aug[ rr][ r] * Aug[ r][ _n];
         Aug[ rr][ r] = 0;
      }
}
return 0;
}
//} Gaussian elimination

		自动登录	找回密码
密码			注册

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

浏览过的版块