快读函数

inline ll read()
{
  ll t = 0, dp = 1; char c = getchar();
  while(!isdigit(c)){if (c == '-') dp = -1; c = getchar();}
  while(isdigit(c)) t = t * 10 + c - 48, c = getchar();
  return t * dp;
}

进制转换

inline int base10(int x, int k) // K进制转十进制
{
  int ret = 0, w = 0;
  for (; x; x /= 10, w ++)
  {
    ret += (x % 10) * pow(k, w);
  }
  return ret;
}

inline int basek(int x, int k) // 十进制转K进制(k <= 10)
{
  string ret;
  for (; x; x /= k)
  {
    int now = x % k;
    ret += ('0' + now);
  }
  reverse(ret.begin(), ret.end());
  return stoll(ret);
}
// 如果K>10只需要对对应字符进行map匹配

并查集

struct dsu
{
  vector<int> fa, sz;

  dsu(int n) : fa(n), sz(n, 1){iota(fa.begin(), fa.end(), 0);}
  int find(int x){while (x != fa[x]) x = fa[x] = fa[fa[x]]; return x;}
  bool same(int x, int y){return find(x) == find(y);}
  bool merge(int x, int y)
  {
    x = find(x); y = find(y);
    if (x == y) return false;
    sz[x] += sz[y];
    fa[y] = x;
    return true;
  }
  int size(int x){return sz[find(x)];}
};

关闭同步流

  ios::sync_with_stdio(false);
  cin.tie(nullptr);

mint

constexpr int P = 1000000007;
// assume -P <= x < 2P
int norm(int x) 
{
  if (x < 0) x += P;
  if (x >= P) x -= P;
  return x;
}
template<class T>
T qpow(T a, int b) 
{
  T res = 1;
  for (; b; b /= 2, a *= a) 
  {
    if (b % 2) res *= a;
  }
  return res;
}
struct Z
{
  int x;
  Z(int x = 0) : x(norm(x)){}
  int val()const{return x;}
  Z operator - ()const{return Z(norm(P - x));}
  Z inv()const {assert(x != 0); return qpow(*this, P - 2);}
  Z &operator *= (const Z &rhs){x = x * rhs.x % P; return *this;}
  Z &operator += (const Z &rhs){x = norm(x + rhs.x); return *this;}
  Z &operator -= (const Z &rhs){x = norm(x - rhs.x); return *this;}
  Z &operator /= (const Z &rhs){return *this *= rhs.inv();}
  friend Z operator * (const Z &lhs, const Z &rhs){Z ret = lhs; ret *= rhs; return ret;}
  friend Z operator + (const Z &lhs, const Z &rhs){Z ret = lhs; ret += rhs; return ret;}
  friend Z operator - (const Z &lhs, const Z &rhs){Z ret = lhs; ret -= rhs; return ret;}
  friend Z operator / (const Z &lhs, const Z &rhs){Z ret = lhs; ret /= rhs; return ret;}
};

高精加

高精乘

vector<int> Mul(vector<int> A, int x)
{
  vector<int> Ret;
  int t = 0, len = A.size();
  for (int i = 0; i < len; i ++)
  {
    t += A[i] * x;
    Ret.push_back(t % 10);
    t /= 10;
  }
  for (; t; t /= 10) Ret.push_back(t % 10);
  return Ret;
}

快速幂

inline int qpow(int x, int y, int z){int ret = 1; for (; y; y /= 2, x = x * x % z) if (y & 1) ret = ret * x % z; return ret;}

快速乘

inline int qmul(int x, int y, int z){int res = 0; for (; y; y /= 2, x = x * 2 % z) if (y & 1) res = (res + x) % z; return res;}

素数逆元

inline int Prime(int x, int y, int z){return qpow(x, y - 2, z);}

扩展欧几里得算法

inline int exgcd(int a, int b, int &x, int &y)
{
  if (!b) return x = 1, y = 0, a;
  int ret = exgcd(b, a % b, x, y);
  tie(x, y) = make_tuple(y, x - (a / b) * y);
  return ret;
}

exgcd求逆元

inline int Inv(int a, int b)
{
  int x, y; 
  int ret = exgcd(a, b, x, y);
  return (ret == 1) ? (x % mod + mod) % mod : -1;
}

中国剩余定理

