C++ 竞赛用模板

模板是泛型编程的基础，泛型编程即以一种独立于任何特定类型的方式编写代码。

—— C++ 模板，来自菜鸟教程 runoob.com

这里记录了我经常使用的算法竞赛的板子。

在 C++17 以及以上的高版本 C++ 中，模板类拥有自动类型推断。比如下文中的 ST<T> ，只要你传入了 vector<long long>& a，T 就等于 long long，无需手动指定。

并查集

struct DSU {
    int tot;
    vector<int> pa, size;
    DSU(int n) : pa(n+1), size(n+1, 1), tot(n) {
        iota(pa.begin(),pa.end(),0);
    }
    
    int find(int x){
        while (x!=pa[x]){
            x=pa[x]=pa[pa[x]];
        }
        return x;
    }
    int operator[](int x) {return find(x);}
    
    void unite(int x, int y) {
        x=find(x),y=find(y);
        if (x==y) return;
        tot--;
        if (size[x]<size[y]) swap(x,y);
        pa[y]=x;
        size[x]+=size[y];
    }
};

ST 表

template<typename T=int, class Func = std::function<T(T, T)>>
struct ST {
    int n;
    vector<vector<T>> st;
    vector<int> lg;
    Func op;
    ST(vector<T>& a, Func _op=[](T x, T y){ return max(x,y); }): n(a.size()-1), lg(a.size()), op(_op){
        lg[0]=lg[1]=0;
        for (int i=2;i<=n;i++) lg[i]=lg[i>>1]+1;
        st.resize(lg[n]+1);
        for (int i=0;i<=lg[n];i++) st[i].resize(a.size());
        for (int i=1;i<=n;i++) st[0][i]=a[i];
        for (int i=1;i<=lg[n];i++){
            for (int j=1;j+(1<<i)-1<=n;j++){
                st[i][j]=op(st[i-1][j],st[i-1][j+(1<<(i-1))]);
            }
        }
    }
    
    T query(int l,int r){
        int p=lg[r-l+1];
        return op(st[p][l],st[p][r-(1<<p)+1]);
    }
    T operator()(int l,int r){
        return query(l,r);
    }
};

ModInt

template<typename T = long long, int mod = 998244353>
struct Mint {
    T v;

    Mint(T _v = T{}) {
        v = _v % mod;
        if (v < 0) v += mod;
    }

    explicit operator int() const { return (int)v; }
    explicit operator long long() const { return (long long)v; }

    Mint operator+(const Mint &o) const { return Mint(v + o.v); }
    Mint operator-(const Mint &o) const { return Mint(v - o.v); }
    Mint operator*(const Mint &o) const { return Mint(v * o.v % mod); }

    Mint pow(long long e) const {
        Mint res(1), base(v);
        while (e > 0) {
            if (e & 1) res = res * base;
            base = base * base;
            e >>= 1;
        }
        return res;
    }

    Mint inv() const { return pow(mod - 2); }

    Mint operator/(const Mint &o) const { return *this * o.inv(); }

    Mint& operator+=(const Mint &o) { v += o.v; if (v >= mod) v -= mod; return *this; }
    Mint& operator-=(const Mint &o) { v -= o.v; if (v < 0) v += mod; return *this; }
    Mint& operator*=(const Mint &o) { v = (v * o.v) % mod; return *this; }
    Mint& operator/=(const Mint &o) { return *this *= o.inv(); }

    bool operator==(const Mint &o) const { return v == o.v; }
    bool operator!=(const Mint &o) const { return v != o.v; }

    friend istream& operator>>(istream &is, Mint &m) {
        long long x; is >> x;
        m = Mint(x);
        return is;
    }

    friend ostream& operator<<(ostream &os, const Mint &m) {
        return os << m.v;
    }
};

using Z=Mint<long long,998244353>;

树状数组

template<typename T=int>
struct fenwick {
    int n;
    vector<T> t;
    fenwick(int _n): n(_n), t(_n+1){}
    fenwick(vector<T>& a): n(a.size()-1), t(a.size()){
        for (int i=1;i<=n;i++){
            t[i]+=a[i];
            if (i+(i&(-i))<=n){
                t[i+(i&(-i))]+=t[i];
            }
        }
    }
    
