算法模板

快速输入输出

使用前进行初始化 IO.init()，在 freopen 后。

• read() 读入 int，read<long long>() 读入 long long。
• read(a, b, c, ...)
• write(a) 输出并换行，write(a, ' ') 输出并加空格。

struct IO {
    static const int inSZ = 1 << 17;
    char inBuf[inSZ], *in1, *in2;
    template<class T> inline __attribute((always_inline))
    T read() {
        if (in1 > inBuf + inSZ - 32) [[unlikely]] {
            auto len = in2 - in1;
            memcpy(inBuf, in1, len);
            in1 = inBuf, in2 = inBuf + len;
            in2 += fread(in2, 1, inSZ - len, stdin);
            if (in2 != inBuf + inSZ) *in2 = 0;
        }
        T res = 0;
        unsigned char c;
        bool neg = 0;
        while ((c = *in1++) < 48) neg = c == 45;
        while (res = res * 10 + (c - 48), (c = *in1++) >= 48);
        return neg ? -res : res;
    }
    static const int outSZ = 1 << 21;
    char outBuf[outSZ], *out;
    template<class T> inline __attribute((always_inline))
    void write(T x) {
        if (out > outBuf + outSZ - 32) [[unlikely]]
            fwrite(outBuf, 1, out - outBuf, stdout), out = outBuf;
        if (!x) return *out++ = 48, void();
        if (x < 0) *out++ = 45, x = -x;
        alignas(2) const char* digits =
        "0001020304050607080910111213141516171819"
        "2021222324252627282930313233343536373839"
        "4041424344454647484950515253545556575859"
        "6061626364656667686970717273747576777879"
        "8081828384858687888990919293949596979899";
        alignas(64) static char buf[20];
        char* p = buf + 20;
        while (x >= 10) memcpy(p -= 2, digits + x % 100 * 2, 2), x /= 100;
        if (x) *--p = 48 + x;
        auto len = buf + 20 - p;
        memcpy(out, p, len), out += len;
    }
    void init() {
        in1 = in2 = inBuf + inSZ;
        out = outBuf;
    }
    ~IO() { fwrite(outBuf, 1, out - outBuf, stdout); }
} IO;
template<class T = int> inline T read() {
    return IO.read<T>();
}
template<class... Args> inline void read(Args&... args) {
    ((args = IO.read<Args>()), ...);
}
template<class T> inline void write(T x, char c = '\n') {
    IO.write(x), *IO.out++ = c;
}

自动取模类型 modint

实现同 AC Library，文档。

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using u32 = uint32_t;
using u64 = uint64_t;

constexpr ll safe_mod(ll x, ll m) {
    return x %= m, x < 0 ? x + m : x;
}
constexpr ll pow_mod_constexpr(ll x, ll n, int m) {
    if (m == 1) return 0;
    u32 _m = m;
    u64 r = 1, _x = safe_mod(x, m);
    for (; n; n >>= 1, _x = _x * _x % _m)
    if (n & 1) r = r * _x % m;
    return r;
}
constexpr bool is_prime_constexpr(int n) {
    if (n <= 1) return false;
    if (n == 2 || n == 7 || n == 61) return true;
    if (n % 2 == 0) return false;
    ll d = n - 1;
    while (~d & 1) d >>= 1;
    for (ll a : {2, 7, 61}) {
        ll t = d, y = pow_mod_constexpr(a, t, n);
        while (t != n - 1 && y != 1 && y != n - 1)
            y = y * y % n, t <<= 1;
        if (y != n - 1 && t % 2 == 0) return false;
    }
    return true;
}
constexpr pair<ll, ll> inv_gcd(ll a, ll b) {
    a = safe_mod(a, b);
    if (a == 0) return {b, 0};
    ll s = b, t = a, m0 = 0, m1 = 1;
    while (t) {
        ll u = s / t;
        s -= t * u, m0 -= m1 * u;
        ll tmp = s;
        s = t, t = tmp, tmp = m0, m0 = m1, m1 = tmp;
    }
    if (m0 < 0) m0 += b / s;
    return {s, m0};
}
struct barrett {
    u32 m; u64 im;
    barrett(u32 m) :m(m), im(~0ull / m + 1) {}
    u32 mul(u32 a, u32 b) const {
        u64 z = (u64)a * b;
        u64 x = (__uint128_t)z * im >> 64;
        u32 v = z - x * m;
        return (int)v < 0 ? v + m : v;
    }
};
template<int m> struct static_modint {
    using mint = static_modint;
  public:
    static mint raw(int v) {
        mint x;
        return x._v = v, x;
    }
    static_modint() : _v(0) {}
    template<class T> static_modint(T v) {
        ll x = v % m;
        _v = x < 0 ? x + m : x;
    }
    u32 val() const { return _v; }
    mint& operator++() {
        if (++_v == m) _v = 0;
        return *this;
    }
    mint& operator--() {
        if (!_v--) _v = m - 1;
        return *this;
    }
    mint operator++(int) {
        mint res = *this;
        ++*this;
        return res;
    }
    mint operator--(int) {
        mint res = *this;
        --*this;
        return res;
    }
    mint& operator+=(const mint& rhs) {
        _v += rhs._v;
        if (_v >= m) _v -= m;
        return *this;
    }
    mint& operator-=(const mint& rhs) {
        _v -= rhs._v;
        if (_v >= m) _v += m;
        return *this;
    }
    mint& operator*=(const mint& rhs) {
        u64 z = _v;
        z *= rhs._v, _v = z % m;
        return *this;
    }
    mint& operator/=(const mint& rhs) { return *this = *this * rhs.inv(); }
    mint operator+() const { return *this; }
    mint operator-() const { return mint() - *this; }

    mint pow(ll n) const {
        assert(0 <= n);
        mint x = *this, r = 1;
        for (; n; n >>= 1, x *= x) if (n & 1) r *= x;
        return r;
    }
    mint inv() const {
        if (prime) {
            assert(_v);
            return pow(m - 2);
        } else {
            auto eg = inv_gcd(_v, m);
            assert(eg.first == 1);
            return eg.second;
        }
    }

    friend mint operator+(const mint& lhs, const mint& rhs) {
        return mint(lhs) += rhs;
    }
    friend mint operator-(const mint& lhs, const mint& rhs) {
        return mint(lhs) -= rhs;
    }
    friend mint operator*(const mint& lhs, const mint& rhs) {
        return mint(lhs) *= rhs;
    }
    friend mint operator/(const mint& lhs, const mint& rhs) {
        return mint(lhs) /= rhs;
    }
    friend bool operator==(const mint& lhs, const mint& rhs) {
        return lhs._v == rhs._v;
    }
    friend bool operator!=(const mint& lhs, const mint& rhs) {
        return lhs._v != rhs._v;
    }

  private:
    u32 _v;
    static constexpr bool prime = is_prime_constexpr(m);
};

