myself算法模板

快读(__int128)

i128 read () {
    i128 x = 0, f = 1;
    char ch = getchar ();
    while (ch < '0' || ch > '9') {
        if (ch == '-')
            f = - 1;
        ch = getchar ();
    }
    while (ch >= '0' && ch <= '9') {
        x = x * 10 + ch - '0';
        ch = getchar ();
    }
    return x * f;
}

void print (i128 x) {
    if (x < 0){
        putchar ('-');
        x = - x;
    }
    if (x > 9)
        print (x / 10);
    putchar (x % 10 + '0');
}

树状数组

template <typename T>
struct Fenwick {
    int n;
    std::vector<T> a;
    
    Fenwick(int n_ = 0) {
        init(n_);
    }
    
    void init(int n_) {
        n = n_;
        a.assign(n, T{});
    }
    
    void add(int x, const T &v) {
        for (int i = x + 1; i <= n; i += i & -i) {
            a[i - 1] = a[i - 1] + v;
        }
    }
    
    T sum(int x) {
        T ans{};
        for (int i = x; i > 0; i -= i & -i) {
            ans = ans + a[i - 1];
        }
        return ans;
    }
    
    T rangeSum(int l, int r) {
        return sum(r) - sum(l);
    }
    
    int select(const T &k) {
        int x = 0;
        T cur{};
        for (int i = 1 << std::__lg(n); i; i /= 2) {
            if (x + i <= n && cur + a[x + i - 1] <= k) {
                x += i;
                cur = cur + a[x - 1];
            }
        }
        return x;
    }
};

快速幂

$计算a^{b}\mod p$

#define int long long
int qpow(int a, int b, int p) {  
    int res = 1;  
    a %= p;  
    while (b) {  
        if (b & 1) res = res * a % p;  
        a = a * a % p;  
        b >>= 1;  
    }  
    return res;  
}

大数乘法

#define int long long
int bigMul(int a, int b, int p) {  
    unsigned int c =  
            (unsigned int) a * b -  
            (unsigned int) ((long double) a / p * b + 0.5L) * p;  
    if (c < p) return c;  
    return c + p;  
}

并查集(DSU)

普通DSU

class DSU {
public:
    std::vector<int> f;

    DSU(int n) {
        f.assign(n + 1, 0ll);
        std::iota(f.begin(), f.end(), 0ll);
    }

    int find(int x) {
        return x == f[x] ? x : f[x] = find(f[x]);
    }

    void combine(int x, int y) {
        x = find(x), y = find(y);
        if(x == y) return;
        f[y] = x;
    }

    bool same(int x, int y) {
        return find(x) == find(y);
    }
};

可查询集合大小的DSU

class DSU {
public :
    std::vector<int> f, siz;

    DSU(int n) {
        init(n);
    }

    void init(int n) {
        f.resize(n + 1);
        std::iota(f.begin(), f.end(), 0);
        siz.assign(n + 1, 1);
    }

    int find(int x) {
        while (x != f[x]) x = f[x] = f[f[x]];
        return x;
    }

    bool same(int x, int y) {
        return find(x) == find(y);
    }

    void merge(int x, int y) {
        x = find(x);
        y = find(y);
        if (x == y)
            return;
        siz[x] += siz[y];
        f[y] = x;
    }

    int size(int x) {
        return siz[find(x)];
    }
};

欧拉筛

std::vector<int> minp, primes;

void sieve(int n) {
    minp.assign(n + 1, 0);
    primes.clear();
    
    for (int i = 2; i <= n; i++) {
        if (minp[i] == 0) {
            minp[i] = i;
            primes.push_back(i);
        }
        
        for (auto p : primes) {
            if (i * p > n) {
                break;
            }
            minp[i * p] = p;
            if (p == minp[i]) {
                break;
            }
        }
    }
}

[[最短路问题]]

朴素Dijkstra

class Dijkstra {
public:
    std::vector<int> dijkstra(int n, std::vector<std::vector<int> > &a) {//求1到各个点的最短路
        std::vector<bool> f(n + 1, false);
        std::vector<int> dis(n + 1, INF);
        dis[1] = 0;
        for (int i = 0; i < n - 1; i++) {//注意此处只需要遍历n-1次
            int pos = -1;
            for (int j = 1; j <= n; j++)//查找未经过,并且路径最短的点
                if (!f[j] && (pos == -1 || dis[j] < dis[pos]))
                    pos = j;
            for (int j = 1; j <= n; j++)
                dis[j] = std::min(dis[pos] + a[pos][j], dis[j]);
            f[pos] = true;
        }
        return dis;
    }
};

堆优化Dijkstra

class Dijkstra {
public :
    static std::vector<int> dijkstra(int n, std::vector<std::vector<pii> > &a) {
        std::priority_queue<pii, std::vector<pii>, std::greater<> > q;
        std::vector<int> dis(n + 1, INF);
        std::vector<bool> f(n + 1, false);
        dis[1] = 0ll;
        q.emplace(dis[1], 1);//{1-x的距离,节点编号
        while (!q.empty()) {
            auto [x, y] = q.top();
            q.pop();
            if (f[y]) continue;
            f[y] = true;
            for (auto i: a[y]) {
                auto [v, w] = i; //{x能到的节点x, x-v的距离}
                if (dis[v] > w + x) {
                    dis[v] = w + x;
                    q.emplace(dis[v], v);
                }
            }
        }
        return dis;
    }
};

存在负权边的BellmanFord(k条路径的最短路)

typedef struct edge {
    int u, v, w;
} E;

