Skip to content

Instantly share code, notes, and snippets.

View GoBigorGoHome's full-sized avatar

Pat GoBigorGoHome

9 followers · 75 following
View GitHub Profile
@GoBigorGoHome
GoBigorGoHome / 【模板】后缀数组.cpp
Last active March 22, 2020 12:38
// 要求T具有<运算符
template <typename T>
void sort_suffix(const T *s, int n, vector<int>& suf, vector<int>& h) {
assert(SZ(suf) >= n && SZ(h) >= n);
vector<int> rank(n);
iota(all(suf), 0);
sort(all(suf), [s](int x, int y) { return s[x] < s[y]; });
rank[suf[0]] = 0;
for (int i = 1; i < n; ++i) {
rank[suf[i]] = rank[suf[i - 1]] + (s[suf[i - 1]] < s[suf[i]]);
@GoBigorGoHome
GoBigorGoHome / ctz_clz.cpp
Created December 11, 2019 03:07 — forked from pps83/ctz_clz.cpp
__builtin_ctz (ctzl, ctzll) and __builtin_clz (clzl, clzll) for Visual Studio
#ifdef _MSC_VER
#include <intrin.h>
static inline int __builtin_ctz(uint32_t x) {
unsigned long ret;
_BitScanForward(&ret, x);
return (int)ret;
}
static inline int __builtin_ctzll(unsigned long long x) {
@GoBigorGoHome
GoBigorGoHome / 【模板】拉格朗日插值求多项式系数.cpp
Last active December 13, 2019 16:54
用Lagrange插值公式求多项式系数。这个实现针对域Fp上的多项式，且p很小（<= 2999）的情形。一般情况下需要注意爆 long long 的问题。来自 ABC137F。
// tourist 的逆元模板
template <typename T>
T inverse(T a, T m) {
T u = 0, v = 1;
while (a != 0) {
T t = m / a;
m -= t * a; swap(a, m);
u -= t * v; swap(u, v);
}
assert(m == 1);
@GoBigorGoHome
GoBigorGoHome / 【模板】单调栈求最大矩形.cpp
Created May 26, 2019 12:01
单调栈求最大矩形
auto solve = [](vi& h, int n) {
vi L(n + 1), R(n + 1);
// 严格递增的单调栈
vpii inc{{0, 0}}; // pair.first 表示高度，pair.second 表示下标。假设 h[0] = -INF。
assert(SZ(inc) == 1);
for (int i = 1; i <= n; i++) {
while (inc.back().first >= h[i]) {
inc.pop_back();
}
L[i] = inc.back().second + 1; //左闭
@GoBigorGoHome
GoBigorGoHome / 【模板】最小费用最大流.cpp
Last active November 8, 2019 15:47
封装成一个类。连续最短路算法：Dijkstra/SPFA + DFS 多路增广（precondition：初始网络中没有负圈）
class MCMF {
struct arc {
const int to, next, cost;
mutable int cap;
};
const int n_node;
vi head;
vector<arc> e;
mutable vi d;
@GoBigorGoHome
GoBigorGoHome / 【模板】mod_int_class_by_tourist.cpp
Last active February 16, 2023 16:53
tourist's modular arithmetic class. https://codeforces.com/contest/1146/submission/53066321
template <typename T>
T inverse(T a, T m) {
T u = 0, v = 1;
while (a != 0) {
T t = m / a;
m -= t * a; swap(a, m);
u -= t * v; swap(u, v);
}
assert(m == 1);
return u;
@GoBigorGoHome
GoBigorGoHome / 【模板】高斯消元.cpp
Last active April 23, 2019 13:04
F_p 上的高斯消元。
/* a tutorial on Gauss-Jordan elimination: https://cp-algorithms.com/linear_algebra/linear-system-gauss.html
From the article:
Strictly speaking, the method described below should be called "Gauss-Jordan", or Gauss-Jordan elimination,
because it is a variation of the Gauss method, described by Jordan in 1887.
*/
using num = modnum<1000003>;
using mat = vv<num>;
using vec = vector<num>;
// precondition: 系数矩阵不含0，否则需要选主元。
@GoBigorGoHome
GoBigorGoHome / 【模板】树链剖分.cpp
Created April 15, 2019 17:31
树链剖分（HLD）模板
// BEGIN 树剖模板
vi g[N];
int fa[N];
int sz[N];
int heavy_son[N];
int dep[N];
void dfs(int u, int f) {
fa[u] = f;
sz[u] = 1;
@GoBigorGoHome
GoBigorGoHome / transitive-closure-Tarjan-SCC-bitset.cpp
Created April 3, 2019 05:41
任意有向图求传递闭包。Tarjan SCC + bitset 优化。
const int nax = 10005;
vector<int> g[nax];
int scc_id[nax];
int dn[nax]; // dfs_no
int dfs_clock;
int low[nax];
bitset<nax> bs[nax];
vector<bool> in_stack(nax);
stack<int> stk;
@GoBigorGoHome
GoBigorGoHome / 【模板】AC自动机.cpp
Last active April 7, 2020 03:05
/*** 朴素AC自动机 ***/
struct node {
static const int sigma_size = 2;
array<int, sigma_size> pos{};
bool is_accept_state = false;
int suffix_pos = 0;
};
vector<node> trie;
void insert(const int* s, int len) {