    T query(int p){
        T res=T{};
        while(p){
            res+=t[p];
            p-=(p&(-p));
        }
        return res;
    }
    T operator[](int p){
        return query(p);
    }
    T operator()(int l,int r){
        if (l>r) swap(l,r);
        return query(r)-query(l-1);
    }
    
    void add(int p,T x){
        while(p<=n){
            t[p]+=x;
            p+=(p&(-p));
        }
    }
};

矩阵 + 快速幂

template <typename T = long long, int p = 998244353>
struct matrix{
	int n;
	vector<vector<T>> a;
	matrix (int _n,T x=T{}):n(_n),a(_n,vector<T>(_n,0)){
		for (int i=0;i<n;i++) a[i][i]=x;
	}
	vector<T>& operator[] (int i){
		return a[i];
	}
	const vector<T>& operator[] (int i) const{
		return a[i];
	}
	matrix operator* (const matrix& b) const{
		matrix ret={n};
		for (int i=0;i<n;i++)
			for (int k=0;k<n;k++)
				for (int j=0;j<n;j++)
					ret[i][j]=(ret[i][j]+a[i][k]*b[k][j]%p)%p;
		return ret;
	}
	matrix pow(long long b) const{
		matrix a=*this;
		matrix ret={n,T{1}};
		while (b){
			if (b&1) ret=ret*a;
			a=a*a;
			b>>=1;
		}
		return ret;
	}
};

区间加线段树

template <typename T=int>
struct segtree {
    vector<T> tree, lazy;
    int n;
    void push(int cl, int cr, int p) {
        int cm = cl + (cr - cl) / 2;
        if (cl != cr && lazy[p]) {
            lazy[p * 2] += lazy[p];
            lazy[p * 2 + 1] += lazy[p];
            tree[p * 2] += lazy[p] * (cm - cl + 1);
            tree[p * 2 + 1] += lazy[p] * (cr - cm);
            lazy[p] = 0;
        }
    }
    T query(int l, int r, int cl, int cr, int p) {
        if (l <= cl && cr <= r) return tree[p];
        int m = cl + (cr - cl) / 2;
        T sum = T{};
        push(cl, cr, p);
        if (l <= m) sum += query(l, r, cl, m, p * 2);
        if (r > m) sum += query(l, r, m + 1, cr, p * 2 + 1);
        return sum;
    }

    void add(int l, int r, T val, int cl, int cr, int p) {
        if (l <= cl && cr <= r) {
            lazy[p] += val;
            tree[p] += (cr - cl + 1) * val;
            return;
        }
        int m = cl + (cr - cl) / 2;
        push(cl, cr, p);
        if (l <= m) add(l, r, val, cl, m, p * 2);
        if (r > m) add(l, r, val, m + 1, cr, p * 2 + 1);
        tree[p] = tree[p * 2] + tree[p * 2 + 1];
    }

    void build(int s, int t, int p, vector<T> &arr) {
        if (s == t) {
            tree[p] = arr[s];
            return;
        }
        int m = s + (t - s) / 2;
        build(s, m, p * 2, arr);
        build(m + 1, t, p * 2 + 1, arr);
        tree[p] = tree[p * 2] + tree[p * 2 + 1];
    }
    
    void build(int s, int t, int p, T init) {
        if (s == t) {
            tree[p] = init;
            return;
        }
        int m = s + (t - s) / 2;
        build(s, m, p * 2, init);
        build(m + 1, t, p * 2 + 1, init);
        tree[p] = tree[p * 2] + tree[p * 2 + 1];
    }

    segtree(vector<T> &arr): n(arr.size()), tree(arr.size()<<2), lazy(arr.size()<<2) {
        build(0, n-1, 1, arr);
    }
    segtree(int _n,T init): n(_n), tree(_n<<2), lazy(_n<<2) {
        build(0, n-1, 1, init);
    }
    T query(int l, int r) { return query(l, r, 0, n-1, 1); }
    T operator()(int l,int r){ return query(l,r);}
    void add(int l, int r, T val) { add(l, r, val, 0, n-1, 1); }
};

