代码模板

by JiuQiin 学习on Posted on
Contents hide
1 数论
1.1 线性基
1.2 取模类
1.3 组合数
1.4 大模数（只有模数接近 101810^{18} 才用）
1.5 随机数模板
2 数据结构
2.1 线段树（带懒标记）

数论

线性基

异或第 k 大 
vector<LL> a(n+ 1, 0), d(LOG + 1, 0);

    auto add = [&](LL x)
    {
        for (LL i = LOG; i >= 0; --i) {
            if (!(x >> i & 1)) continue;
            if (!d[i]) {
                d[i] = x;
                return;
            }
            x ^= d[i];
        }
    };
    
    auto Gaussion = [&]() {
        for (LL i = LOG; i >= 0; --i) {
            if (!d[i]) continue;
            for (LL j = i - 1; j >= 0; --j) {
                if (d[i] >> j & 1) {
                    d[i] ^= d[j];
                }
            }
        }

        for (LL i = 0; i <= LOG; ++i) {
            if (!d[i]) continue;
            p.push_back(d[i]);
        }
    };
    
    for (LL i = 1; i <= n; ++i) {
        cin >> a[i];
        add(a[i]);
    }

    Gaussion();

取模类 + 组合数

取模类

using i64 = long long;

template<class T>
constexpr T power(T a, i64 b)
{
    T res = 1;
    for (; b; b >>= 1, a *= a)
    {
        if (b & 1)
        {
            res *= a;
        }
    }
    return res;
}

template<int P>
struct MInt
{
    int x;

    constexpr MInt() : x(0) {}

    constexpr MInt(i64 v)
    {
        x = v % P;
        if (x < 0)
        {
            x += P;
        }
    }

    constexpr int val() const
    {
        return x;
    }

    constexpr MInt inv() const
    {
        return power(*this, P - 2);
    }

    constexpr MInt& operator+=(const MInt& rhs)
    {
        x += rhs.x;
        if (x >= P)
        {
            x -= P;
        }
        return *this;
    }

    constexpr MInt& operator-=(const MInt& rhs)
    {
        x -= rhs.x;
        if (x < 0)
        {
            x += P;
        }
        return *this;
    }

    constexpr MInt& operator*=(const MInt& rhs)
    {
        x = 1LL * x * rhs.x % P;
        return *this;
    }

    constexpr MInt& operator/=(const MInt& rhs)
    {
        return *this *= rhs.inv();
    }

    friend constexpr MInt operator+(MInt a, const MInt& b)
    {
        return a += b;
    }

    friend constexpr MInt operator-(MInt a, const MInt& b)
    {
        return a -= b;
    }

    friend constexpr MInt operator*(MInt a, const MInt& b)
    {
        return a *= b;
    }

    friend constexpr MInt operator/(MInt a, const MInt& b)
    {
        return a /= b;
    }

    friend ostream& operator<<(ostream& os, const MInt& a)
    {
        return os << a.x;
    }

    friend istream& operator>>(istream& is, MInt& a)
    {
        i64 v;
        is >> v;
        a = MInt(v);
        return is;
    }
};

using Z = MInt<998244353>;

用法

Z a = 3;
Z b = 5;

cout << a + b << endl;
cout << a * b << endl;
cout << a / b << endl;

组合数

using i64 = long long;

template<class T>
constexpr T power(T a, i64 b)
{
    T res = 1;
    for (; b; b >>= 1, a *= a)
    {
        if (b & 1)
        {
            res *= a;
        }
    }
    return res;
}

template<int P>
struct MInt
{
    int x;

    constexpr MInt() : x(0) {}

    constexpr MInt(i64 v)
    {
        x = v % P;
        if (x < 0)
        {
            x += P;
        }
    }

    constexpr int val() const
    {
        return x;
    }

    constexpr MInt inv() const
    {
        return power(*this, P - 2);
    }

    constexpr MInt& operator+=(const MInt& rhs)
    {
        x += rhs.x;
        if (x >= P)
        {
            x -= P;
        }
        return *this;
    }

    constexpr MInt& operator-=(const MInt& rhs)
    {
        x -= rhs.x;
        if (x < 0)
        {
            x += P;
        }
        return *this;
    }

    constexpr MInt& operator*=(const MInt& rhs)
    {
        x = 1LL * x * rhs.x % P;
        return *this;
    }

    constexpr MInt& operator/=(const MInt& rhs)
    {
        return *this *= rhs.inv();
    }

    friend constexpr MInt operator+(MInt a, const MInt& b)
    {
        return a += b;
    }

    friend constexpr MInt operator-(MInt a, const MInt& b)
    {
        return a -= b;
    }

    friend constexpr MInt operator*(MInt a, const MInt& b)
    {
        return a *= b;
    }

    friend constexpr MInt operator/(MInt a, const MInt& b)
    {
        return a /= b;
    }