template<int id> struct dynamic_modint {
    using mint = dynamic_modint;

  public:
    static int mod() { return bt.m; }
    static void set_mod(int m) {
        assert(1 <= m), bt = barrett(m);
    }
    static mint raw(int v) {
        mint x;
        return x._v = v, x;
    }

    dynamic_modint() : _v(0) {}
    template<class T> dynamic_modint(T v) {
        ll x = v % (int)bt.m;
        _v = x < 0 ? x + bt.m : x;
    }

    u32 val() const { return _v; }

    mint& operator++() {
        if (++_v == bt.m) _v = 0;
        return *this;
    }
    mint& operator--() {
        if (!_v--) _v = bt.m - 1;
        return *this;
    }
    mint operator++(int) {
        mint res = *this;
        ++*this;
        return res;
    }
    mint operator--(int) {
        mint res = *this;
        --*this;
        return res;
    }

    mint& operator+=(const mint& rhs) {
        _v += rhs._v;
        if (_v >= bt.m) _v -= bt.m;
        return *this;
    }
    mint& operator-=(const mint& rhs) {
        _v += bt.m - rhs._v;
        if (_v >= bt.m) _v -= bt.m;
        return *this;
    }
    mint& operator*=(const mint& rhs) {
        _v = bt.mul(_v, rhs._v);
        return *this;
    }
    mint& operator/=(const mint& rhs) { return *this = *this * rhs.inv(); }

    mint operator+() const { return *this; }
    mint operator-() const { return mint() - *this; }

    mint pow(ll n) const {
        assert(0 <= n);
        mint x = *this, r = 1;
        for (; n; n >>= 1, x *= x) if (n & 1) r *= x;
        return r;
    }
    mint inv() const {
        auto eg = inv_gcd(_v, bt.m);
        assert(eg.first == 1);
        return eg.second;
    }

    friend mint operator+(const mint& lhs, const mint& rhs) {
        return mint(lhs) += rhs;
    }
    friend mint operator-(const mint& lhs, const mint& rhs) {
        return mint(lhs) -= rhs;
    }
    friend mint operator*(const mint& lhs, const mint& rhs) {
        return mint(lhs) *= rhs;
    }
    friend mint operator/(const mint& lhs, const mint& rhs) {
        return mint(lhs) /= rhs;
    }
    friend bool operator==(const mint& lhs, const mint& rhs) {
        return lhs._v == rhs._v;
    }
    friend bool operator!=(const mint& lhs, const mint& rhs) {
        return lhs._v != rhs._v;
    }

  private:
    u32 _v;
    static barrett bt;
};
template<int id> barrett dynamic_modint<id>::bt = 998244353;

using mint = static_modint<998244353>;

istream& operator >> (istream& is, mint& a) {
    int v;
    is >> v, a = mint::raw(v);
    return is;
}
ostream& operator << (ostream& os, mint a) {
    return os << a.val();
}

NTT 系列

经典版

const int P = 998244353;

int add(int a, int b) { return (a += b) < P ? a : a - P; }
int sub(int a, int b) { return (a -= b) < 0 ? a + P : a; }
int mul(int a, int b) { return (uint64_t)(uint32_t)a * (uint32_t)b % P; }
int ceil2(int n) { return n ? 2 << __builtin_ia32_bsrsi(n) : 0; }
int Pow(int a, int n) {
    int r = 1;
    for (; n; n >>= 1, a = mul(a, a))
        if (n & 1) r = mul(r, a);
    return r;
}
struct precalc {
    int w[23], iw[23];
    precalc() {
        int e[22], ie[22], now = 15311432, inow = 469870224;
        for (int i = 21; i >= 0; i--) {
            e[i] = now, ie[i] = inow;
            now = mul(now, now), inow = mul(inow, inow);
        }
        now = inow = 1;
        for (int i = 0; i <= 21; i++) {
            w[i] = mul(e[i], now), iw[i] = mul(ie[i], inow);
            now = mul(now, ie[i]), inow = mul(inow, e[i]);
        }
    }
} pre;
void DIF(int a[], int n) {
    for (int i = n >> 1; i; i >>= 1) {
        int now = 1;
        for (int j = 0; j < n / 2 / i; j++) {
            int p = j * i * 2;
            for (int k = p; k < p + i; k++) {
                int x = a[k], y = mul(a[k + i], now);
                a[k] = add(x, y), a[k + i] = sub(x, y);
            }
            now = mul(now, pre.w[__builtin_ctz(j + 1)]);
        }
    }
}
void IDIF(int a[], int n) {
    for (int i = 1; i < n; i <<= 1) {
        int now = 1;
        for (int j = 0; j < n / 2 / i; j++) {
            int p = j * i * 2;
            for (int k = p; k < p + i; k++) {
                int x = a[k], y = a[k + i];
                a[k] = add(x, y), a[k + i] = mul(x - y + P, now);
            }
            now = mul(now, pre.iw[__builtin_ctz(j + 1)]);
        }
    }
    int inv = Pow(n, P - 2);
    for (int i = 0; i < n; i++) a[i] = mul(a[i], inv);
}

经典版 (modint)

int ceil2(int n) { return n ? 2 << __builtin_ia32_bsrsi(n) : 1; }
struct precalc {
    mint w[23], iw[23];
    precalc() {
        mint e[22], ie[22], now = 15311432, inow = 469870224;
        for (int i = 21; i >= 0; i--) {
            e[i] = now, ie[i] = inow;
            now *= now, inow *= inow;
        }
        now = inow = 1;
        for (int i = 0; i <= 21; i++) {
            w[i] = e[i] * now, iw[i] = ie[i] * inow;
            now *= ie[i], inow *= e[i];
        }
    }
} pre;
void DIF(mint a[], int n) {
    for (int i = n >> 1; i; i >>= 1) {
        mint now = 1;
        for (int j = 0; j < n / 2 / i; j++) {
            int p = j * i * 2;
            for (int k = p; k < p + i; k++) {
                mint x = a[k], y = a[k + i] * now;
                a[k] = x + y, a[k + i] = x - y;
            }
            now *= pre.w[__builtin_ctz(j + 1)];
        }
    }
}
void IDIF(mint a[], int n) {
    for (int i = 1; i < n; i <<= 1) {
        mint now = 1;
        for (int j = 0; j < n / 2 / i; j++) {
            int p = j * i * 2;
            for (int k = p; k < p + i; k++) {
                mint x = a[k], y = a[k + i];
                a[k] = x + y, a[k + i] = (x - y) * now;
            }
            now *= pre.iw[__builtin_ctz(j + 1)];
        }
    }
    mint inv = mint(n).inv();
    for (int i = 0; i < n; i++) a[i] *= inv;
}

任意模数 NTT

using cplx = complex<double>;

const int N = /**/;
const double PI = acos(-1);

int rev[N];
cplx w[N];

void FFT(cplx a[], int n, bool t) {
    for (int i = 0; i < n; i++)
        if (i < rev[i]) swap(a[i], a[rev[i]]);
    for (int i = 1; i < n; i <<= 1)
        for (int j = 0; j < n; j += i << 1)
            for (int k = j; k < j + i; k++) {
                cplx x = a[k], y = a[k + i] * w[i + k - j];
                a[k] = x + y, a[k + i] = x - y;
            }
    if (t) return;
    reverse(a + 1, a + n);
    double inv = 1.0 / n;
    for (int i = 0; i < n; i++) a[i] *= inv;
}
void FFT2(cplx a[], cplx b[], int n) {
    for (int i = 0; i < n; i++) a[i] += b[i] * 1i;
    FFT(a, n, 1);
    b[0] = conj(a[0]);
    for (int i = 1; i < n; i++) b[i] = conj(a[n - i]);
    for (int i = 0; i < n; i++) {
        cplx x = a[i], y = b[i];
        a[i] = (y + x) * 0.5, b[i] = (y - x) * 0.5i;
    }
}
void mul(int n, int m, int P, int a[], int b[], int c[]) {
    static cplx a0[N], a1[N], b0[N], b1[N]; 
    int M = sqrt(P);
    for (int i = 0; i <= n; i++)
        a0[i] = a[i] / M, a1[i] = a[i] % M;
    for (int i = 0; i <= m; i++)
        b0[i] = b[i] / M, b1[i] = b[i] % M;
    int lim = 2 << __builtin_ia32_bsrsi(n + m);
    for (int i = 0; i < lim; i++)
        rev[i] = rev[i >> 1] >> 1 | (i & 1 ? lim >> 1 : 0);
    for (int i = 1; i < lim; i <<= 1)
        for (int j = 0; j < i; j++)
            w[i + j] = cplx(cos(PI / i * j), sin(PI / i * j));
    FFT2(a0, a1, lim), FFT2(b0, b1, lim);
    for (int i = 0; i < lim; i++) {
        cplx t = a0[i] + a1[i] * 1i;
        b0[i] *= t, b1[i] *= t;
    }
    FFT(b0, lim, 0), FFT(b1, lim, 0);
    for (int i = 0; i <= n + m; i++) {
        using u64 = uint64_t;
        u64 high = M * u64(real(b0[i]) + 0.5) + u64(imag(b0[i]) + 0.5);
        u64 low = M * u64(real(b1[i]) + 0.5) + u64(imag(b1[i]) + 0.5);
        c[i] = (high % P * M + low) % P;
    }
    for (int i = 0; i < lim; i++)
        a0[i] = a1[i] = b0[i] = b1[i] = 0;
}