inline int qpow(int x, int y, int z){int ret = 1; for (; y; y /= 2, x = x * x % z) if (y & 1) ret = ret * x % z; return ret;}
inline int qmul(int x, int y, int z){int res = 0; for (; y; y /= 2, x = x * 2 % z) if (y & 1) res = (res + x) % z; return res;}
inline int PrimeInv(int x, int y, int z){return qpow(x, y - 2, z);}

int m[20], c[20];

inline int exgcd(int a, int b, int &x, int &y)
{
  if (!b)
  {
    x = 1;
    y = 0;
    return a;
  }
  int res = exgcd(b, a % b, x, y);
  int t = x;
  x = y;
  y = t - a / b * y;
  return res;
}

inline int Inv(int a, int b)
{
  int x, y; 
  int ret = exgcd(a, b, x, y);
  return (ret == 1) ? (x % mod + mod) % mod : -1;
}

signed main()
{
  int k = read();
  int M = 1, ans = 0;
  For(i,1,k) 
  {
    m[i] = read();
    c[i] = read();
    M *= m[i];
  }
  For(i,1,k)
  {
    int res = qmul(c[i], (M / m[i]), M);
    res = qmul(res, Inv(M / m[i], m[i]), M);
    (ans += res) %= M;
  }
  writeln(ans);

  return 0;
}

2000组合数

inline void init()
{
  for (int i = 0; i < maxn; i ++)
  {
    for (int j = 0; j <= i; j ++)
    {
      if (j == 0) C[i][j] = 1;
      else C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % P;
    }
  }
}

2e5组合数

inline int qpow(int x, int y, int z){int ret = 1; for (; y; y /= 2, x = x * x % z) if (y & 1) ret = ret * x % z; return ret;}
inline void init()
{
  fact[0] = 1;
  for (int i = 1; i <= maxn; i ++) fact[i] = fact[i - 1] * i % P;
  infact[maxn] = qpow(fact[maxn], P - 2, P);
  for (int i = maxn; i >= 1; -- i) infact[i - 1] = infact[i] * i % P;
}
inline int C(int x, int y){return x >= y && y >= 0 ? fact[x] * infact[y] % P * infact[x - y] % P : 0;}

Lucas求i64组合数

inline int C(int x, int y, int P)
{
  if (y > x) return 0;
  int ret = 1;
  for (int i = 1, j = x; i <= y; i ++, -- j)
  {
    ret = ret * j % P;
    ret = ret * qpow(i, P - 2, P) % P;
  }
  return ret;
}
inline int Lucas(int x, int y, int P)
{
  if (x < P && y < P) return C(x, y, P);
  return C(x % P, y % P, P) * Lucas(x / P, y / P, P) % P;
}

高精组合数

const int maxn = 5005;
int Prime[maxn], cnt;
int sum[maxn];
bool NotPrime[maxn];

inline void EulerSieve(int x)
{
  for (int i = 2; i <= x; i ++)
  {
    if (!NotPrime[i]) Prime[cnt ++] = i;
    for (int j = 0; Prime[j] <= x / i; j ++)
    {
      NotPrime[i * Prime[j]] = true;
      if (i % Prime[j] == 0) break;
    }
  }
}

inline int Count(int x, int P)
{
  int ret = 0; while (x){ret += x / P; x /= P;} return ret;
}

vector<int> Mul(vector<int> A, int x)
{
  vector<int> Ret;
  int t = 0, len = A.size();
  for (int i = 0; i < len; i ++)
  {
    t += A[i] * x;
    Ret.push_back(t % 10);
    t /= 10;
  }
  for (; t; t /= 10) Ret.push_back(t % 10);
  return Ret;
}
signed main()
{
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int a, b; cin >> a >> b;
  EulerSieve(a);
  for (int i = 0; i < cnt; i ++)
  {
    int p = Prime[i];
    sum[i] = Count(a, p) - Count(a - b, p) - Count(b, p);
  }
  vector<int> res; res.push_back(1);
  for (int i = 0; i < cnt; i ++)
  {
    for (int j = 0; j < sum[i]; j ++)
    {
      res = Mul(res, Prime[i]);
    }
  }
  reverse(res.begin(), res.end());
  for (int &x : res) cout << x;
  return 0;
}

旋转

point turn(double kl)
{
  return (point){x * cos(kl) - y * sin(kl), x * sin(kl) + y * cos(kl)};
}