    friend ostream& operator<<(ostream& os, const MInt& a)
    {
        return os << a.x;
    }

    friend istream& operator>>(istream& is, MInt& a)
    {
        i64 v;
        is >> v;
        a = MInt(v);
        return is;
    }
};

using Z = MInt<998244353>;

struct Comb
{
    int n;
    vector<Z> fac_;
    vector<Z> ifac_;
    vector<Z> inv_;

    Comb() : n(0), fac_(1, 1), ifac_(1, 1), inv_(1, 0) {}

    void init(int m)
    {
        if (m <= n)
        {
            return;
        }

        fac_.resize(m + 1);
        ifac_.resize(m + 1);
        inv_.resize(m + 1);

        for (int i = n + 1; i <= m; i++)
        {
            fac_[i] = fac_[i - 1] * i;
        }

        ifac_[m] = fac_[m].inv();

        for (int i = m; i > n; i--)
        {
            ifac_[i - 1] = ifac_[i] * i;
            inv_[i] = ifac_[i] * fac_[i - 1];
        }

        n = m;
    }

    Z fac(int m)
    {
        if (m > n)
        {
            init(2 * m);
        }
        return fac_[m];
    }

    Z ifac(int m)
    {
        if (m > n)
        {
            init(2 * m);
        }
        return ifac_[m];
    }

    Z inv(int m)
    {
        if (m > n)
        {
            init(2 * m);
        }
        return inv_[m];
    }

    Z C(int n, int m)
    {
        if (m < 0 || m > n)
        {
            return 0;
        }
        return fac(n) * ifac(m) * ifac(n - m);
    }

    Z P(int n, int m)
    {
        if (m < 0 || m > n)
        {
            return 0;
        }
        return fac(n) * ifac(n - m);
    }
};

Comb comb;

用法

comb.init(100000);

cout << comb.C(5,2) << endl;
cout << comb.C(10,3) << endl;
cout << comb.P(10,3) << endl;

/*
fac     -> 阶乘

ifac    -> 阶乘逆元

inv     -> 普通逆元

C       -> 组合数

P       -> 排列数
*/

大模数（只有模数接近 101810^{18} 才用）

using i64 = long long;

template<class T>
constexpr T power(T a, i64 b)
{
    T res = 1;
    for (; b; b >>= 1, a *= a)
    {
        if (b & 1)
        {
            res *= a;
        }
    }
    return res;
}

constexpr i64 mul(i64 a, i64 b, i64 mod)
{
    i64 res = a * b - i64(1.L * a * b / mod) * mod;
    res %= mod;

    if (res < 0)
    {
        res += mod;
    }

    return res;
}

template<i64 P>
struct MLong
{
    i64 x;

    constexpr MLong() : x(0) {}

    constexpr MLong(i64 v)
    {
        x = v % P;
        if (x < 0)
        {
            x += P;
        }
    }

    constexpr MLong inv() const
    {
        return power(*this, P - 2);
    }

    constexpr MLong& operator+=(const MLong& rhs)
    {
        x += rhs.x;
        if (x >= P)
        {
            x -= P;
        }
        return *this;
    }

    constexpr MLong& operator-=(const MLong& rhs)
    {
        x -= rhs.x;
        if (x < 0)
        {
            x += P;
        }
        return *this;
    }

    constexpr MLong& operator*=(const MLong& rhs)
    {
        x = mul(x, rhs.x, P);
        return *this;
    }

    constexpr MLong& operator/=(const MLong& rhs)
    {
        return *this *= rhs.inv();
    }

    friend constexpr MLong operator+(MLong a, const MLong& b)
    {
        return a += b;
    }

    friend constexpr MLong operator-(MLong a, const MLong& b)
    {
        return a -= b;
    }

    friend constexpr MLong operator*(MLong a, const MLong& b)
    {
        return a *= b;
    }

    friend constexpr MLong operator/(MLong a, const MLong& b)
    {
        return a /= b;
    }
};

随机数模板

mt19937 rng(
    chrono::steady_clock::now().time_since_epoch().count()
);

int Rand(int l, int r)
{
    return uniform_int_distribution<int>(l, r)(rng);
}

用法

cout << Rand(1, 100) << endl;

数据结构

线段树（带懒标记）

求最大值 
struct segTree
{
    LL n;

    // tree : 当前区间答案
    // lazy : 懒标记
    vector<LL> tree, lazy;

    segTree(LL n) : n(n)
    {
        tree.assign(n << 2, 0);
        lazy.assign(n << 2, 0);
    }

    // 合并左右儿子
    // 当前版本维护区间最大值
    LL merge(LL a, LL b)
    {
        return max(a, b);
    }