任意模数 NTT (modint)

using cplx = complex<double>;

const int N = /**/;
const double PI = acos(-1);

int rev[N];
cplx w[N];

void FFT(cplx a[], int n, bool t) {
    for (int i = 0; i < n; i++)
        if (i < rev[i]) swap(a[i], a[rev[i]]);
    for (int i = 1; i < n; i <<= 1)
        for (int j = 0; j < n; j += i << 1)
            for (int k = j; k < j + i; k++) {
                cplx x = a[k], y = a[k + i] * w[i + k - j];
                a[k] = x + y, a[k + i] = x - y;
            }
    if (t) return;
    reverse(a + 1, a + n);
    double inv = 1.0 / n;
    for (int i = 0; i < n; i++) a[i] *= inv;
}
void FFT2(cplx a[], cplx b[], int n) {
    for (int i = 0; i < n; i++) a[i] += b[i] * 1i;
    FFT(a, n, 1);
    b[0] = conj(a[0]);
    for (int i = 1; i < n; i++) b[i] = conj(a[n - i]);
    for (int i = 0; i < n; i++) {
        cplx x = a[i], y = b[i];
        a[i] = (y + x) * 0.5, b[i] = (y - x) * 0.5i;
    }
}
void mul(int n, int m, mint a[], mint b[], mint c[]) {
    static cplx a0[N], a1[N], b0[N], b1[N];
    int M = sqrt(mint::mod());
    for (int i = 0; i <= n; i++)
        a0[i] = a[i].val() / M, a1[i] = a[i].val() % M;
    for (int i = 0; i <= m; i++)
        b0[i] = b[i].val() / M, b1[i] = b[i].val() % M;
    int lim = 2 << __builtin_ia32_bsrsi(n + m);
    for (int i = 0; i < lim; i++)
        rev[i] = rev[i >> 1] >> 1 | (i & 1 ? lim >> 1 : 0);
    for (int i = 1; i < lim; i <<= 1)
        for (int j = 0; j < i; j++)
            w[i + j] = cplx(cos(PI / i * j), sin(PI / i * j));
    FFT2(a0, a1, lim), FFT2(b0, b1, lim);
    for (int i = 0; i < lim; i++) {
        cplx t = a0[i] + a1[i] * 1i;
        b0[i] *= t, b1[i] *= t;
    }
    FFT(b0, lim, 0), FFT(b1, lim, 0);
    for (int i = 0; i <= n + m; i++) {
        using u64 = uint64_t;
        u64 high = M * u64(real(b0[i]) + 0.5) + u64(imag(b0[i]) + 0.5);
        u64 low = M * u64(real(b1[i]) + 0.5) + u64(imag(b1[i]) + 0.5);
        c[i] = high % mint::mod() * M + low;
    }
    for (int i = 0; i < lim; i++)
        a0[i] = a1[i] = b0[i] = b1[i] = 0;
}

多项式求逆

const int P = 998244353;
const int N = /**/;

inline int add(int a, int b) { return (a += b) < P ? a : a - P; }
inline int sub(int a, int b) { return (a -= b) < 0 ? a + P : a; }
inline int mul(int a, int b) { return (uint64_t)(uint32_t)a * (uint32_t)b % P; }
inline int ceil2(int n) { return 2 << __builtin_ia32_bsrsi(n); }
int Pow(int a, int n) {
    int r = 1;
    for (; n; n >>= 1, a = mul(a, a))
        if (n & 1) r = mul(r, a);
    return r;
}
struct precalc {
    int w[23], iw[23];
    precalc() {
        int e[22], ie[22], now = 15311432, inow = 469870224;
        for (int i = 21; i >= 0; i--) {
            e[i] = now, ie[i] = inow;
            now = mul(now, now), inow = mul(inow, inow);
        }
        now = inow = 1;
        for (int i = 0; i <= 21; i++) {
            w[i] = mul(e[i], now), iw[i] = mul(ie[i], inow);
            now = mul(now, ie[i]), inow = mul(inow, e[i]);
        }
    }
} pre;
void DIF(int a[], int n) {
    for (int i = n >> 1, l = 1; i; i >>= 1, l <<= 1) {
        int now = 1;
        for (int j = 0; j < l; j++) {
            int p = j * i * 2;
            for (int k = p; k < p + i; k++) {
                int x = a[k], y = mul(a[k + i], now);
                a[k] = add(x, y), a[k + i] = sub(x, y);
            }
            now = mul(now, pre.w[__builtin_ctz(j + 1)]);
        }
    }
}
void IDIF(int a[], int n) {
    for (int i = 1, l = n >> 1; l; i <<= 1, l >>= 1) {
        int now = 1;
        for (int j = 0; j < l; j++) {
            int p = j * i * 2;
            for (int k = p; k < p + i; k++) {
                int x = a[k], y = a[k + i];
                a[k] = add(x, y), a[k + i] = mul(x - y + P, now);
            }
            now = mul(now, pre.iw[__builtin_ctz(j + 1)]);
        }
    }
    int inv = Pow(n, P - 2);
    for (int i = 0; i < n; i++) a[i] = mul(a[i], inv);
}
void polyInv(int n, int a[], int b[]) {
    static int c[N];
    int lim = ceil2(n);
    memset(b, 0, lim * 8);
    b[0] = 1;
    for (int k = 1; k < lim; k <<= 1) {
        memcpy(c, a, k * 8);
        DIF(b, k * 4), DIF(c, k * 4);
        for (int i = 0; i < k * 4; i++)
            b[i] = mul(b[i], 2 + P - mul(c[i], b[i]));
        IDIF(b, k * 4), memset(b + k * 2, 0, k * 8);
    }
    memset(c, 0, lim * 8);
}

多项式求逆 (modint)

using mint = static_modint<998244353>;
const int N = /**/;