计算几何

const int maxn = 1005;
const double eps = 1e-5;

inline int sgn(double x){return fabs(x) < eps ? 0 : (x < 0 ? -1 : 1);}
inline int cmp(double x, double y){return sgn(x - y);}

struct Point
{
  double x;
  double y;
};
typedef Point Vector;
Vector operator + (Vector a, Vector b){return (Vector){a.x + b.x, a.y + b.y};} //点的四则运算
Vector operator - (Vector a, Vector b){return (Vector){a.x - b.x, a.y - b.y};}
Vector operator * (Vector a, double b){return (Vector){a.x * b, a.y * b};}
Vector operator / (Vector a, double b){return (Vector){a.x / b, a.y / b};}
double operator & (Vector a, Vector b){return a.x * b.x + a.y * b.y;} // 点积
double operator ^ (Vector a, Vector b){return a.x * b.y - a.y * b.x;} // 叉积
double PointDistance(Point a, Point b){return sqrt((b - a) & (b - a));} // 点距

struct Line // 直线
{
  Point Pa;
  Point Pb;
};
typedef Line Segment; // 线段 
double LineDistance(Line a, Segment b){return ((b.Pa - a.Pa) ^ (b.Pb - a.Pa)) / ((b.Pb - b.Pa) ^ (a.Pb - a.Pa)) * PointDistance(a.Pa, a.Pb);}
// 平行线距
struct Status
{
  double Length;
  int Flag;
};
inline bool operator < (Status a, Status b){return sgn(b.Length - a.Length) > 0;}

inline bool InLine(double x, double y, double z){return sgn(x - z) * sgn(y - z) <= 0;}
inline bool InLine(Point P1, Point P2, Point P3){return InLine(P1.x, P2.x, P3.x) && InLine(P1.y, P2.y, P3.y);} // 共线

inline double Cross(Point P1, Point P2, Point P3)
{
  return (P1.x - P3.x) * (P2.y - P3.y) - (P1.y - P3.y) * (P2.x - P3.x);
}

inline Point GetCrossPoint(Point P1, Point P2, Point P3, Point P4) // 求交点
{
  double W1 = (P1 - P3) ^ (P4 - P3), W2 = (P4 - P3) ^ (P2 - P3);
  return (Point)((P1 * W2 + P2 * W1) / (W1 + W2));
}

区间调度问题

int N = read(), D = read();
vector<PII> A(N);
For(i,0,N-1)
{
  A[i].fir = read();
  A[i].sec = read();
}
sort(A.begin(), A.end(), [&](const PII &a, const PII &b){return a.sec < b.sec;});
int x = LLONG_MIN, ans = 0;
for (auto [l, r] : A)
{
  if (x + D - 1 < l) ans ++, x = r;
}

线段树单点修改

// code of JUYU ^ ^ never doubt youself !
#include <bits/stdc++.h>
typedef long long ll;
#define int ll
#define For(i,a,b) for (int i = a; i <= b; i ++)
#define Dow(i,a,b) for (int i = b; i >= a; -- i)
#define ms(a,b) memset(a, b, sizeof (a))
#define fir first
#define sec second
#define mk make_pair
#define pb push_back
#define eb emplace_back
using namespace std;
typedef pair<int,int> PII;

const int mod = 998244353;
const int MOD = 1000000007;
const int maxn = 2e5 + 5;

inline ll read()
{
  ll t = 0, dp = 1; char c = getchar();
  while(!isdigit(c)) {if (c == '-') dp = -1; c = getchar();}
  while(isdigit(c)) t = t * 10 + c - 48, c = getchar();
  return t * dp;
}
inline void write(ll x){if (x < 0){putchar('-'); x = -x;} if(x >= 10) write(x / 10); putchar(x % 10 + 48);}
inline void writeln(ll x){write(x); puts("");}
inline void write_p(ll x){write(x); putchar(' ');}
inline void write_b(ll x){putchar(' '); write(x);}
inline int qpow(int x, int y, int z){int ret = 1; for (; y; y /= 2, x = x * x % z) if (y & 1) ret = ret * x % z; return ret;}
inline int PrimeInv(int x, int y, int z){return qpow(x, y - 2, z);}

int sum[maxn * 4], a[maxn];

