算法 {算法代码模板,算法模板编写规范}

算法 {算法代码模板,算法模板编写规范}

算法 {算法代码模板,算法模板编写规范}

算法代码模板

代码

#include <bits/stdc++.h>
using namespace ::std;namespace ___Tools{
//{ Macro
#define  ASSERT_( _op)  assert( _op)
#define  ASSERT_WEAK_( _op)  ASSERT_( _op)
#define  ASSERT_MSG_( _msg)  static_assert( true, _msg)
#define  EXIT_( ...)  DE_( __VA_ARGS__, "EXIT!");  exit(0)
#define  EXIT_COUNTER_( _max)  { static int cont = 0; ++ cont; if( cont == _max){ string str = "EXIT_COUNTER(" + to_string(_max) + ")"; EXIT_(str);}}
#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(___Tools::Debug::__IsEnable_DE){ cout<< ___Tools::Debug::__ToString_items( __VA_ARGS__)<< "    {Line: "<< __LINE__<< ", Msg: "<< #__VA_ARGS__<< "}n";}
#define  INFO_( ...)  ___Tools::Debug::__Info_items( #__VA_ARGS__, __VA_ARGS__)
//} Macronamespace Debug{bool __IsEnable_DE = true;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> &);template< class _T> string __ToString( const _T & _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(), d());}  return "UInt128("+ANS+")";}   string __ToString( __int128 _v){ string ANS; if( _v == 0){ ANS = "0";} else{ if( _v < 0){ ANS+="-";}  for( ; _v != 0; _v /= 10){ ANS+=('0' + std::abs((int)(_v%10)));}  reverse(ANS.begin()+(ANS[0]=='-'?1:0), d());}  return "Int128("+ANS+")";}    string __ToString( bool _b){ ostringstream ANS; ANS<< (_b ? "true" : "false"); return ANS.str();}    string __ToString( char _t){ ostringstream ANS; ANS<< '''<< _t<< '''; return ANS.str();}    string __ToString( const char * _s){ ostringstream ANS; ANS<< '"'<< _s<< '"'; return ANS.str();}    string __ToString( const string & _t){ ostringstream ANS; ANS<< '"'<< _t<< '"'; return ANS.str();}    template< class _T, int _N> string __ToString( const _T (& _v)[ _N]){ ostringstream ANS; ANS<< "Array["; bool first = true; FOR_( ind, 0, _N-1){ if( false == first) ANS<<","; if( first) first = false; ANS<<__ToString(_v[ind]);} ANS<<"]"; return ANS.str();}    template< class _T1, class _T2> string __ToString( const pair< _T1, _T2> & _v){ ostringstream ANS; ANS<< "Pair("; ANS<<__ToString( _v.first); ANS<< ","; ANS<<__ToString( _v.second); ANS<< ")"; return ANS.str();}    template< class _T> string __ToString( const vector< _T> & _v){ ostringstream ANS; ANS<< "Vector["; bool first = true; for( const auto & i : _v){ if( false == first) ANS<<","; if( first) first = false; ANS<<__ToString(i);} ANS<<"]"; return ANS.str();}    template< class _T> string __ToString( const set< _T> & _v){ ostringstream ANS; ANS<< "Set["; bool first = true; for( const auto & i : _v){ if( false == first) ANS<<","; if( first) first = false; ANS<<__ToString(i);} ANS<<"]"; return ANS.str();}    template< class _T> string __ToString( const unordered_set< _T> & _v){ ostringstream ANS; ANS<< "UnorderedSet{"; bool first = true; for( const auto & i : _v){ if( false == first) ANS<<","; if( first) first = false; ANS<<__ToString(i);} ANS<<"}"; return ANS.str();}    template< class _Key, class _Val> string __ToString( const map< _Key, _Val> & _v){ ostringstream ANS; ANS<< "Map["; bool first = true; for( const auto & i : _v){ if( false == first) ANS<<","; if( first) first = false; ANS<< "("; ANS<<__ToString( i.first); ANS<< ":"; ANS<<__ToString(i.second); ANS<<")";} ANS<<"]"; return ANS.str();}    template< class _Key, class _Val> string __ToString( const unordered_map< _Key, _Val> & _v){ ostringstream ANS; ANS<< "UnorderedMap{"; bool first = true; for( const auto & i : _v){ if( false == first) ANS<<","; if( first) first = false; ANS<< "("; ANS<<__ToString( i.first); ANS<< ":"; ANS<<__ToString(i.second); ANS<<")";} ANS<<"}"; return ANS.str();}    template< class _T> string __ToString( const multiset< _T> & _v){ ostringstream ANS; ANS<< "MultiSet["; bool first = true; for( const auto & i : _v){ if( false == first) ANS<<","; if( first) first = false; ANS<<__ToString(i);} ANS<<"]"; return ANS.str();}    template< class _T> string __ToString( const unordered_multiset< _T> & _v){ ostringstream ANS; ANS<< "UnorderedMultiSet{"; bool first = true; for( const auto & i : _v){ if( false == first) ANS<<","; if( first) first = false; ANS<<__ToString(i);} ANS<<"}"; return ANS.str();}    template< class _T1, class _T2> string __ToString( const tuple< _T1, _T2> & _v){ ostringstream ANS; ANS<< "Tuple2("; ANS<<__ToString(std::get< 0>( _v)); ANS<< ","; ANS<<__ToString(std::get< 1>( _v)); ANS<< ")"; return ANS.str();}    template< class _T1, class _T2, class _T3> string __ToString( const tuple< _T1, _T2, _T3> & _v){ ostringstream 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.str();}    template< class _T1, class _T2, class _T3, class _T4> string __ToString( const tuple< _T1, _T2, _T3, _T4> & _v){ ostringstream 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.str();}    template< class _T1, class _T2, class _T3, class _T4, class _T5> string __ToString( const tuple< _T1, _T2, _T3, _T4, _T5> & _v){ ostringstream 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.str();}string __ToString_items(){ return "";}    template< class _H,  _T> string __ToString_items( const _H & _h, const _T & ... _t){ ostringstream ANS; ANS<<__ToString( _h); if( ( _t) > 0){ ANS<<", ";} ANS<<__ToString_items( _t...); return ANS.str();}string __Info_items( string){ return "";}    template< class _H,  _T> string __Info_items( string _names, const _H & _h, const _T & ... _t){ ASSERT_(_names.size()>=1);  string curName;  { int i=0;  while( i < (int)_names.size()){  if( _names[i]==','){ break;}  if( _names[i]=='('){  int c = 0;  while( i < (int)_names.size()){  curName += _names[i];  if( _names[i]=='('){ ++c;}  if( _names[i]==')'){ --c;}  if( c==0){ break;}  ++ i;}  ++ i;  continue;}  curName += _names[i];  ++ i;}  _ase( 0, i+1);  while( pty()==false && curName.front()==' '){ ase(curName.begin());}  while( pty()==false && curName.back()==' '){ d()-1);}}   { (void)"把`a.Data`變成`Data`"; for( auto it = curName.find( "."); it != string::npos; it = curName.find(".")){ ase( 0, it+1);}  for( auto it = curName.find( "->"); it != string::npos; it = curName.find("->")){ ase( 0, it+2);}}   ASSERT_( pty()==false);  ostringstream ANS; ANS<<curName<<": "<<__ToString( _h);  if( ( _t) > 0){ ANS<<", ";}  ANS<<__Info_items( _names, _t ...);  if( ( _t) == 0){ ASSERT_(_pty());}  return ANS.str();}
} // namespace Debug//{ Double
using Double = long double;    static constexpr Double __DoubleEpsilon_ = 1e-12;
int Double_cmp( Double _a, Double _b){ if( (_a < _b ? _b-_a : _a-_b) <= __DoubleEpsilon_){ return 0;} return (_a < _b ? -1 : 1);}
//} Doublenamespace Integer{template< class _T> _T Power( _T _base, int _pow){ ASSERT_WEAK_(_pow>=0); _T ANS=1; while(_pow-- > 0){ ANS*=_base;} return ANS;}template< class _T> int Sqrt( _T _a, int _p){ ASSERT_WEAK_(_a>=1 && _p>=2); int ANS = ::std::pow<Double>( _a, (Double)1/_p); _T sum = 1; FOR_( i, 1, _p){ sum *= (ANS + 1);} if( sum == _a){ return ANS + 1;} return ANS;}template< class _T> _T VectorToInteger( const vector<int> & _v, const int _radix){ ASSERT_( _v.size()>0); _T ANS = 0; for( auto i : _v){ ASSERT_WEAK_( i>=0 && i<_radix);  ANS *= _radix; ANS += i;} return ANS;}template< class _T> vector<int> IntegerToVector( _T _a, int _len, const int _radix){ ASSERT_( _a>=0);  vector<int> ANS;  for( auto t = _a; t > 0; t /= _radix){ ANS.push_back( t%_radix);}  if(_a==0){ ANS.push_back(0);}  while( _len!=-1 && (int)ANS.size() < _len){ ANS.push_back( 0);}  ASSERT_WEAK_( _len==-1 || (int)ANS.size()==_len);  reverse( ANS.begin(), d());  return ANS;}template< class _T> _T __GetPower( int _radix, int _power){ ASSERT_( false && "修改`__Power[a][b]`使其滿足`a>_radix && b>_power`"); static _T __Power[0][0]; static bool __isFirst = true;  if( __isFirst){ __isFirst=false; memset(__Power, -1, sizeof(__Power));} auto & cur = __Power[_radix][_power]; if( cur == -1){ cur = 1; for( int i = 0; i < _power; ++i){ cur *= _radix;}} return cur;}template< class _T> int GetBit( _T _num, int _index, const int _radix){ return _num / __GetPower<_T>(_radix,_index) % _radix;}template< class _T> void SetBit( _T & _num, int _index, int _value, const int _radix){ _num += (_value - GetBit(_num,_index,_radix)) * __GetPower<_T>(_radix,_index);}namespace Binary{template< class _T> vector<int> GetBits( _T _num, int _len){ vector<int> ANS;  if( _len==-1){ _len = sizeof(_T)*8;} size(_len); FOR_( i, 0, _len-1){ ANS[_len-1-i] = (_num>>i)&1;} return ANS;}template< class _T> int GetBit( _T _num, int _index){ return (_num >> _index) & 1;}template< class _T> void SetBit( _T & _num, int _index, int _v){ if( _v == 1){ _num |= ((_T)1 << _index);} else{ _num &= (~( (_T)1 << _index));}}void __builtin_ctz(); // __builtin_ctz(int), __builtin_ctzll(int64): 二進制中 最低位的`1`的下標(即連續的後綴的`0`的個數); 比如`...100`的答案為`2`;void __builtin_clz(); // __builtin_clz(int), __builtin_clzll(int64): 二進制中 連續的前綴的`0`的個數; 比如&#`的答案為`3`;void __builtin_popcount(); // __builtin_popcount(int), __builtin_popcountll(int64): 二進制中`1`的個數;} // namespace Binary
} // namespace Integernamespace String{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( pty()==false){ ANS.push_back(cur);}  cur.clear();  i += m;  continue;}  cur += _s[i];  ++ i;}  if( pty()==false){ ANS.push_back(cur);}  return ANS;}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){  _place( i, m, _new);  i += _new.size();  continue;}  ++ i;}}
} // namespace Stringnamespace Random{mt19937 MT32( chrono::steady_clock::now().time_since_epoch().count());    mt19937_64 MT64( 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() / UINT32_MAX);}    Double GetDouble64( Double _l, Double _r){ return _l + (_r - _l) * (Double)(MT64() / UINT64_MAX);}
} // namespace Randomtemplate< class _ModType_, __int128 _Mod> class Modular{
public:static_assert( std::is_same_v<_ModType_,int> || std::is_same_v<_ModType_,int64_t> || std::is_same_v<_ModType_,__int128>);using __UnsignedModType_ = std::conditional_t< std::is_same_v<_ModType_,__int128>, unsigned __int128, std::conditional_t< std::is_same_v<_ModType_,int>, unsigned int, uint64_t> >;inline static conditional_t< _Mod<0, __UnsignedModType_, std::add_const_t< __UnsignedModType_> > Mod = _Mod;__UnsignedModType_ Value;Modular():Value(0){}    template<class _T> Modular( _T _v){ Value=_v%Mod; if(Value<0){ Value+=Mod;}}inline static void Set_mod( _ModType_ _mod){ static_assert( false == std::is_const_v<decltype(Mod)>); ASSERT_(_mod > 0);  Mod = _mod;}Modular operator-() const{ return Modular(0) - *this;}    void operator++(){ ++Value; if(Value==Mod){Value=0;}}    void operator++(int){ ++Value; if(Value==Mod){Value=0;}}    void operator--(){ if(Value==0){Value=Mod-1;} else{--Value;}}    void operator--(int){ if(Value==0){Value=Mod-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 (false == (*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("<< ::___Tools::Debug::__ToString(_a.Value)<< ")"; return _cout;}void operator-=( const Modular & _a){ if( Value < _a.Value){ Value = (Mod - (_a.Value - Value));}else{ Value -= _a.Value;}}   void operator+=( const Modular & _a){ Value += _a.Value; if( Value >= Mod) Value -= Mod;}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 % Mod;} 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_( _a.Value != 0); *this *= _a.Power( Mod - 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 Modularnamespace Object{const Double Pi = acos( -1);  const Double Pi_twice = Pi*2;  const Double Pi_half = Pi/2;    constexpr int64_t INT64_0x80=0x8080808080808080, INT64_0xC0=0xC0C0C0C0C0C0C0C0, INT64_0x3F=0x3F3F3F3F3F3F3F3F, INT64_0x7F=0x7F7F7F7F7F7F7F7F;
} // namespace Objectnamespace Function{template< class _T> bool IsInInterval( _T _c, _T _l, _T _r, bool _rel){ return (_c>=_l && _c<=_r) == _rel;}
} // namespace Function} // namespace ___Tools
using namespace ::___Tools;
//----void ___Solve( ){{ // ___LocalInitialize}}
void ___GlobleInitialize(){
}
int main(){ios::sync_with_stdio( false);  cin.tie( nullptr);  cout.setf( ios::fixed);  cout.precision( 2);___GlobleInitialize();//    int ___tests; cin>> ___tests; for( int ___id = 0; ___id < ___tests; ++___id)___Solve( );return 0;
}

注釋

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

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报警宏

這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`;

#除法#
调用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`, 即在這個區間外;

Integer

使用该模块里的任何函数 都是谨慎, 最好就是在调试期间调用, 你要充分考虑好他的实际效率问题;
比如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;

算法模板编写规范

#類/命名空間的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;

#嵌入模板的全局变量#

{ // ___XXconst 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){}

这样分来 会导致, 每次使用时 必须是: 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;

其他算法

选择前K小/大数

//{ 前K小/大的元素
auto add_? = [ &@Unfinish(目标数组)] -> void{
//<
// @TimeCost
// . O(K);static constexpr int __K_ = ?;@Unfinish(目标数组).emplace_back( _a);if( depth.size() > __K_){nth_element( @Unfinish(目标数组).begin(), @Unfinish(目标数组).begin() + __K_, @Unfinish(目标数组).end());//< 如果要`前K大`的元素, 则添加第4参数`greater<?>()`;@Unfinish(目标数组).resize( __K_);}
};
//} 前K大/小的元素

数组元素去重

数组

sort( A, A + N);
N = unique( A, A + N) - A;

vector

sort( A.begin(), A.end());
A.erase( unique( A.begin(), A.end()), A.end());

最长相同前缀后缀

两个字符串

{ //{ LSPS-EX
// @Brief
// . `answer` is the `LSPS-EX` of Suffixed-`strMain` and Prefixed-`strMatch`, where `strMain-current` is the Last-Element of `strMain`;
// . `preMatched_len` is the `LSPS-EX` of Suffixed-`ss` (ss: `strMain` with removing its Last-Element) and Prefixed-`strMatch`;
// . `LSPS_strMatch` is the `LSPS` of `strMatch`;
// @TimeCost
// . $1$;using Type = @Unfinisded( the type of elements); // @Unfinisded( the type of elements);const Type * strMatch = @Unfinished( match-string); // @Unfinished( match-string);int strMatch_length = @Unfinished( the length of `strMatch`); // @Unfinished( the length of `strMatch`);ASSERT_( strMatch_length >= 1);Type strMain_last = @Unfinished( the back-element of `strMain`); // @Unfinished( the back-element of `strMain`);int preMatched_len = @Unfinished( the `LSPS-EX` of Suffixed-`ss` (ss: `strMain` with removing its Last-Element) and Prefixed-`strMatch`); // @Unfinished( the `LSPS-EX` of Suffixed-`ss` (ss: `strMain` with removing its Last-Element) and Prefixed-`strMatch`);const int * LSPS_strMatch = @Unfinished( `LSPS` of `strMatch`); // @Unfinished( `LSPS` of `strMatch`);int * answer = @Unfinished( the `LSPS-EX` of Suffixed-`strMain` and Prefixed-`strMatch`); // @Unfinished( the `LSPS-EX` of Suffixed-`strMain` and Prefixed-`strMatch`);ASSERT_( strMatch_length >= 1);if( preMatched_len == strMatch_length){preMatched_len = LSPS_strMatch[ strMatch_length - 1];}while( true){if( preMatched_len == 0){if( strMain_last == strMatch[ 0]){ *answer = 1;}else{ *answer = 0;}//--break;}if( strMain_last == strMatch[ preMatched_len]){*answer = preMatched_len + 1;//--break;}preMatched_len = LSPS_strMatch[ preMatched_len - 1];}
} //} LSPS-EX

@Delimiter

示例

Find the `LSPS-EX` of A[...i] and B[all] (i.e., it must be a suffix of A and a prefix of B);
If we already know that, the `LSPS-EX` of `A[...,i-1]` and `B[all]` is `pre` (as the below variable);
And the element `A[i]` is `c` (as the below variable);
You need pre-handle the `LSPS` of `B` (as the below variable `LSPS_len_B`);for( int pre = 0; pre < m; ++pre){for( char c = '0'; c <= '9'; ++c){int len; // the LSPS-EX of `A[...,i-1] + c` and `B[all]`;{ //{ LSPS-EXusing Type = char; // @Unfinisded( the type of elements);const Type * strMatch = B.c_str(); // @Unfinished( match-string);int strMatch_length = B.size(); // @Unfinished( the length of `strMatch`);ASSERT_( strMatch_length >= 1);Type strMain_last = c; // @Unfinished( the back-element of `strMain`);int preMatched_len = pre; // @Unfinished( the `LSPS-EX` of Suffixed-`ss` (ss: `strMain` with removing its Last-Element) and Prefixed-`strMatch`);const int * LSPS_strMatch = LSPS_len_B; // @Unfinished( `LSPS` of `strMatch`);int * answer = &len;...} //} LSPS-EX}
}

单个字符串

//{ Build_LongestSamePrefixSuffix-Declaration
template< class _Type> void Build_LongestSamePrefixSuffix( int, const _Type *, int *);
//} Build_LongestSamePrefixSuffix-Declaration//{ Build_LongestSamePrefixSuffix-Implementation
template< class _Type> void Build_LongestSamePrefixSuffix( int _length, const _Type * _str, int * _result){
//<
// @Brief
// . The range of `str` is [0, n);
// @TimeCost
// . $_length$;ASSERT_( _length >= 1);_result[ 0] = 0;for( int i = 1; i < _length; ++i){int len = _result[ i - 1];while( true){if( len == 0){if( _str[ i] == _str[ 0]){ _result[ i] = 1;}else{ _result[ i] = 0;}//--break;}if( _str[ i] == _str[ len]){_result[ i] = len + 1;//--break;}len = _result[ len - 1];}}
}
//} Build_LongestSamePrefixSuffix-Implementation

数据结构

树Tree

求每个点的最长距离

基于边权 ValuedEdge

//{ MaximalDistance_OnTree_ValuedEdge-Declaration
template< class _Type_EdgeValue, class _Type_DistanceValue>
class MaximalDistance_OnTree_ValuedEdge{
public:MaximalDistance_OnTree_ValuedEdge( const Graph_Weighted< _Type_EdgeValue> *);void Initialize();_Type_DistanceValue Get_maximalDistance( int) const;
private:const Graph_Weighted< _Type_EdgeValue> * tree;_Type_DistanceValue * maximalDistance;//-- variable endsvoid dfs_down( int, int);void dfs_up( int, int, _Type_DistanceValue);
};
//} MaximalDistance_OnTree_ValuedEdge-Declaration//{ MaximalDistance_OnTree_ValuedEdge-Implementation
// + `maximalDistance` always $>= 0$;
template< class _Type_EdgeValue, class _Type_DistanceValue> MaximalDistance_OnTree_ValuedEdge< _Type_EdgeValue, _Type_DistanceValue>::MaximalDistance_OnTree_ValuedEdge( const Graph_Weighted< _Type_EdgeValue> * _tree):tree( _tree){maximalDistance = new _Type_DistanceValue[ tree->Get_pointsCountMaximum()];
}
template< class _Type_EdgeValue, class _Type_DistanceValue> _Type_DistanceValue MaximalDistance_OnTree_ValuedEdge< _Type_EdgeValue, _Type_DistanceValue>::Get_maximalDistance( int _point) const{ASSERT_( (_point >= 0) && (_point < tree->Get_pointsCount()));return maximalDistance[ _point];
}
template< class _Type_EdgeValue, class _Type_DistanceValue> void MaximalDistance_OnTree_ValuedEdge< _Type_EdgeValue, _Type_DistanceValue>::Initialize(){
// The root of the tree is supposed `0`;ASSERT_( tree->Get_pointsCount() >= 1);dfs_down( 0, -1);//>< the `Maximal Distance-Down` has finalized;dfs_up( 0, -1, 0);
}
template< class _Type_EdgeValue, class _Type_DistanceValue> void MaximalDistance_OnTree_ValuedEdge< _Type_EdgeValue, _Type_DistanceValue>::dfs_down( int _cur, int _fa){maximalDistance[ _cur] = 0;for( int nex, edge = tree->Head[ _cur]; ~edge; edge = tree->Next[ edge]){nex = tree->Vertex[ edge];if( nex == _fa){ continue;}dfs_down( nex, _cur);maximalDistance[ _cur] = max( maximalDistance[ nex] + tree->Weight[ edge], maximalDistance[ _cur]);}
}
template< class _Type_EdgeValue, class _Type_DistanceValue> void MaximalDistance_OnTree_ValuedEdge< _Type_EdgeValue, _Type_DistanceValue>::dfs_up( int _cur, int _fa, _Type_DistanceValue _up){
//< + @Var(_up): the Maximal-Path of @Var(cur) in the form `cur->fa->...`(or `cur`);maximalDistance[ _cur] = max( _up, maximalDistance[ _cur]); //< the answer (i.e., MaximalDistance) of `_cur` is finalized;//--_Type_DistanceValue max_down_1 = 0, max_down_2 = 0; //< corresponding to the `Maximum`, `InferiorMaximum` Distance-Down of all `Sons` of @Var(_cur);int son_1 = -1; //< corresponding to `max_down_1`;for( int nex, edge = tree->Head[ _cur]; ~edge; edge = tree->Next[ edge]){nex = tree->Vertex[ edge];if( nex == _fa){ continue;}_Type_DistanceValue down = maximalDistance[ nex] + tree->Weight[ edge];if( down > max_down_1){max_down_2 = max_down_1;max_down_1 = down;son_1 = nex;}else if( down > max_down_2){max_down_2 = down;}}//--for( int nex, edge = tree->Head[ _cur]; ~edge; edge = tree->Next[ edge]){nex = tree->Vertex[ edge];if( nex == _fa){ continue;}if( nex != son_1){dfs_up( nex, _cur, max( _up, max_down_1) + tree->Weight[ edge]);}else{dfs_up( nex, _cur, max( _up, max_down_2) + tree->Weight[ edge]);}}
}
//} MaximalDistance_OnTree_ValuedEdge-Implementation

基于点权 ValuedPoint

//{ MaximalDistance_OnTree_ValuedPoint-Declaration
template< class _Type_PointValue, class _Type_DistanceValue>
class MaximalDistance_OnTree_ValuedPoint{
public:MaximalDistance_OnTree_ValuedPoint( const Graph *, const _Type_PointValue *);void Initialize();_Type_DistanceValue Get_maximalDistance( int) const;
private:const Graph * tree;const _Type_PointValue * point_value;_Type_DistanceValue * maximalDistance;//-- variable endsvoid dfs_down( int, int);void dfs_up( int, int, _Type_DistanceValue);
};
//} MaximalDistance_OnTree_ValuedPoint-Declaration//{ MaximalDistance_OnTree_ValuedPoint-Implementation
// + Stipulate that a Path must contains `at least one-point`, i.e., `maximalDistance[x]` must contains the value `point_value[x]`;
template< class _Type_PointValue, class _Type_DistanceValue> MaximalDistance_OnTree_ValuedPoint< _Type_PointValue, _Type_DistanceValue>::MaximalDistance_OnTree_ValuedPoint( const Graph * _tree, const _Type_PointValue * _point_value):tree( _tree),point_value( _point_value){maximalDistance = new _Type_DistanceValue[ tree->Get_pointsCountMaximum()];
}
template< class _Type_PointValue, class _Type_DistanceValue> _Type_DistanceValue MaximalDistance_OnTree_ValuedPoint< _Type_PointValue, _Type_DistanceValue>::Get_maximalDistance( int _point) const{ASSERT_( (_point >= 0) && (_point < tree->Get_pointsCount()));return maximalDistance[ _point];
}
template< class _Type_PointValue, class _Type_DistanceValue> void MaximalDistance_OnTree_ValuedPoint< _Type_PointValue, _Type_DistanceValue>::Initialize(){
// The root of the tree is supposed `0`;ASSERT_( tree->Get_pointsCount() >= 1);dfs_down( 0, -1);//>< the `Maximal Distance-Down` has finalized;dfs_up( 0, -1, 0);
}
template< class _Type_PointValue, class _Type_DistanceValue> void MaximalDistance_OnTree_ValuedPoint< _Type_PointValue, _Type_DistanceValue>::dfs_down( int _cur, int _fa){maximalDistance[ _cur] = 0;for( int nex, edge = tree->Head[ _cur]; ~edge; edge = tree->Next[ edge]){nex = tree->Vertex[ edge];if( nex == _fa){ continue;}dfs_down( nex, _cur);maximalDistance[ _cur] = max( maximalDistance[ nex], maximalDistance[ _cur]);}maximalDistance[ _cur] += point_value[ _cur];
}
template< class _Type_PointValue, class _Type_DistanceValue> void MaximalDistance_OnTree_ValuedPoint< _Type_PointValue, _Type_DistanceValue>::dfs_up( int _cur, int _fa, _Type_DistanceValue _up){
//< + @Var(_up), the Maximal-Path of @Var(_fa) without visiting @Var(_cur) (i.e., `fa->x->y->...` where `x != @Var(_cur)`);maximalDistance[ _cur] = max( _up + point_value[ _cur], maximalDistance[ _cur]); //< the answer (i.e., MaximalDistance) of `_cur` is finalized;//--_Type_DistanceValue max_down_1 = 0, max_down_2 = 0; //< corresponding to the `Maximum and InferiorMaximum` Distance-Down of all `Sons` of @Var(_cur);int son_1 = -1; //< corresponding to `max_down_1`;for( int nex, edge = tree->Head[ _cur]; ~edge; edge = tree->Next[ edge]){nex = tree->Vertex[ edge];if( nex == _fa){ continue;}if( maximalDistance[ nex] > max_down_1){max_down_2 = max_down_1;max_down_1 = maximalDistance[ nex];  son_1 = nex;}else if( maximalDistance[ nex] > max_down_2){max_down_2 = maximalDistance[ nex];}}//--for( int nex, edge = tree->Head[ _cur]; ~edge; edge = tree->Next[ edge]){nex = tree->Vertex[ edge];if( nex == _fa){ continue;}if( nex != son_1){dfs_up( nex, _cur, max( _up, max_down_1) + point_value[ _cur]);}else{dfs_up( nex, _cur, max( _up, max_down_2) + point_value[ _cur]);}}
}
//} MaximalDistance_OnTree_ValuedPoint-Implementation

有向无环图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;
}

区间最值RMQ

template< class _Type, int _MaxLength, int _MaxLog>
class RMQ{
//< `_MaxLength`: the maximal length of array, ranges [0, _MaxLength - 1]
//< `_MaxLog`: maximal number satifying (2^x <= _MaxLength)
private:_Type Dp[ _MaxLength][ _MaxLog + 1]; //< Dp[i][j]: max/min( arr[i],...,arr[i + (1<<j) - 1])int Log[ _MaxLength + 1]; //< Log[4]=2, Log[5]=2int Length; //< the actual length of array
public:RMQ( const _Type * _arr, int _length) : Length( _length){assert( (1 << _MaxLog) <= _MaxLength);assert( (1 << (_MaxLog + 1)) > _MaxLength);assert( Length <= _MaxLength);//--for( int i = 0; i < _length; ++i){Dp[ i][ 0] = _arr[ i];}for( int p = 1; p <= _MaxLog; ++p){int l = 0;while( l + (1 << p) <= Length){Dp[ l][ p] = ?( Dp[ l][ p - 1], Dp[ l + (1 << (p-1))][ p - 1]);++ l;}}//--Log[ 1] = 0;for( int i = 2; i <= Length; ++i){Log[ i] = Log[ i / 2] + 1;}            }_Type Query( int _l, int _r){assert( (_l >= 0) && (_l <= _r) && (_r < Length));int p = Log[ _r - _l + 1];return ?( Dp[ _l][ p], Dp[ _r - (1 << p) + 1][ p]);}
};

回文串

O ( n 2 ) O(n^2) O(n2)预处理二维数组

template< int _SquareArrayLength>
void Palindrome_preProcess( char * _str, int _length, bool (* _result)[_SquareArrayLength]){ASSERT_( _length < _SquareArrayLength);//--memset( _result, false, sizeof( bool) * _SquareArrayLength* _SquareArrayLength);int l, r;for( int i = 0; i < _length; ++i){_result[ i][ i] = true;l = i - 1, r = i + 1;while( (l >= 0) && (r < _length)){if( _str[ l] == _str[ r]){_result[ l][ r] = true;-- l, ++ r;}else{break;}}}for( int i = 0; i < _length; ++i){l = i, r = i + 1;while( (l >= 0) && (r < _length)){if( _str[ l] == _str[ r]){_result[ l][ r] = true;-- l, ++ r;}else{break;}}}
}
//} Palindrome_preProcess

# 图论## 最短路## TARJAN### 无向图-PBCC点双连通分量
`+` 割点```cpp
//{ Tarjan_PBCC-Declaration
template< class _Edge_Type>
class Tarjan_PBCC{
public:const vector< int> * Pbcc;const bool * Is_cutPoint;//-- variable endsTarjan_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 endsvoid 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 Undirectedlow_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 endsTarjan_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 endsvoid 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 endsTarjan_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 endsvoid 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 calledGraph< _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) != d()){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 endsMinimize_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.

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 endsvoid 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;

中国剩余定理

朴素 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; // LCMA = (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

裴蜀方程 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 inue;}//{ swap two rowsfor( 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-matrixfor( 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