inline int ceil2(int n) { return 2 << __builtin_ia32_bsrsi(n); }
struct precalc {
    mint w[23], iw[23];
    precalc() {
        mint e[22], ie[22], now = 15311432, inow = 469870224;
        for (int i = 21; i >= 0; i--) {
            e[i] = now, ie[i] = inow;
            now *= now, inow *= inow;
        }
        now = inow = 1;
        for (int i = 0; i <= 21; i++) {
            w[i] = e[i] * now, iw[i] = ie[i] * inow;
            now *= ie[i], inow *= e[i];
        }
    }
} pre;
void DIF(mint a[], int n) {
    for (int i = n >> 1, l = 1; i; i >>= 1, l <<= 1) {
        mint now = 1;
        for (int j = 0; j < l; j++) {
            int p = j * i * 2;
            for (int k = p; k < p + i; k++) {
                mint x = a[k], y = a[k + i] * now;
                a[k] = x + y, a[k + i] = x - y;
            }
            now *= pre.w[__builtin_ctz(j + 1)];
        }
    }
}
void IDIF(mint a[], int n) {
    for (int i = 1, l = n >> 1; l; i <<= 1, l >>= 1) {
        mint now = 1;
        for (int j = 0; j < l; j++) {
            int p = j * i * 2;
            for (int k = p; k < p + i; k++) {
                mint x = a[k], y = a[k + i];
                a[k] = x + y, a[k + i] = (x - y) * now;
            }
            now *= pre.iw[__builtin_ctz(j + 1)];
        }
    }
    mint inv = mint(n).inv();
    for (int i = 0; i < n; i++) a[i] *= inv;
}
void polyInv(int n, mint a[], mint b[]) {
    static mint c[N];
    int lim = ceil2(n);
    memset(b, 0, lim * 8);
    b[0] = 1;
    for (int k = 1; k < lim; k <<= 1) {
        memcpy(c, a, k * 8);
        DIF(b, k * 4), DIF(c, k * 4);
        for (int i = 0; i < k * 4; i++)
            b[i] *= 2 - c[i] * b[i];
        IDIF(b, k * 4), memset(b + k * 2, 0, k * 8);
    }
    memset(c, 0, lim * 8);
}

网络流

最大流

const int N = /**/, M = /**/;

int eid, deg[N], G[M << 1], cur[N], d[N];
struct { int v, c; } e[M << 1];

inline void add(int u, int v, int c) {
    deg[u]++, e[eid++] = {v, c};
    deg[v]++, e[eid++] = {u, 0};
}
bool bfs(int s, int t) {
    memcpy(cur, deg, sizeof deg);
    memset(d, 0x3f, sizeof d);
    static int q[N];
    d[t] = 0, q[0] = t;
    for (int L = 0, R = 1; L != R; L++) {
        int u = q[L];
        for (int i = deg[u]; i != deg[u + 1]; i++) {
            int k = G[i], v = e[k].v;
            if (!e[k ^ 1].c | d[v] != 0x3f3f3f3f) continue;
            d[v] = d[u] + 1;
            if (v == s) return true;
            q[R++] = v;
        }
    }
    return false;
}
int dfs(int u, int t, int lim) {
    if (u == t) return lim;
    int dis = d[u], res = 0;
    for (int& i = cur[u]; i != deg[u + 1]; i++) {
        int k = G[i], v = e[k].v, c = e[k].c;
        if (!c | d[v] >= dis) continue;
        int f = dfs(v, t, min(lim, c));
        e[k].c -= f, e[k ^ 1].c += f;
        res += f, lim -= f;
        if (!lim) return res;
    }
    d[u] = 0x3f3f3f3f;
    return res;
}
int maxFlow(int s, int t) {
    partial_sum(deg, deg + N, deg);
    for (int i = 0; i < eid; i += 2) {
        G[--deg[e[i + 1].v]] = i;
        G[--deg[e[i].v]] = i + 1;
    }
    int flow = 0;
    while (bfs(s, t)) flow += dfs(s, t, INT64_MAX);
    return flow;
}

最小费用最大流

const int N = /**/, M = /**/, SZ = /**/;

int eid, deg[N], G[M << 1], d[N], h[N], pre[N];
struct { int v, c, w; } e[M << 1];
uint64_t c[SZ << 1];

inline void add(int u, int v, int c, int w) {
    deg[u]++, e[eid++] = {v, c, w};
    deg[v]++, e[eid++] = {u, 0, -w};
}
inline void push(int i, uint32_t v0) {
    auto v = (uint64_t)v0 << 32 | i;
    for (i += SZ; i; i >>= 1) c[i] = min(c[i], v);
}
inline void pop(int i) {
    uint64_t v = -1;
    for (i += SZ; i; i >>= 1) c[i] = v, v = min(v, c[i ^ 1]);
}
bool dijkstra(int s, int t) {
    memset(c, -1, sizeof c);
    memset(d, 0x3f, sizeof d);
    d[s] = 0, push(s, 0);
    while (~c[1]) {
        int u = c[1];
        auto dis = d[u] + h[u];
        pop(u);
        for (int i = deg[u]; i != deg[u + 1]; i++) {
            int k = G[i], v = e[k].v;
            if (!e[k].c) continue;
            auto w = dis + e[k].w - h[v];
            if (w < d[v]) pre[v] = k ^ 1, d[v] = w, push(v, w);
        }
    }
    return d[t] < d[0];
}
pair<int, int> minCostFlow(int n, int s, int t) {
    for (int i = 1; i <= n; i++) deg[i + 1] += deg[i];
    for (int i = 0; i < eid; i += 2) {
        G[--deg[e[i + 1].v]] = i;
        G[--deg[e[i].v]] = i + 1;
    }
    int flow = 0, cost = 0;
    while (dijkstra(s, t)) {
        for (int i = 1; i <= n; i++) h[i] += d[i];
        int f = 0x3f3f3f3f;
        for (int u = t, k; u != s; u = e[k].v)
            k = pre[u], f = min(f, e[k ^ 1].c);
        for (int u = t, k; u != s; u = e[k].v)
            k = pre[u], e[k ^ 1].c -= f, e[k].c += f;
        flow += f, cost += f * h[t];
    }
    return {flow, cost};
}

最小费用最大流 多路增广

const int N = /**/, M = /**/, SZ = /**/;

int eid, deg[N], G[M << 1], d[N], h[N], pre[N];
struct { int v, c, w; } e[M << 1];
uint64_t c[SZ << 1];
int deg0[N], G0[M << 1];

inline void add(int u, int v, int c, int w) {
    deg[u]++, e[eid++] = {v, c, w};
    deg[v]++, e[eid++] = {u, 0, -w};
}
inline void push(int i, uint32_t v0) {
    auto v = (uint64_t)v0 << 32 | i;
    for (i += SZ; i; i >>= 1) c[i] = min(c[i], v);
}
inline void pop(int i) {
    uint64_t v = -1;
    for (i += SZ; i; i >>= 1) c[i] = v, v = min(v, c[i ^ 1]);
}
bool dijkstra(int s, int t) {
    memset(c, -1, sizeof c);
    memset(d, 0x3f, sizeof d);
    d[s] = 0, push(s, 0);
    while (~c[1]) {
        int u = c[1];
        auto dis = d[u] + h[u];
        pop(u);
        for (int i = deg[u]; i != deg[u + 1]; i++) {
            int k = G[i], v = e[k].v;
            if (!e[k].c) continue;
            auto w = dis + e[k].w - h[v];
            if (w < d[v]) pre[v] = k ^ 1, d[v] = w, push(v, w);
        }
    }
    return d[t] < d[0];
}
bool bfs(int s, int t) {
    static int q[N];
    memset(pre, -1, sizeof pre);
    pre[s] = 0, q[0] = s;
    for (int l = 0, r = 0; l <= r; l++) {
        int u = q[l];
        for (int i = deg0[u]; i != deg0[u + 1]; i++) {
            int k = G0[i], v = e[k].v;
            if ((pre[v] < 0) & (e[k].c != 0)) {
                pre[v] = k ^ 1, q[++r] = v;
                if (v == t) return 1;
            }
        }
    }
    return 0;
}
pair<int, int> minCostFlow(int n, int s, int t) {
    for (int i = 1; i <= n; i++) deg[i + 1] += deg[i];
    for (int i = 0; i < eid; i += 2) {
        G[--deg[e[i + 1].v]] = i;
        G[--deg[e[i].v]] = i + 1;
    }
    int flow = 0, cost = 0;
    while (dijkstra(s, t)) {
        for (int i = 1; i <= n; i++) h[i] += d[i];
        for (int i = 0; i < eid; i += 2) {
            int u = e[i + 1].v, v = e[i].v;
            if (e[i].w == h[v] - h[u])
                deg0[u]++, deg0[v]++;
        }
        for (int i = 1; i <= n; i++) deg0[i + 1] += deg0[i];
        for (int i = 0; i < eid; i += 2) {
            int u = e[i + 1].v, v = e[i].v;
            if (e[i].w == h[v] - h[u])
                G0[--deg0[u]] = i, G0[--deg0[v]] = i + 1;
        }
        do {
            int f = 0x3f3f3f3f;
            for (int u = t, k; u != s; u = e[k].v)
                k = pre[u], f = min(f, e[k ^ 1].c);
            for (int u = t, k; u != s; u = e[k].v)
                k = pre[u], e[k ^ 1].c -= f, e[k].c += f;
            flow += f, cost += f * h[t];
        } while (bfs(s, t));
        memset(deg0, 0, sizeof deg0);
    }
    return {flow, cost};
}