inline void update(int x)
{
  sum[x] = sum[x * 2] + sum[x * 2 + 1];
}

inline void build(int x, int l, int r)
{
  if (l == r)
  {
    sum[x] = a[l];
    return ;
  }
  int mid = (l + r) / 2;
  build(x * 2, l, mid);
  build(x * 2 + 1, mid + 1, r);
  update(x);
}

inline int query(int x, int l, int r, int ql, int qr)
{
  if (ql <= l && qr >= r) return sum[x];
  int mid = (l + r) / 2, ret = 0;
  if (ql <= mid) ret += query(x * 2, l, mid, ql, qr);
  if (qr > mid) ret += query(x * 2 + 1, mid + 1, r, ql, qr);
  return ret;
}

inline void change(int x, int l, int r, int v, int k)
{
  if (l == v && r == v)
  {
    sum[x] = k;
    return ;
  }
  int mid = (l + r) / 2;
  if (v <= mid) change(x * 2, l, mid, v, k);
  else change(x * 2 + 1, mid + 1, r, v, k);
  update(x);
}

signed main()
{
  int n = read(), m = read();
  For(i,1,n) a[i] = read();
  build(1, 1, n);
  while (m --)
  {
    int op = read();
    if (op == 1)
    {
      int v = read(), k = read();
      change(1, 1, n, v + 1, k);
    }
    else
    {
      int l = read(), r = read();
      writeln(query(1, 1, n, l + 1, r));
    }
  }

  return 0;
}

线段树区间修改

// code of JUYU ^ ^ never doubt youself !
#include <bits/stdc++.h>
typedef long long ll;
#define int ll
#define For(i,a,b) for (int i = a; i <= b; i ++)
#define Dow(i,a,b) for (int i = b; i >= a; -- i)
#define ms(a,b) memset(a, b, sizeof (a))
#define fir first
#define sec second
#define mk make_pair
#define pb push_back
#define eb emplace_back
using namespace std;
typedef pair<int,int> PII;

const int mod = 998244353;
const int MOD = 1000000007;
const int maxn = 1e5 + 5;

inline ll read()
{
  ll t = 0, dp = 1; char c = getchar();
  while(!isdigit(c)) {if (c == '-') dp = -1; c = getchar();}
  while(isdigit(c)) t = t * 10 + c - 48, c = getchar();
  return t * dp;
}
inline void write(ll x){if (x < 0){putchar('-'); x = -x;} if(x >= 10) write(x / 10); putchar(x % 10 + 48);}
inline void writeln(ll x){write(x); puts("");}
inline void write_p(ll x){write(x); putchar(' ');}
inline void write_b(ll x){putchar(' '); write(x);}
inline int qpow(int x, int y, int z){int ret = 1; for (; y; y /= 2, x = x * x % z) if (y & 1) ret = ret * x % z; return ret;}
inline int PrimeInv(int x, int y, int z){return qpow(x, y - 2, z);}

int a[maxn];
int sum[maxn * 4], tag[maxn * 4];

inline void update(int x)
{
  sum[x] = sum[x * 2] + sum[x * 2 + 1];
}

inline void build(int x, int l, int r)
{
  if (l == r)
  {
    sum[x] = a[l];
    return ;
  }
  int mid = (l + r) / 2;
  build(x * 2, l, mid);
  build(x * 2 + 1, mid + 1, r);
  update(x);
}

inline void pushdown(int x, int l, int r)
{
  int mid = (l + r) / 2;
  sum[x * 2] += tag[x] * (mid - l + 1); tag[x * 2] += tag[x]; 
  sum[x * 2 + 1] += tag[x] * (r - mid); tag[x * 2 + 1] += tag[x]; 
  tag[x] = 0;
}

inline void change(int x, int l, int r, int ql, int qr, int v)
{
  if (ql <= l && qr >= r)
  {
    sum[x] += v * (r - l + 1); tag[x] += v;
    return ;
  }
  pushdown(x, l, r);
  int mid = (l + r) / 2;
  if (ql <= mid) change(x * 2, l, mid, ql, qr, v);
  if (qr > mid) change(x * 2 + 1, mid + 1, r, ql, qr, v);
  update(x);
}