    // 建树
    void build(vector<LL> &arr, LL idx, LL l, LL r)
    {
        if (l == r)
        {
            tree[idx] = arr[l];
            return;
        }

        LL mid = (l + r) >> 1;
        LL ls = idx << 1;
        LL rs = ls | 1;

        build(arr, ls, l, mid);
        build(arr, rs, mid + 1, r);

        tree[idx] = merge(tree[ls], tree[rs]);
    }

    // 下传懒标记
    void pushDown(LL idx)
    {

        if (!lazy[idx])
            return;

        LL ls = idx << 1;
        LL rs = ls | 1;

        tree[ls] += lazy[idx];
        tree[rs] += lazy[idx];

        lazy[ls] += lazy[idx];
        lazy[rs] += lazy[idx];

        lazy[idx] = 0;
    }

    // 区间修改
    // [ql, qr] 全部 + val
    void update(LL idx, LL l, LL r, LL ql, LL qr, LL val)
    {
        if (ql <= l && r <= qr)
        {
            tree[idx] += val;
            lazy[idx] += val;
            return;
        }

        pushDown(idx);

        LL mid = (l + r) >> 1;
        LL ls = idx << 1;
        LL rs = ls | 1;

        if (ql <= mid)
            update(ls, l, mid, ql, qr, val);

        if (qr > mid)
            update(rs, mid + 1, r, ql, qr, val);

        tree[idx] = merge(tree[ls], tree[rs]);
    }

    // 区间查询
    LL query(LL idx, LL l, LL r, LL ql, LL qr)
    {
        if (ql > qr)
            return 0;

        if (ql <= l && r <= qr)
        {
            return tree[idx];
        }

        pushDown(idx);

        LL mid = (l + r) >> 1;
        LL ls = idx << 1;
        LL rs = ls | 1;

        LL res = LLONG_MIN;

        if (ql <= mid)
            res = merge(res, query(ls, l, mid, ql, qr));

        if (qr > mid)
            res = merge(res, query(rs, mid + 1, r, ql, qr));

        return res;
    }
};

用法

// 假设数组长度 n
segTree seg(n);

seg.build(a, 1, 1, n);

// 区间加
seg.update(1, 1, n, L, R, val);
// 表示 [L,R] += val

// 查询最大值
cout << seg.query(1, 1, n, L, R);

求区间和 
struct segTree
{
    LL n;
    vector<LL> tree, lazy;

    segTree(LL n) : n(n)
    {
        tree.assign(n << 2, 0);
        lazy.assign(n << 2, 0);
    }

    //
    LL merge(LL a, LL b)
    {
        return a + b;
    }

    void build(vector<LL> &arr, LL idx, LL l, LL r)
    {
        if (l == r)
        {
            tree[idx] = arr[l];
            return;
        }

        LL mid = (l + r) >> 1;
        LL ls = idx << 1;
        LL rs = ls | 1;

        build(arr, ls, l, mid);
        build(arr, rs, mid + 1, r);

        tree[idx] = merge(tree[ls], tree[rs]);
    }

    //
    void pushDown(LL idx, LL l, LL r)
    {
        if (!lazy[idx])
            return;

        LL mid = (l + r) >> 1;
        LL ls = idx << 1;
        LL rs = ls | 1;

        //
        tree[ls] += (mid - l + 1) * lazy[idx];
        tree[rs] += (r - mid) * lazy[idx];

        lazy[ls] += lazy[idx];
        lazy[rs] += lazy[idx];

        lazy[idx] = 0;
    }

    void update(LL idx, LL l, LL r, LL ql, LL qr, LL val)
    {
        if (ql <= l && r <= qr)
        {
            //
            tree[idx] += (r - l + 1) * val;
            lazy[idx] += val;
            return;
        }

        //
        pushDown(idx, l, r);

        LL mid = (l + r) >> 1;
        LL ls = idx << 1;
        LL rs = ls | 1;

        if (ql <= mid)
            update(ls, l, mid, ql, qr, val);

        if (qr > mid)
            update(rs, mid + 1, r, ql, qr, val);

        tree[idx] = merge(tree[ls], tree[rs]);
    }

    LL query(LL idx, LL l, LL r, LL ql, LL qr)
    {
        if (ql > qr)
            return 0;

        if (ql <= l && r <= qr)
            return tree[idx];

        //
        pushDown(idx, l, r);

        LL mid = (l + r) >> 1;
        LL ls = idx << 1;
        LL rs = ls | 1;

        //
        LL res = 0;

        if (ql <= mid)
            res = merge(res, query(ls, l, mid, ql, qr));

        if (qr > mid)
            res = merge(res, query(rs, mid + 1, r, ql, qr));

        return res;
    }
};
“Must thou go, my glorious Chief, Severed from thy faithful few? Who can tell thy warrior's grief, Maddening o'er that long adieu?”
— George Gordon, Lord Byron · From the French
Post authorWritten by

Leave a Comment

您的邮箱地址不会被公开。 必填项已用 * 标注