二分图匹配 增光路算法

int n, m, vis[N], mat[N];
vector<int> G[N];

bool dfs(int u, int s) {
    if (vis[u] == s) return 0;
    vis[u] = s;
    for (int v : G[u]) if (!mat[v] || dfs(mat[v], s)) return mat[v] = u, 1;
    return 0;
}
int match() {
    int res = 0;
    for (int i = 1; i <= n; i++) res += dfs(i, i);
    return res;
}

二分图匹配 Hopcroft–Karp

比网络流快，方案存于 mate 数组。

const int N = /**/ + 8, M = /**/ + 8;

int L, R, eid, from[M], to[M], deg[2][N], G[2][M];
int mate[2][N], level[2][N];

bool bfs() {
    static int q[N];
    int l = 0, r = 0;
    memset(level, 0x3f, sizeof level);
    for (int i = 1; i <= R; i++)
        if (!mate[1][i]) level[1][i] = 0, q[r++] = i;
    bool res = false;
    while (l != r) {
        int u = q[l++];
        for (int i = deg[1][u]; i < deg[1][u + 1]; i++) {
            int v = G[1][i];
            if (level[0][v] != 0x3f3f3f3f) continue;
            level[0][v] = level[1][u] + 1;
            if (!(v = mate[0][v])) res = true;
            else level[1][v] = level[1][u] + 2, q[r++] = v;
        }
    }
    return res;
}
bool dfs(int u, int l) {
    for (int i = deg[0][u]; i < deg[0][u + 1]; i++) {
        int x = G[0][i];
        if(level[1][x] >= l) continue;
        level[1][x] = 0x3f3f3f3f;
        int v = mate[1][x];
        if (!v || dfs(v, l - 2))
            return mate[0][u] = x, mate[1][x] = u, true;
    }
    return false;
}
inline void add(int u, int v) {
    deg[0][u]++, from[eid] = u;
    deg[1][v]++, to[eid] = v;
}
int match() {
    for (int i = 1; i <= L; i++) deg[0][i + 1] += deg[0][i];
    for (int i = 1; i <= R; i++) deg[1][i + 1] += deg[1][i];
    for (int i = 0; i < eid; i++) {
        G[0][--deg[0][from[i]]] = to[i];
        G[1][--deg[1][to[i]]] = from[i];
    }
    int ans = 0;
    while (bfs()) for (int i = 1; i <= L; i++)
        if (!mate[0][i] & level[0][i] != 0x3f3f3f3f)
            ans += dfs(i, level[0][i]);
    return ans;
}

数论相关

min25 筛 质数计数

#define rep(i, l, r) for(int i = (l); i <= (r); i++)
#define per(i, r, l) for(int i = (r); i >= (l); i--)
ll f1[N], f2[N];

ll min25(ll n) {
    int lim = sqrt(n);
    rep(i, 1, lim) f1[i] = i - 1, f2[i] = n / i - 1;
    rep(p, 2, lim) if (f1[p] != f1[p - 1]) {
        int w1 = lim / p;
        ll x = f1[p - 1], w3 = (ll)p * p, w2 = min((ll)lim, n / w3), d = n / p;
        rep(i, 1, w1) f2[i] -= f2[i * p] - x;
        rep(i, w1 + 1, w2) f2[i] -= f1[d / i] - x;
        for (int i = lim; i >= w3; i++)
        per(i, lim, w3) f1[i] -= f1[i / p] - x;
    }
    return f2[1];
}

exBSGS

map<int, int> mp;

int BSGS(ll pls, ll a, ll b, int p) {
    pls %= p, a %= p, b %= p; mp.clear();
    ll m = ceil(sqrt(p)), ls = 1, rs = 1;
    for (int i = 0; i < m; i++) mp[ls * b % p] = i, ls = ls * a % p;
    for (int i = 1; i <= m; i++) {
        rs = rs * ls % p;
        if (mp.count(rs * pls % p)) return i * m - mp[rs * pls % p];
    }
    return -1;
}
int exBSGS(int a, int b, int p) {
    a %= p, b %= p;
    int pls = 1, cnt = 0, g;
    while ((g = __gcd(a, p)) > 1) {
        if (b == pls) return cnt;
        if (b % g) return -1;
        p /= g, b /= g, pls = pls * ll(a / g) % p, cnt++;
    }
    int ret = BSGS(pls, a, b, p);
    return ~ret ? ret + cnt : -1;
}

cipolla

int n; ll II;
struct cplx {
    ll r, i;
    cplx operator *(const cplx& b) {
        return {(r * b.r + i * b.i % P * II) % P, (r * b.i + i * b.r) % P};
    }
} U = {1, 0};

int pow1(ll a, int n, ll r = 1) {
    for (; n; n >>= 1, a = a * a % P)
    if (n & 1) r = r * a % P;
    return r;
}
cplx pow2(cplx a, int n, cplx r = U) {
    for (; n; n >>= 1, a = a * a)
    if (n & 1) r = r * a;
    return r;
}
int cipolla(int n) {
    if (!n) return 0;
    if (P == 2) return n;
    if (pow1(n, P / 2) != 1) return -1;
    static mt19937 gen;
    ll a;
    do a = gen() % P, II = (a * a - n + P) % P; while (pow1(II, P / 2) == 1);
    return pow2({a, 1}, P / 2 + 1).r;
}

cipolla(modint)

mint n, II;
struct cplx {
    mint r, i;
    cplx operator *(const cplx& b) {
        return {r * b.r + i * b.i * II, r * b.i + i * b.r};
    }
} U = {1, 0};

cplx Pow(cplx a, int n, cplx r = U) {
    for (; n; n >>= 1, a = a * a)
    if (n & 1) r = r * a;
    return r;
}
int cipolla(mint n) {
    if (n == 0) return 0;
    if (P == 2) return n.val();
    if (n.pow(P / 2) != 1) return -1;
    mint a;
    do a = rand(), II = a * a - n; while (a == 0 || II.pow(P / 2) == 1);
    return Pow({a, 1}, P / 2 + 1).r.val();
}

Miller Rabin & Pollard Rho 质因数分解

vector<ll> prime;

