Template

source: NA

CPP template.

#include <bits/stdc++.h>

using namespace std;

#define FIO                                                        \
  ios_base::sync_with_stdio(0); /* false */                        \
  cin.tie(0);                   /* nullptr */                      \
  cout.tie(0);                  /* nullptr */

typedef long long lli;
typedef long double ld;

#ifndef ONLINE_JUDGE
#define perr(x) cerr << #x << " " << (x) << endl
#else
#define perr(x) 0
#endif // !ONLINE_JUDGE

#define sz(c) c.size()
#define fora(i, a, b) for(lli i = (a); (i) < (b); ++i) // [a -> b)
#define ford(i, a, b) for(lli i = (a); (i)-- > (b);)   // [b <- a)

typedef lli num;

int main() {
  FIO;
  return 0;
}

Utils

Macros

source: NA

Useful macros.

#include <vector>

using namespace std;

#define sz(c) c.size()

#define fora(i, a, b) for(lli i = (a); (i) < (b); ++i) // [a -> b)
#define ford(i, a, b) for(lli i = (a); (i)-- > (b);)   // [b <- a)

#define mid(l, r) ((l) + ((r) - (l)) / 2)
#define btl(p) ((p) * 2)     // binary tree buf left child
#define btr(p) ((p) * 2 + 1) // binary tree buf right child

#define INF(T, s) numeric_limits<T>::s() // s: min | max

#define alias_t(T, A)                                              \
  typedef T A;                                                     \
  const T POSINF = INF(T, max);                                    \
  const T NEGINF = INF(T, min);                                    \
  typedef vector<T> vec;                                           \
  typedef pair<T, T> pr;

#define all(v) v.begin(), v.end()

Types

source: NA

Useful types.

typedef size_t size;
typedef long long lli;
typedef unsigned long long ull;
typedef long double ld;

Operator overload and template specialization of std::hash examples.

struct Type {
  int x, y;

  Type operator*(const Type &o) const;
  bool operator==(const Type &o) const;

  friend ostream &operator<<(ostream &os, const Type &o);
  friend istream &operator>>(istream &is, Type &o);
};

namespace std {
template <> struct hash<Type> {
  size_t operator()(const Type &o) const {
    size_t h1 = hash<int>()(o.x), h2 = hash<int>()(o.y);
    return h1 ^ (h2 << 1); // Combine hashes of members
  }
};
} // namespace std

Math

Binary Exponentiation

source: cp-algorithms

Generic binary exponentiation to compute \( b^N \) in \( O(logN) \). Any type with the T * T operator defined can be used. In case the type does not have an identity value simply exponentiate until \( N-1 \) and set the initial value of res to the base.

template <typename T> T binexp(T a, ull b) {
  T res = 1; //@ identity
  while(b > 0) {
    if(b & 1) res = res * a;
    a = a * a;
    b /= 2;
  }
  return res;
}

Dependencies.

typedef unsigned long long ull;
type operator*(const type& a, const type& b);

Computation of Exponents Modulo a Number

source: cp-algorithms

Compute \( x^N mod m \) efficiently. Any type which can be used in the previous binexp can also be used in the modular version, with the additional constraint of needing to define the T % T operator defined.

template <typename T> T binexp(T a, ull b, T m) {
  a = a % m;
  T res = 1;
  while(b > 0) {
    if(b & 1) res = res * a % m;
    a = a * a % m;
    b /= 2;
  }
  return res;
}

Trees