inline int query(int x, int l, int r, int ql, int qr)
{
  if (ql <= l && qr >= r) return sum[x];
  int mid = (l + r) / 2, ans = 0;
  pushdown(x, l, r);
  if (ql <= mid) ans += query(x * 2, l, mid, ql, qr);
  if (qr > mid) ans += query(x * 2 + 1, mid + 1, r, ql, qr);
  return ans;
}

signed main()
{
  int n = read(), m = read();
  For(i,1,n) a[i] = read();
  build(1, 1, n);
  while (m --)
  {
    int op = read();
    if (op == 1)
    {
      int l = read(), r = read(), k = read();
      change(1, 1, n, l, r, k);
    }
    else
    {
      int l = read(), r = read();
      writeln(query(1, 1, n, l, r));
    }
  }

  return 0;
}

数论分块

// code of JUYU ^ ^ never doubt youself !
#include <bits/stdc++.h>
typedef long long ll;
#define int ll
#define For(i,a,b) for (int i = a; i <= b; i ++)
#define Dow(i,a,b) for (int i = b; i >= a; -- i)
#define ms(a,b) memset(a, b, sizeof (a))
#define fir first
#define sec second
#define mk make_pair
#define pb push_back
#define eb emplace_back
using namespace std;
typedef pair<int,int> PII;

const int mod = 998244353;
const int MOD = 1000000007;
const int maxn = 2e5 + 5;

inline ll read()
{
  ll t = 0, dp = 1; char c = getchar();
  while(!isdigit(c)) {if (c == '-') dp = -1; c = getchar();}
  while(isdigit(c)) t = t * 10 + c - 48, c = getchar();
  return t * dp;
}
inline void write(ll x){if (x < 0){putchar('-'); x = -x;} if(x >= 10) write(x / 10); putchar(x % 10 + 48);}
inline void writeln(ll x){write(x); puts("");}
inline void write_p(ll x){write(x); putchar(' ');}
inline void write_b(ll x){putchar(' '); write(x);}
inline int qpow(int x, int y, int z){int ret = 1; for (; y; y /= 2, x = x * x % z) if (y & 1) ret = ret * x % z; return ret;}
inline int qmul(int x, int y, int z){int res = 0; for (; y; y /= 2, x = x * 2 % z) if (y & 1) res = (res + x) % z; return res;}
inline int PrimeInv(int x, int y, int z){return qpow(x, y - 2, z);}

const int P = mod;

signed main()
{
  int N = read(), K = read();
  int ans = N * K;
  for (int l = 1, r; l <= min(N, K); l = r + 1)
  {
    r = min(N, K / (K / l));
    ans -= (r - l + 1) * (K / l) * (l + r) / 2;
  }
  writeln(ans);

  return 0;
}

/* stuff you should look for
 * int overflow, array bounds
 * special cases (n=1?)
 * do smth instead of nothing and stay organized
 * WRITE STUFF DOWN
 * DON'T GET STUCK ON ONE APPROACH
 -- Benq
*/

Min25筛

// code of JUYU ^ ^ never doubt youself !
#include <bits/stdc++.h>
typedef long long ll;
#define int ll
#define For(i,a,b) for (int i = a; i <= b; i ++)
#define Dow(i,a,b) for (int i = b; i >= a; -- i)
#define ms(a,b) memset(a, b, sizeof (a))
#define fir first
#define sec second
#define mk make_pair
#define pb push_back
#define eb emplace_back
using namespace std;
typedef pair<int,int> PII;

const int mod = 998244353;
const int MOD = 1000000007;
const int maxn = 1e6 + 5;

inline ll read()
{
  ll t = 0, dp = 1; char c = getchar();
  while(!isdigit(c)) {if (c == '-') dp = -1; c = getchar();}
  while(isdigit(c)) t = t * 10 + c - 48, c = getchar();
  return t * dp;
}
inline void write(ll x){if (x < 0){putchar('-'); x = -x;} if(x >= 10) write(x / 10); putchar(x % 10 + 48);}
inline void writeln(ll x){write(x); puts("");}
inline void write_p(ll x){write(x); putchar(' ');}
inline void write_b(ll x){putchar(' '); write(x);}
inline int qpow(int x, int y, int z){int ret = 1; for (; y; y /= 2, x = x * x % z) if (y & 1) ret = ret * x % z; return ret;}
inline int qmul(int x, int y, int z){int res = 0; for (; y; y /= 2, x = x * 2 % z) if (y & 1) res = (res + x) % z; return res;}
inline int PrimeInv(int x, int y, int z){return qpow(x, y - 2, z);}

