Skip to content

Instantly share code, notes, and snippets.

Avatar

Horace He Chillee

View GitHub Profile
@Chillee
Chillee / LCT.cpp
Last active Oct 26, 2019
Miscellaneous
View LCT.cpp
/**
* Author:
* Description: link-cut Tree. Supports BST-like augmentations. (Can be used in place of HLD).
* Current implementation supports update value at a node, and query max on a path.
* For details about the structure, refer to https://en.wikipedia.org/wiki/Link/cut_tree
* Tested on: http://acm.timus.ru/problem.aspx?num=1553
* Status: Passes existing fuzz tests (with function names modified).
*/
struct Node {
bool flip = 0;
@Chillee
Chillee / factor.h
Last active Apr 30, 2019
Pollard Rho (Factoring algorithm)
View factor.h
ull f(ull x, ull n) { return (mod_mul(x, x, n) + 1) % n; }
ull Pollard(ull n) {
if (isPrime(n)) return n;
if (!(n & 1)) return 2;
for(int i = 1; i < 50; i++) {
ull x = i, y = f(x, n), p = __gcd(n + y - x, n);
while (p == 1)
x = f(x, n), y = f(f(y, n), n), p = __gcd(n + y - x, n);
if (p == n) continue;
return p;
@Chillee
Chillee / fft.cpp
Created Apr 23, 2019
Educational implementations
View fft.cpp
typedef complex<double> cpx;
typedef vector<cpx> Poly;
typedef vector<cpx> Eval;
Eval FFT(Poly P) {
int n = P.size();
if (n == 1)
return P;
Poly P_even(n / 2), P_odd(n / 2);
for (int j = 0; j < n / 2; j++) {
P_even[j] = P[j * 2]; // Put all the even terms (2*0, 2*1, 2*2,...) in one polynomial
@Chillee
Chillee / crt.cpp
Created Apr 13, 2019
Chinese Remainder Theorem
View crt.cpp
ll chinese(ll a, ll m, ll b, ll n) { //x = a %m, x = b%n, gcd(m,n)=1
ll x, y;
euclid(m, n, x, y);
ll ret = a * (y + m) % m * n + b * (x + n) % n * m;
if (ret >= m * n)
ret -= m * n;
return ret;
}
ll chinese_common(ll a, ll m, ll b, ll n) { // gcd(m,n) != 1
ll d = __gcd(m, n);
@Chillee
Chillee / BerlekampMassey.cpp
Created Apr 4, 2019
Linear Recurrence (Berlekamp Massey, K-th term)
View BerlekampMassey.cpp
vector<ll> BerlekampMassey(vector<ll> s) {
int n = s.size(), L = 0, m = 0;
vector<ll> C(n), B(n), T;
C[0] = B[0] = 1;
ll b = 1;
for (int i = 0; i < n; i++) {
m++;
ll d = s[i] % MOD;
for (int j = 1; j < L + 1; j++)
@Chillee
Chillee / min_rotation.cpp
Last active Apr 4, 2019
Minimum Rotation: O(N)
View min_rotation.cpp
int min_rotation(string s) {
int a = 0, N = s.size();
s += s;
for (int b = 0; b < N; b++)
for (int i = 0; i < N; i++) {
if (a + i == b || s[a + i] < s[b + i]) {
b += max(0, i - 1);
break;
}
if (s[a + i] > s[b + i]) {
@Chillee
Chillee / benchmark.cpp
Created Apr 2, 2019
Benchmarking utilities
View benchmark.cpp
struct timeit {
decltype(chrono::high_resolution_clock::now()) begin;
const string label;
timeit(string label = "???") : label(label) { begin = chrono::high_resolution_clock::now(); }
~timeit() {
auto end = chrono::high_resolution_clock::now();
auto duration = chrono::duration_cast<chrono::milliseconds>(end - begin).count();
cerr << duration << "ms elapsed [" << label << "]" << endl;
}
};
View fread_gc.cpp
struct GC {
char buf[1 << 16 | 1];
int bc = 0, be = 0;
char operator()() {
if (bc >= be) {
be = fread(buf, 1, sizeof(buf) - 1, stdin);
buf[be] = bc = 0;
}
return buf[bc++];
}
@Chillee
Chillee / diameter.cpp
Last active Apr 4, 2019
Tree Diameter: O(N)
View diameter.cpp
int dfs(int cur, int prv = -1, int d = 0) {
dist[cur] = d;
int mx = cur;
for (auto i : adj[cur]) {
if (i == prv)
continue;
int res = dfs(i, cur, d + 1);
if (dist[res] > dist[mx])
mx = res;
}
View const_intervals.cpp
void rec(int from, int to, function<int(int)> f, int &i, int &p, int q, vector<array<int, 3>> &ints) {
if (p == q)
return;
if (from == to) {
ints.push_back({i, to, p});
i = to;
p = q;
} else {
int mid = (from + to) >> 1;
rec(from, mid, f, i, p, f(mid), ints);
You can’t perform that action at this time.