class Bellmanford {
public:
    static std::vector<int> bellmanford(int n, int k, int m, std::vector<E> &a) {
        std::vector<int> dis(n + 1, INF);
        std::vector<bool> f(n + 1, false);
        dis[1] = 0;
        for (int i = 1; i <= k; i++) {
            auto t = dis;
            for (int j = 0; j < m; j++) {
                auto [u, v, w] = a[j];
                dis[v] = std::min(t[u] + w, dis[v]);
            }
        }
        return dis;
    }
};

存在负权边的spfa

class Spfa {
public :
    static std::vector<int> spfa(int n, const std::vector<std::vector<pii> > &a) {
        std::vector<int> dis(n + 1, INF);
        std::vector<bool> f(n + 1, false);
        std::queue<pii> q;//其实这里可以只需要queue<int>
        dis[1] = 0, f[1] = true;
        q.emplace(dis[1], 1);
        while (!q.empty()) {
            auto [x, y] = q.front();
            q.pop();
            f[y] = false;
            for (auto [v, w]: a[y]) {
                if (dis[v] > dis[y] + w) {
                    dis[v] = dis[y] + w;
                    if (!f[v]) {
                        q.emplace(dis[v], v);
                        f[v] = true;
                    }
                }
            }
        }
        return dis;
    }
};

Floyd(多源汇最短路)

class Floyd {
public :
    static std::vector<std::vector<int> > floyd(int n, std::vector<std::vector<int> > &a) {
        for (int k = 1; k <= n; k++)
            for (int i = 1; i <= n; i++)
                for (int j = 1; j <= n; j++)
                    if (i != j)
                        a[i][j] = std::min(a[i][j], a[i][k] + a[k][j]);
                    else a[i][j] = 0;
//特别注意i==j的情况
        return a;
    }
};

[[图论]]

Prime

class Prime {
public :
    static int getMST(int n, std::vector<std::vector<int>> &a) {
        std::vector<int> dis(n + 1, INF);
        std::vector<bool> f(n + 1, false);
        dis[1] = 0;
        int res = 0;
        for (int i = 0; i < n; i++) {
            int pos = -1;
            for (int j = 1; j <= n; j++)
                if (!f[j] && (pos == -1 || dis[pos] > dis[j]))
                    pos = j;
            f[pos] = true;
            res += dis[pos];
            if (i && dis[pos] == INF)
                return INF + INF;
            for (int j = 1; j <= n; j++)
                dis[j] = std::min(dis[j], a[pos][j]);
        }
        return res;
    }
};

Kruskal

class Kruskal {
public :
    struct E {
        int u, v, w;

        bool friend operator<(const E &a, const E &b) {
            return a.w < b.w;
        }
    };

    int n{}, m{};
    std::vector<E> a;
    std::vector<int> f;

    void init() {
        std::cin >> n >> m;
        a.assign(m, {0, 0, 0});
        for (int i = 0; i < m; i++) {
            int u, v, w;
            std::cin >> u >> v >> w;
            a[i] = {u, v, w};
        }
    }

    int find(int x) {
        return x == f[x] ? x : f[x] = find(f[x]);
    }

    int GetMST() {
        int res = 0, cnt = 0;
        f.assign(n + 1, 0ll);
        std::iota(f.begin(), f.end(), 0ll);
        std::sort(a.begin(), a.end());
        for (int i = 0; i < m; i++) {
            auto [u, v, w] = a[i];
            int x = find(u), y = find(v);
            if (x != y) {
                cnt++, res += w;
                f[y] = x;
            }
        }
        if (cnt != n - 1)
            return INF + INF;
        return res;
    }
};

[[图论]]

染色法(判断是否为二分图)

class drawBinaryGraph {
public:
    int n{}, m{};
    std::vector<std::vector<int>> a;
    std::vector<int> color;

    void init() {
        std::cin >> n >> m;
        a.assign(n + 1, std::vector<int>());
        color.assign(n + 1, 0);
        for (int i = 0; i < m; i++) {
            int u, v;
            std::cin >> u >> v;
            a[u].push_back(v);
            a[v].push_back(u);
        }
    }

    bool dfs(int u, int c) {
        color[u] = c;
        for (int i = 0; i < a[u].size(); i++) {
            int t = a[u][i];
            if (!color[t]) {
                if (!dfs(t, 3 - c))
                    return false;
            } else if (color[t] == c)
                return false;
        }
        return true;
    }

    bool isBinaryGraph() {
        bool t = true;
        for (int i = 1; i <= n; i++)
            if (!color[i])
                if (!dfs(i, 1)) {
                    t = false;
                    break;
                }
        return t;
    }
};

匈牙利算法

class Hungary {
  public:
  int n1, n2, m;
  std::vector<std::vector<int>> l;
  std::vector<int> r;
  std::vector<bool> f;

  void init() {
    std::cin >> n1 >> n2 >> m;
    l.assign(n1 + 1, std::vector<int>());
    r.assign(n2 + 1, 0ll);
    f.assign(n2 + 1, false);
    for(int i = 0; i < m; i++) {
      int u, v;
      std::cin >> u >> v;
      l[u].push_back(v);
    }
  }

  bool find(int x) {
    for(int i = 0; i < l[x].size(); i++) {
      int j = l[x][i];
      if(!f[j]) {
        f[j] = true;
        if(r[j] == 0 || find(r[j])) {
          r[j] = x;
          return true;
        }
      }
    }
    return false;
  }

  int maxMatch() {
    int ans = 0;
    for(int i = 1; i <= n1; i++) {
      std::fill(f.begin(), f.end(), false);
      if(find(i))
        ans++;
    }
    return ans;
  }
};

---

数论

组合数

int C(int n, int m) {
  if (m > n) return 0;
  int  ans = 1;
  for (int i = 1;i <= m;i++) {
    ans = ans * (n - m + i) / i;
  }
  return ans;
}