inline ll mul(ll a, ll b, ll p) {
    ll c = a * b - ll((long double)a * b / p + 0.5) * p;
    return c < 0 ? c + p : c;
}
ll Pow(ll a, ll n, ll p) {
    ll r = 1;
    for (; n; n >>= 1, a = mul(a, a, p))
        if (n & 1) r = mul(r, a, p);
    return r;
}
bool check(ll n) {
    ll d = n - 1 >> __builtin_ctzll(n - 1);
    for (ll a : {2, 3, 5, 7, 11, 13, 17, 19, 23}) {
        if (a == n) return 1;
        ll t = d, x = Pow(a, d, n);
        if (x == 1) continue;
        while (t != n - 1 & x != 1 & x != n - 1)
            x = mul(x, x, n), t <<= 1;
        if (x != n - 1) return 0;
    }
    return 1;
}
ll find(ll n) {
    static mt19937_64 gen;
    ll x = gen() % n;
    for (int L = 128;; L <<= 1) {
        ll y = x;
        for (int i = 0; i < L; i += 128) {
            ll z = x, p = 1;
            for (int j = 0; j < 128; j++) {
                x = mul(x, x, n) + 1;
                p = mul(p, abs(x - y), n);
            }
            if (gcd(p, n) == 1) continue;
            for (int j = 0; j < 128; j++) {
                z = mul(z, z, n) + 1;
                ll g = gcd(abs(z - y), n);
                if (g > 1) return g;
            }
        }
    }
}
void factorize(ll n) {
    if (n == 1) return;
    if (check(n)) return prime.push_back(n);
    ll d;
    do d = find(n); while (d == n);
    factorize(d), factorize(n / d);
}

数据结构

pbds::tree

#include <bits/extc++.h>

using namespace __gnu_pbds;

template<class T> using pbds_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<class K, class V> using pbds_map = tree<K, V, less<K>, rb_tree_tag, tree_order_statistics_node_update>;

// insert, erase 同 STL
// order_of_key
// find_by_order
// copy_from_range

Treap

struct { int l, r, s; } c[N];

inline void pu(int o) {
    c[o].s = c[c[o].l].s + c[c[o].r].s + 1;
}
void split(int o, int k, int& u, int& v) {
    if (!o) u = v = 0;
    else if (k <= c[c[o].l].s) split(c[v = o].l, k, u, c[o].l), pu(o);
    else split(c[u = o].r, k - c[c[o].l].s - 1, c[o].r, v), pu(o);
}
int merge(int u, int v) {
    static mt19937 gen;
    if (!u || !v) return u + v;
    if (gen() % (c[u].s + c[v].s) < c[u].s)
        return c[u].r = merge(c[u].r, v), pu(u), u;
    return c[v].l = merge(u, c[v].l), pu(v), v;
}
int build(int l, int r) {
    if (l > r) return 0;
    int m = l + r >> 1;
    c[m].s = r - l + 1;
    c[m].l = build(l, m - 1);
    c[m].r = build(m + 1, r);
    return m;
}

可持久化 Treap

#include <cstdio>
#include <limits>
#include <vector>
using namespace std;

typedef long long int64;

inline int64 Fingerprint(int64 x) {
    const int64 kMul = 0x9ddfea08eb382d69ULL;
    x *= kMul, x ^= x >> 47;
    x *= kMul, x ^= x >> 47;
    x *= kMul, x ^= x >> 47;
    return x * kMul;
}

inline int64 Random() {
    static int64 Seed = 2;
    Seed += Fingerprint(Seed);
    return Seed & numeric_limits<int64>::max();
}

typedef int DataType;

struct RBST {
    RBST *ChildL, *ChildR;
    int Size;
    DataType Data;

    RBST() { ChildL = ChildR = 0; }
};

int GetSize(const RBST* root) { return root ? root->Size : 0; }

int LowerBoundIndex(const RBST* root, DataType x) {
    if (!root) return 0;
    if (x <= root->Data) return LowerBoundIndex(root->ChildL, x);
    int sizeL = GetSize(root->ChildL);
    return LowerBoundIndex(root->ChildR, x) + sizeL + 1;
}

DataType Select(const RBST* root, int index) {
    int sizeL = GetSize(root->ChildL);
    if (index == sizeL) return root->Data;
    if (index < sizeL) return Select(root->ChildL, index);
    return Select(root->ChildR, index - sizeL - 1);
}

RBST* SetSize(RBST* root) {
    root->Size = GetSize(root->ChildL) + GetSize(root->ChildR) + 1;
    return root;
}

struct RBSTree {
    vector<RBST*> Nodes;

    RBST* NewNode(RBST* node) {
        Nodes.push_back(new RBST(*node));
        return Nodes.back();
    }

    void Split(RBST* root, DataType x, RBST*& treeL, RBST*& treeR) {
        if (!root) {
            treeL = treeR = 0;
        } else if (x <= root->Data) {
            RBST *newRoot = NewNode(root);
            Split(root->ChildL, x, treeL, newRoot->ChildL);
            treeR = SetSize(newRoot);
        } else {
            RBST* newRoot = NewNode(root);
            Split(root->ChildR, x, newRoot->ChildR, treeR);
            treeL = SetSize(newRoot);
        }
    }

    RBST* Join(RBST* treeL, RBST* treeR) {
        int sizeL = GetSize(treeL);
        int sizeR = GetSize(treeR);
        int size = sizeL + sizeR;
        if (size == 0) return 0;
        if (Random() % size < sizeL) {
            RBST* newRoot = NewNode(treeL);
            newRoot->ChildR = Join(treeL->ChildR, treeR);
            return SetSize(newRoot);
        } else {
            RBST* newRoot = NewNode(treeR);
            newRoot->ChildL = Join(treeL, treeR->ChildL);
            return SetSize(newRoot);
        }
    }

    RBST* InsertAsRoot(RBST* root, DataType item) {
        Nodes.push_back(new RBST);
        RBST *newRoot = Nodes.back();
        newRoot->Data = item;
        Split(root, item + 1, newRoot->ChildL, newRoot->ChildR);
        return SetSize(newRoot);
    }

    RBST* Insert(RBST* root, DataType item) {
        if (Random() % (GetSize(root) + 1) == 0) {
            return InsertAsRoot(root, item);
        } else if (item < root->Data) {
            RBST *newRoot = NewNode(root);
            newRoot->ChildL = Insert(root->ChildL, item);
            return SetSize(newRoot);
        } else {
            RBST *newRoot = NewNode(root);
            newRoot->ChildR = Insert(root->ChildR, item);
            return SetSize(newRoot);
        }
    }

    RBST* Remove(RBST* root, DataType item) {
        RBST *tree1, *tree2, *tree3, *tree4 = 0;
        Split(root, item, tree1, tree2);
        Split(tree2, item + 1, tree2, tree3);
        if (tree2) tree4 = Join(tree2->ChildL, tree2->ChildR);
        return Join(Join(tree1, tree4), tree3);
    }

    void Destroy() {
        for (int i = 0; i < Nodes.size(); ++i) delete Nodes[i];
    }
};

LCT

struct { int c[2], f; bool r; } c[N];