区间推平线段树

template <typename T=int>
struct segtree {
    vector<T> tree, lazy;
    vector<bool> if_lazy;
    int n;
    void push(int cl, int cr, int p) {
        int cm = cl + (cr - cl) / 2;
        if (cl != cr && if_lazy[p]) {
            lazy[p * 2] = lazy[p],if_lazy[p*2] = 1;
            lazy[p * 2 + 1] = lazy[p],if_lazy[p*2+1] = 1;
            tree[p * 2] = lazy[p] * (cm - cl + 1);
            tree[p * 2 + 1] = lazy[p] * (cr - cm);
            lazy[p] = 0;
            if_lazy[p] = 0;
        }
    }

    T query(int l, int r, int cl, int cr, int p) {
        if (l <= cl && cr <= r) return tree[p];
        int m = cl + (cr - cl) / 2;
        T sum = T{};
        push(cl, cr, p);
        if (l <= m) sum += query(l, r, cl, m, p * 2);
        if (r > m) sum += query(l, r, m + 1, cr, p * 2 + 1);
        return sum;
    }

    void modify(int l, int r, T val, int cl, int cr, int p) {
        if (l <= cl && cr <= r) {
            lazy[p] = val;
            if_lazy[p] = 1;
            tree[p] = (cr - cl + 1) * val;
            return;
        }
        int m = cl + (cr - cl) / 2;
        push(cl, cr, p);
        if (l <= m) modify(l, r, val, cl, m, p * 2);
        if (r > m) modify(l, r, val, m + 1, cr, p * 2 + 1);
        tree[p] = tree[p * 2] + tree[p * 2 + 1];
    }

    void build(int s, int t, int p, vector<T> &arr) {
        if (s == t) {
            tree[p] = arr[s];
            return;
        }
        int m = s + (t - s) / 2;
        build(s, m, p * 2, arr);
        build(m + 1, t, p * 2 + 1, arr);
        tree[p] = tree[p * 2] + tree[p * 2 + 1];
    }
    
    void build(int s, int t, int p, T init) {
        if (s == t) {
            tree[p] = init;
            return;
        }
        int m = s + (t - s) / 2;
        build(s, m, p * 2, init);
        build(m + 1, t, p * 2 + 1, init);
        tree[p] = tree[p * 2] + tree[p * 2 + 1];
    }

    segtree(vector<T> &arr): n(arr.size()), tree(arr.size()<<2), lazy(arr.size()<<2), if_lazy((arr.size()<<2),0) {
        build(0, n-1, 1, arr);
    }
    segtree(int _n,T init): n(_n), tree(_n<<2), lazy(_n<<2), if_lazy((_n<<2),0) {
        build(0, n-1, 1, init);
    }

    T query(int l, int r) { return query(l, r, 0, n-1, 1); }
    T operator()(int l,int r){ return query(l,r);}
    void modify(int l, int r, T val) { modify(l, r, val, 0, n-1, 1); }
};

单点修改线段树

template <typename T=int>
struct segtree {
    vector<T> tree;
    int n;
    T query(int l, int r, int cl, int cr, int p) {
        if (l <= cl && cr <= r) return tree[p];
        int m = cl + (cr - cl) / 2;
        T sum = T{};
        if (l <= m) sum += query(l, r, cl, m, p * 2);
        if (r > m) sum += query(l, r, m + 1, cr, p * 2 + 1);
        return sum;
    }

    void add(int idx, T val, int cl, int cr, int p) {
        if (cl == cr && cr == idx) {
            tree[p] += val;
            return;
        }
        int m = cl + (cr - cl) / 2;
        if (idx <= m) add(idx, val, cl, m, p * 2);
        if (idx > m) add(idx, val, m + 1, cr, p * 2 + 1);
        tree[p] = tree[p * 2] + tree[p * 2 + 1];
    }

    void modify(int idx, T val, int cl, int cr, int p) {
        if (cl == cr && cr == idx) {
            tree[p] = val;
            return;
        }
        int m = cl + (cr - cl) / 2;
        if (idx <= m) modify(idx, val, cl, m, p * 2);
        if (idx > m) modify(idx, val, m + 1, cr, p * 2 + 1);
        tree[p] = tree[p * 2] + tree[p * 2 + 1];
    }