int n, tot;
const int INV1 = 500000004, INV2 = 333333336;
int num, Prime[maxn];
bool NotPrime[maxn];
int P1[maxn], P2[maxn];
int sqr, G1[maxn], G2[maxn], W[maxn], id1[maxn], id2[maxn];

inline void EulerSieve(int n)
{
  for (int i = 2; i <= n; i ++)
  {
    if (!NotPrime[i])
    {
      Prime[++ num] = i;
      P1[num] = (P1[num - 1] + i) % MOD;
      P2[num] = (P2[num - 1] + i * i) % MOD;
    }
    for (int j = 1; j <= num && Prime[j] <= n / i; j ++)
    {
      NotPrime[i * Prime[j]] = true;
      if (i % Prime[j] == 0) break;
    }
  }
}

inline int Count(int x, int y)
{
  if (Prime[y] > x) return 0;
  int k = (x <= sqr ? id1[x] : id2[n / x]);
  int ans = (G2[k] - G1[k] + MOD - (P2[y - 1] - P1[y - 1]) + MOD) % MOD;
  for (int i = y; i <= num && Prime[i] <= x / Prime[i]; i ++)
  {
    int Pi = Prime[i];
    for (int j = 1; Pi <= x; j ++, Pi *= Prime[i])
    {
      int t = Pi % MOD;
      ans = (ans + t * (t - 1) % MOD * (Count(x / Pi, i + 1) + (j != 1))) % MOD;
    }
  }
  return ans % MOD;
}

inline void Min25()
{
  for (int i = 1; i <= n; )
  {
    int j = n / (n / i);
    W[++ tot] = n / i;
    G1[tot] = W[tot] % MOD;
    G2[tot] = G1[tot] * (G1[tot] + 1) / 2 % MOD * (2 * G1[tot] + 1) % MOD * INV2 % MOD;
    G2[tot] --;
    G1[tot] = G1[tot] * (G1[tot] + 1) / 2 % MOD - 1;
    if (n / i <= sqr) id1[n / i] = tot;
    else id2[n / (n / i)] = tot;
    i = j + 1;
  }
  for (int i = 1; i <= num; i ++)
  {
    for (int j = 1; j <= tot && Prime[i] <= W[j] / Prime[i]; j ++)
    {
      int k = W[j] / Prime[i]; k = k <= sqr ? id1[k] : id2[n / k];
      G1[j] -= Prime[i] * (G1[k] - P1[i - 1] + MOD) % MOD;
      G2[j] -= Prime[i] * Prime[i] % MOD * (G2[k] - P2[i - 1] + MOD) % MOD;
      G1[j] %= MOD; G2[j] %= MOD;
    }
  }
}

signed main()
{
  n = read();
  sqr = (int)sqrt(n);
  EulerSieve(sqr + 100);
  Min25();
  int ans = Count(n, 1) + 1;
  ans = (ans % MOD + MOD) % MOD;
  writeln(ans);

  return 0;
}

/* stuff you should look for
 * int overflow, array bounds
 * special cases (n=1?)
 * do smth instead of nothing and stay organized
 * WRITE STUFF DOWN
 * DON'T GET STUCK ON ONE APPROACH
 -- Benq
*/

稀疏表

struct DualSpareTable
{
  int n, Log;
  vector<vector<int>> ST;
  DualSpareTable(int n) : n(n)
  {
    Log = 32 - __builtin_clz(n);
    ST = vector<vector<int>> (Log, vector<int>(n, INF));
  }
  void RangeChmin(int l, int r, int x)
  {
    int d = 31 - __builtin_clz(r - l);
    ST[d][l] = min(ST[d][l], x);
    ST[d][r - (1 << d)] = min(ST[d][r - (1 << d)], x);
  }
  vector<int> Get()
  {
    for (int i = Log - 2; i >= 0; -- i)
    {
      for (int j = 0; j < n - (1 << i); j ++)
      {
        ST[i][j] = min(ST[i][j], ST[i + 1][j]);
        ST[i][j + (1 << i)] = min(ST[i][j + (1 << i)], ST[i + 1][j]);
      }
    }
    return ST[0];
  }
};