inline bool id(int o) { return c[c[o].f].c[1] == o; }
inline bool nroot(int o) { return c[c[o].f].c[0] == o | c[c[o].f].c[1] == o; }
inline void pu(int o) {

}
inline void rev(int o) {
    swap(c[o].c[0], c[o].c[1]), c[o].r ^= 1;
}
inline void pd(int o) {
    if (c[o].r) rev(c[o].c[0]), rev(c[o].c[1]), c[o].r = 0;
}
void rot(int o, int d) {
    int k = c[o].c[!d], &x = c[k].c[d];
    if (nroot(o)) c[c[o].f].c[id(o)] = k;
    c[k].f = c[o].f;
    pu(x = c[c[o].c[!d] = x].f = o);
    pu(c[o].f = k);
}
void dfs(int o) { if (nroot(o)) dfs(c[o].f); pd(o); }
void splay(int o) {
    dfs(o);
    for (int f; nroot(o); rot(c[o].f, !id(o)))
    if (nroot(f = c[o].f)) rot(id(o) == id(f) ? c[f].f : f, !id(o));
}
int acc(int o) {
    int x = 0;
    for (; o; o = c[x = o].f) splay(o), c[o].c[1] = x, pu(o);
    return x;
}
void link(int u, int v) {
    rev(acc(u)), splay(u), c[u].f = v;
}
void cut(int u, int v) {
    rev(acc(u)), acc(v), splay(v), c[v].c[0] = c[u].f = 0, pu(v);
}

LCT 维护 size

struct { int c[2], f, s, si; bool r; } c[N];

inline bool id(int o) { return c[c[o].f].c[1] == o; }
inline bool nroot(int o) { return c[c[o].f].c[0] == o | c[c[o].f].c[1] == o; }
inline void pu(int o) {
    c[o].s = c[c[o].c[0]].s + c[c[o].c[1]].s + c[o].si + 1;
}
inline void rev(int o) {
    swap(c[o].c[0], c[o].c[1]), c[o].r ^= 1;
}
inline void pd(int o) {
    if (c[o].r) rev(c[o].c[0]), rev(c[o].c[1]), c[o].r = 0;
}
void rot(int o, int d) {
    int k = c[o].c[!d], &x = c[k].c[d];
    if (nroot(o)) c[c[o].f].c[id(o)] = k;
    c[k].f = c[o].f;
    pu(x = c[c[o].c[!d] = x].f = o);
    pu(c[o].f = k);
}
void dfs(int o) { if (nroot(o)) dfs(c[o].f); pd(o); }
void splay(int o) {
    dfs(o);
    for (int f; nroot(o); rot(c[o].f, !id(o)))
    if (nroot(f = c[o].f)) rot(id(o) == id(f) ? c[f].f : f, !id(o));
}
int acc(int o) {
    int x = 0;
    for (; o; o = c[x = o].f) {
        splay(o);
        c[o].si += c[c[o].c[1]].s - c[x].s;
        c[o].c[1] = x, pu(o);
    }
    return x;
}
void link(int u, int v) {
    rev(acc(u)), c[u].f = v, c[v].s += c[u].s, c[v].si += c[u].s;
}
void cut(int u, int v) {
    rev(acc(u)), acc(v), splay(v), c[v][0] = f[u] = 0, pu(v);
}

图论

2-SAT 字典序最小解

int n, m, co[N << 1], stk[N << 1], tp;
vector<int> G[N << 1];

inline void add(int u, int a, int v, int b) {
    G[u * 2 + !a].push_back(v * 2 + b);
    G[v * 2 + !b].push_back(u * 2 + a);
}
int dfs(int u) {
    if (co[u] | co[u ^ 1]) return co[u];
    co[u] = 1, stk[++tp] = u;
    for (int v : G[u]) if (!dfs(v)) return 0;
    return 1;
}
int twoSat() {
    for (int i = 1; i <= n; i++) {
        if (!co[i * 2] && !co[i * 2 + 1] && !dfs(i * 2)) {
            while (tp) co[stk[tp--]] = 0;
            if (!dfs(i * 2 + 1)) return 0;
        }
        tp = 0;
    }
    return 1;
}

字符串

后缀数组

#define rep(i, l, r) for(int i = (l); i <= (r); i++)
#define per(i, r, l) for(int i = (r); i >= (l); i--)
int n, sa[N], rk[N], tp[N], px[N], buc[N];
int h[20][N];
char s[N];

void SA() {
    int m = 128;
    rep(i, 1, n) buc[rk[i] = s[i]]++;
    rep(i, 1, m) buc[i] += buc[i - 1];
    per(i, n, 1) sa[buc[rk[i]]--] = i;
    for (int k = 1, p; memset(buc, p = 0, m + 1 << 2); k <<= 1) {
        rep(i, n - k + 1, n) p++, px[p] = rk[tp[p] = i];
        rep(i, 1, n) if (sa[i] > k) p++, px[p] = rk[tp[p] = sa[i] - k];
        rep(i, 1, n) buc[rk[i]]++;
        rep(i, 1, m) buc[i] += buc[i - 1];
        per(i, n, 1) sa[buc[px[i]]--] = tp[i];
        memcpy(tp, rk, n + 1 << 2), p = 0;
        rep(i, 1, n) {
            int a = sa[i], b = sa[i - 1];
            rk[a] = p += tp[a] != tp[b] || tp[a + k] != tp[b + k];
        }
        if ((m = p) >= n) break;
    }
    int p = 0;
    rep(i, 1, n) {
        for (p && p--; s[i + p] == s[sa[rk[i] - 1] + p]; p++);
        h[0][rk[i]] = p;
    }
    rep(i, 1, 19) rep(j, 1 << i, n)
        h[i][j] = min(h[i - 1][j], h[i - 1][j - (1 << i - 1)]);
}

后缀自动机

char s[N];
int n, sz = 1, nw = 1, f[N << 1], len[N << 1], ch[N << 1][26];

void ins(int c) {
    int u = ++sz;
    len[u] = len[nw] + 1;
    while (nw && !ch[nw][c]) ch[nw][c] = u, nw = f[nw];
    if (!nw) f[u] = 1;
    else {
        int v = ch[nw][c];
        if (len[v] > len[nw] + 1) {
            f[++sz] = f[v], memcpy(ch[sz], ch[v], sizeof ch[v]);
            f[v] = f[u] = sz, len[sz] = len[nw] + 1;
            while (ch[nw][c] == v) ch[nw][c] = sz, nw = f[nw];
        } else f[u] = v;
    }
    nw = u;
}

manacher 求偶回文串

for (int i = 1; i <= n; i++) {
    int& j = R[i] = ma > i ? min(R[p * 2 - i], ma - i) : 0;
    while (s[i - j] == s[i + j + 1]) j++;
    if (i + j > ma) ma = i + j, p = i;
}

回文自动机

char s[N];
int n, sz = 1, nw, len[N], f[N], ch[N][26];

void ins(int i) {
    auto jmp = [&](int o) {
        while (s[i - len[o] - 1] != s[i]) o = f[o];
        return o;
    };
    int o = jmp(nw), c = s[i] - 97;
    if (!ch[o][c]) {
        f[++sz] = ch[jmp(f[o])][c];
        len[ch[o][c] = sz] = len[o] + 2;
    }
    nw = ch[o][c];
}
void init() {
    len[1] = -1, f[0] = 1;
}

偶回文自动机

void ins(int i) {
    auto jmp = [&](int o) {
        while (o && s[i - len[o] - 1] != s[i]) o = f[o];
        return o;
    };
    int o = jmp(nw), c = s[i] - 97;
    if (!ch[o][c]) {
        f[++sz] = ch[jmp(f[o])][c];
        len[ch[o][c] = sz] = len[o] + 2;
    }
    nw = ch[o][c];
}
void init() {
    for (int i = 0; i < 26; i++) ch[0][i] = 1;
}

最小表示法

int calc(char s[]) {
    int i = 0, j = 1, k = 0;
    while (max({i, j, k}) < n)
    if (s[(i + k) % n] == s[(j + k) % n]) k++;
    else {
        if (s[(i + k) % n] > s[(j + k) % n]) swap(i, j);
        j += k + 1, k = 0;
        if (i == j) j++;
    }
    return min(i, j);
}