    void build(int s, int t, int p, vector<T> &arr) {
        if (s == t) {
            tree[p] = arr[s];
            return;
        }
        int m = s + (t - s) / 2;
        build(s, m, p * 2, arr);
        build(m + 1, t, p * 2 + 1, arr);
        tree[p] = tree[p * 2] + tree[p * 2 + 1];
    }
    
    void build(int s, int t, int p, T init) {
        if (s == t) {
            tree[p] = init;
            return;
        }
        int m = s + (t - s) / 2;
        build(s, m, p * 2, init);
        build(m + 1, t, p * 2 + 1, init);
        tree[p] = tree[p * 2] + tree[p * 2 + 1];
    }

    segtree(vector<T> &arr): n(arr.size()), tree(arr.size()<<2) {
        build(0, n-1, 1, arr);
    }
    segtree(int _n,T init): n(_n), tree(_n<<2) {
        build(0, n-1, 1, init);
    }
    T query(int l, int r) { return query(l, r, 0, n-1, 1); }
    T operator()(int l,int r){ return query(l,r);}
    void add(int idx, T val) { add(idx, val, 0, n-1, 1); }
    void modify(int idx, T val) { modify(idx, val, 0, n-1, 1); }
};

Lucas 定理

template<typename T=long long>
struct lucas
{
    vector<T>fa,inv;
    T p;
    lucas(T _p): p(_p), fa(_p), inv(_p){
        fa[0]=inv[0]=1;
        for (T i=1;i<p;i++){
            fa[i]=fa[i-1]*i%p;
            inv[i]=qpow(fa[i],p-2);
        }
    }
    T qpow(T a,T b){
        T res=1;
        while(b){
                if (b&1) res=res*a%p;
                a=a*a%p;
                b>>=1;
        }
        return res;
    }
    T c(T a,T b){
        if (b>a) return 0;
        return fa[a]*inv[a-b]%p*inv[b]%p;
    }
    T get(T a,T b){
        if (not b) return 1;
        return get(a/p,b/p)*c(a%p,b%p)%p;
    }
    T operator()(T a,T b){ return get(a,b); }
};

Manacher

struct Manacher {
    vector<int>p;
    int n;
    Manacher(string &_s): n(_s.size()*2+2), p(_s.size()*2+2,1) {
        string s="$|";
        s.reserve(n);
        for (auto&&c:_s){
            s+=c;
            s+='|';
        }
        for (int t=1,r=0,mid=0;t<n;t++){
            if (t<=r) p[t]=min(p[mid*2-t],r-t+1);
            while (p[t]<=t and t+p[t]<n and s[t-p[t]]==s[t+p[t]]) p[t]++;
            if (p[t]+t>r) r=p[t]+t-1,mid=t;
        }
    }
    bool query(int l,int r){
        // 1-indexed
        l=l*2,r=r*2;
        int mid=(l+r)/2;
        return p[mid]>=(r-mid+1);
    }
    bool operator()(int l,int r){ return query(l,r); }
    int operator[](int i){ return p[i]; }
};

预处理的 KMP

struct KMP {
    vector<vector<int>>nxt;
    int n,st,ed;
    KMP(string &p,int _st='a',int _ed='z'): n(p.size()), st(_st), ed(_ed), nxt(_ed-_st+1,vector(p.size(),0)) {
        int pre=0;
        nxt[p[0]-st][0]=1;
        for (int i=1;i<n;i++){
            for (int j=st;j<=ed;j++){
                if (j==p[i])
                    nxt[j-st][i]=i+1;
                else
                    nxt[j-st][i]=nxt[j-st][pre];
            }
            pre=nxt[p[i]-st][pre];
        }
    }
    int find_first(string &s){
        int cur=0;
        for (int i=0;i<s.length();i++){
            cur=nxt[s[i]-st][cur];
            if (cur==n)
                return i-n+1;
        }
        return -1;
    }
    int find_largest(string &s){
        int cur=0,ret=0;
        for (int i=0;i<s.length();i++){
            cur=nxt[s[i]-st][cur];
            if (cur==n)
                return n;
            if (cur>ret)
                ret=cur;
        }
        return ret;
    }
};