最大流

struct Flow {
    int n;
    struct Edge {
        int to;
        i64 cap;
        Edge(int to, i64 cap) : to(to), cap(cap) {}
    };
    std::vector<Edge> e;
    std::vector<std::vector<int>> g;
    std::vector<int> cur, h;
    Flow(int n) : n(n), g(n) {}
    bool bfs(int s, int t) {
        h.assign(n, -1);
        std::queue<int> que;
        h[s] = 0;
        que.push(s);
        while (!que.empty()) {
            int u = que.front();
            que.pop();
            for (int i : g[u]) {
                int v = e[i].to;
                i64 c = e[i].cap;
                if (c > 0 && h[v] == -1) {
                    h[v] = h[u] + 1;
                    if (v == t)
                        return true;
                    que.push(v);
                }
            }
        }
        return false;
    }
    i64 dfs(int u, int t, i64 f) {
        if (u == t)
            return f;
        i64 r = f;
        for (int &i = cur[u]; i < int(g[u].size()); ++i) {
            int j = g[u][i];
            int v = e[j].to;
            i64 c = e[j].cap;
            if (c > 0 && h[v] == h[u] + 1) {
                i64 a = dfs(v, t, std::min(r, c));
                e[j].cap -= a;
                e[j ^ 1].cap += a;
                r -= a;
                if (r == 0)
                    return f;
            }
        }
        return f - r;
    }
    void addEdge(int u, int v, i64 c) {
        g[u].push_back(e.size());
        e.emplace_back(v, c);
        g[v].push_back(e.size());
        e.emplace_back(u, 0);
    }
    i64 maxFlow(int s, int t) {
        i64 ans = 0;
        while (bfs(s, t)) {
            cur.assign(n, 0);
            ans += dfs(s, t, inf);
        }
        return ans;
    }
};

dp注释

  /*
  状态集合:
  策略:
  转移:
  边界:
  */

最小生成树

Kruskal

#include <bits/stdc++.h>
using namespace std;
#define int long long

struct dsu
{
  vector<int> fa, sz;

  dsu(int n) : fa(n), sz(n, 1){iota(fa.begin(), fa.end(), 0);}
  int find(int x){while (x != fa[x]) x = fa[x] = fa[fa[x]]; return x;}
  bool same(int x, int y){return find(x) == find(y);}
  bool merge(int x, int y)
  {
    x = find(x); y = find(y);
    if (x == y) return false;
    sz[x] += sz[y];
    fa[y] = x;
    return true;
  }
  int size(int x){return sz[find(x)];}
};

signed main()
{
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int n, m; cin >> n >> m;
  vector<array<int, 3>> g(m);
  for (auto &[w, u, v] : g)
  {
    cin >> u >> v >> w;
    u --; v --;
  }
  sort(g.begin(), g.end());
  dsu d(n);

  int res = 0, cnt = 0;
  for (auto [w, u, v] : g)
  {
    if (d.same(u, v) == 0)
    {
      d.merge(u, v);
      res += w;
      cnt ++;
    }
  }
  if (cnt < n - 1) cout << "impossible\n";
  else cout << res << "\n";

  return 0;
}

Prim

#include <bits/stdc++.h>
using namespace std;
#define int long long
constexpr int inf = 1e18;
signed main()
{
  ios::sync_with_stdio(0);
  cin.tie(nullptr);

  int n, m; cin >> n >> m;
  vector g(n, vector<int>(n, inf));
  for (int i = 0; i < m; i ++)
  {
    int u, v, w; cin >> u >> v >> w;
    u --; v --;
    g[u][v] = g[v][u] = min(g[u][v], w);
  }

  int res = 0;
  vector<int> dist(n, inf), vis(n);
  for (int i = 0; i < n; i ++)
  {
    int cur = -1;
    for (int j = 0; j < n; j ++)
    {
      if (vis[j] == 0 && (cur == -1 || dist[cur] > dist[j])) cur = j;
    }
    if (i != 0 && dist[cur] == inf) 
    {
      res = inf;
      break;
    }
    if (i != 0) res += dist[cur];
    vis[cur] = 1;
    for (int j = 0; j < n; j ++) dist[j] = min(dist[j], g[cur][j]);
  }

  if (res == inf) cout << "impossible\n";
  else cout << res << "\n";

  return 0;
}