最小后缀

int calc(char s[]) {
    int i = 0, j = 1;
    while (s[j]) {
        int k = 0;
        while (s[i + k] == s[j + k]) k++;
        if (!s[j + k]) i = max(i + k, j + 1), swap(i, j);
        else if (s[i + k] > s[j + k]) i = max(i + k, j) + 1, swap(i, j);
        else j += k + 1;
    }
    return i;
}

其他

10^18 级取模

using ll = long long;
ll mul(ll A, ll B, ll P) {
     C = A * B - (ll)((long double)A * B / P + 0.5) * P;
    return C < 0 ? C + P : C;
}

bash 对拍

# 保存为文件 pai
while true; do
    ./gen > in
    ./a < in > 1
    ./b < in > 2
    diff 1 2
    if (($? != 0)); then break; fi
    if ((++index % 100 == 0)); then echo $index; fi
done

过时的

扩展中国剩余定理

ll mul(ll A, ll B, ll P) {
    ll C = A * B - (ll)((long double)A * B / P + 0.5) * P;
    return C < 0 ? C + P : C;
}
void exgcd(ll a, ll b, ll& d, ll& x, ll& y) {
    if (!b) { d = a, x = 1, y = 0; return; }
    exgcd(b, a % b, d, y, x), y -= a / b * x;
}
void exCRT(ll& b1, ll& m1, ll b2, ll m2) {
    ll d, k1, k2; exgcd(m1, m2, d, k1, k2), m2 /= d;
    b1 = (b1 + mul(mul(k1 % m2, (b2 - b1) / d % m2, m2), m1, m1 * m2)) % (m1 *= m2);
}

虚树

int n, a[N], p, stk[N];
int d[N], fa[N], sz[N], son[N], tp[N], idx, dfn[N];
vector<int> G[N];
int eid, he[N];
struct edge { int v, n; } e[N << 1];

void dfs1(int u) {
    sz[u] = 1;
    for (int v : G[u]) {
        d[v] = d[u] + 1, dfs1(v), sz[u] += sz[v];
        if (sz[v] > sz[son[u]]) son[u] = v;
    }
}
void dfs2(int u, int top) {
    tp[u] = top, dfn[u] = ++idx;
    if (son[u]) dfs2(son[u], top);
    for (int v : G[u]) if (v != son[u]) dfs2(v, v);
}
int lca(int u, int v) {
    for (; tp[u] != tp[v]; d[tp[u]] > d[tp[v]] ? u = fa[tp[u]] : v = fa[tp[v]]);
    return d[u] < d[v] ? u : v;
}
inline void add(int u, int v) {
    e[++eid] = {v, he[u]}, he[u] = eid;
}
void bld(int k) {
    sort(a + 1, a + k + 1, [](int a, int b) { return dfn[a] < dfn[b]; });
    stk[++p] = 1;
    for (int i = 1; i <= k; i++) if (a[i] > 1) {
        int x = lca(a[i], stk[p]);
        while (d[stk[p]] > d[x])
            p--, add(d[stk[p]] > d[x] ? stk[p] : x, stk[p + 1]);
        if (stk[p] != x) stk[++p] = x;
        stk[++p] = a[i];
    }
    while (--p) add(stk[p], stk[p + 1]);
}

K-D tree

定义

#define rep(i, l, r) for(int i = (l); i <= (r); i++)
#define per(i, r, l) for(int i = (r); i >= (l); i--)
#define For(i, l, r) for(int i = (l), i##e = (r); i < i##e; i++)
#define mid ((l + r) >> 1)
#define lc (o << 1)
#define rc (o << 1 | 1)
#define lch l, mid, lc
#define rch mid + 1, r, rc

int D, L[N * 4][K], R[N * 4][K];
struct node {
    int x[K];
    void read() { For(i, 0, K) scanf("%d", &x[i]); }
    bool operator <(const node& rhs)const {
        return x[D] < rhs.x[D];
    }
} a[N];

函数

double sq(double x) { return x * x; }
void pu(int o) {
    For(i, 0, K) {
        L[o][i] = min(L[lc][i], L[rc][i]);
        R[o][i] = max(R[lc][i], R[rc][i]);
    }
}
void build(int l, int r, int o) {
    if (l == r) {
        For(i, 0, K) L[o][i] = R[o][i] = a[l].x[i];
        return;
    }
    double va[K] = {};
    For(i, 0, K) {
        double av = 0;
        rep(j, l, r) av += a[j].x[i];
        av /= r - l + 1;
        rep(j, l, r) va[i] += sq(a[j].x[i] - av);
    }
    D = max_element(va, va + K) - va;
    nth_element(a + l, a + mid, a + r + 1);
    build(lch), build(rch), pu(o);
}

欧几里得距离平方

ll sq(int x) { return 1ll * x * x; }
ll mine(int o, int x[], ll re = 0) {
    For(i, 0, K) re += sq(max(L[o][i] - x[i], 0)) + sq(max(x[i] - R[o][i], 0));
    return re;
}
ll maxe(int o, int x[], ll re = 0) {
    For(i, 0, K) re += max(sq(x[i] - L[o][i]), sq(x[i] - R[o][i]));
    return re;
}

曼哈顿距离

int minm(int o, int x[], int re = 0) {
    For(i, 0, K) re += max(L[o][i] - x[i], 0) + max(x[i] - R[o][i], 0);
    return re;
}
int maxm(int o, int x[], int re = 0) {
    For(i, 0, K) re += max(abs(x[i] - L[o][i]), abs(x[i] - R[o][i]));
    return re;
}

切比雪夫距离

int minc(int o, int x[], int re = inf) {
    For(i, 0, K) re = max(re, max(L[o][i] - x[i], 0) + max(x[i] - R[o][i], 0));
    return re;
}
int maxc(int o, int x[], int re = 0) {
    For(i, 0, K) re = max({re, abs(x[i] - L[o][i]), abs(x[i] - R[o][i])});
    return re;
}

最近点查询

定义

ll res;

函数

void qry(int x[], int l, int r, int o) {
    if (l == r) return void(res = mine(o, x));
    ll dl = mine(lc, x), dr = mine(rc, x);
    if (dl < dr) {
        if (dl < res) qry(x, lch);
        if (dr < res) qry(x, rch);
    } else {
        if (dr < res) qry(x, rch);
        if (dl < res) qry(x, lch);
    }
}

初始化

res = inf;

最远点查询

定义

ll res;

函数

void qry(int x[], int l, int r, int o) {
    if (l == r) return void(res = maxe(o, x));
    ll dl = maxe(lc, x), dr = maxe(rc, x);
    if (dl > dr) {
        if (dl > res) qry(x, lch);
        if (dr > res) qry(x, rch);
    } else {
        if (dr > res) qry(x, rch);
        if (dl > res) qry(x, lch);
    }
}

初始化

res = 0;

矩形是否包含所有点

int chk1(int l[], int r[], int o, int re = 1) {
    For(i, 0, K) re &= l[i] <= L[o][i] && R[o][i] <= r[i];
    return re;
}

矩形是否可能包含点

int chk2(int l[], int r[], int o, int re = 1) {
    For(i, 0, K) re &= max(l[i], L[o][i]) <= min(r[i], R[o][i]);
    return re;
}

圆是否包含所有点

int chk1(int x[], int r, int o) {
    return maxe(x, o) <= 1ll * r * r;
}

圆是否可能包含点

int chk2(int x[], int r, int o) {
    return mine(x, o) <= 1ll * r * r;
}

待填

• 自然数等幂求和
• 中国剩余定理
• 杜教筛
• 拉格朗日插值