Z 函数 / 扩展 KMP

struct exKMP {
    vector<int>z;
    int n;
    exKMP(string &p): n(p.size()), z(p.size()) {
        int l=0;
        for (int i=1;i<n;i++){
            if (l+z[l]>i) z[i]=min(z[i-l],l+z[l]-i);
            while (i+z[i]<n and p[z[i]]==p[i+z[i]]) z[i]++;
            if (i+z[i]>l+z[l]) l=i;
        }
    }
    int query(int i){ return (i==0?n:z[i]); }
    int operator[](int i){ return query(i); }
};

MillerRabin 快速质数判定

template<typename T=__int128>
struct MillerRabin{
	vector<T> p{2,3,5,7,11,13,17,19,23,29,31,37};
	MillerRabin (){}
	T qpow(T a,T b,T p){
        T res=1;
        while(b){
                if (b&1) res=res*a%p;
                a=a*a%p;
                b>>=1;
        }
        return res;
    }
	bool check(T x){
		if (x<=37){
			for (auto&&i:p) if (i==x) return 1;
			return 0;
		}
		T u=x-1,t=0;
		while (not (u&1))
			(u>>=1),t++;
		for (auto&&i:p){
			T v=qpow(i,u,x);
			if (v==1) continue;
			T s=0;
			for (;s<t;s++){
				if (v==x-1) break;
				v=(v*v)%x;
			}
			if (s==t) return 0;
		}
		return 1;
	}
	bool operator()(T x){ return check(x); }
};

NTT 快速数论变换

template<int mod, int root, typename T = long long>
class NTTProc {
private:
	T qpow(T base, T exp) const {
        T res = 1;
        base %= mod;
        while (exp > 0) {
            if (exp % 2 == 1) res = (res * base) % mod;
            base = (base * base) % mod;
            exp /= 2;
        }
        return res;
    }
    T qinv(T x) const {
        return qpow(x, mod - 2);
    }
	inline static const T inv_root = NTTProc<mod, root, T>().qinv((T)root);
    void trans(vector<T>& a, bool invert) {
        int n = a.size();
        for (int i = 1, j = 0; i < n; i++) {
            int bit = n >> 1;
            for (; j & bit; bit >>= 1) {
                j ^= bit;
            }
            j ^= bit;
            if (i < j) {
                swap(a[i], a[j]);
            }
        }
        for (int len = 2; len <= n; len <<= 1) {
            T wlen = qpow(invert ? inv_root : root, (mod - 1) / len);
            for (int i = 0; i < n; i += len) {
                T w = 1;
                for (int j = 0; j < len / 2; j++) {
                    T u = a[i + j];
                    T v = (a[i + j + len / 2] * w) % mod;
                    a[i + j] = (u + v) % mod;
                    a[i + j + len / 2] = (u - v + mod) % mod;
                    w = (w * wlen) % mod;
                }
            }
        }
        if (invert) {
            T n_inv = qinv(n);
            for (T& x : a) {
                x = (x * n_inv) % mod;
            }
        }
    }
public:
    NTTProc() = default;
    vector<T> mul(vector<T>& a, vector<T>& b) {
        if (a.empty() || b.empty()) return {};
        int n = a.size() + b.size() - 1;
        int mx = 1;
        while (mx < n) {
            mx <<= 1;
        }
        a.resize(mx);
        b.resize(mx);
        trans(a, false);
        trans(b, false);
        vector<T> c(mx);
        for (int i = 0; i < mx; i++) {
            c[i] = (a[i] * b[i]) % mod;
        }
        trans(c, true);
        c.resize(n);
        return c;
    }
    vector<T> operator()(vector<T>& a,vector<T>& b) {
    	return mul(a, b);
    }
};

NTTProc<998244353,3> ntt;

发表反馈

上传反馈

上传反馈即代表您已经同意 《隐私政策》 相关内容。 必填项已用 * 标注