矩阵求逆

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
vc<vc<ll>> inverse(vc<vc<ll>> &a) {
  int n = sz(a);
  vc<vc<ll>> b(n);
  rp(i, n) b[i].resize(n), b[i][i] = 1;
  rp(i, n) {
    int r = -1;
    rep(j, i, n) if (a[j][i]) r = j;
    if (r == -1)
      return {};
    swap(a[r], a[i]), swap(b[r], b[i]);
    ll inv = inverse(a[i][i]);
    rp(j, n) {
      if (j == i)
        continue;
      ll p = a[j][i] * inv % P;
      rp(k, n) {
        a[j][k] -= p * a[i][k] % P;
        if (a[j][k] < 0)
          a[j][k] += P;
        b[j][k] -= p * b[i][k] % P;
        if (b[j][k] < 0)
          b[j][k] += P;
      }
    }
    rp(j, n) a[i][j] = a[i][j] * inv % P, b[i][j] = b[i][j] * inv % P;
  }
  return b;
}

FFT

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
namespace Poly {
const int P = 998244353;
const int G = 3;
int power(int x, int y) {
  int res = 1;
  for (; y; y >>= 1, x = 1ll * x * x % P)
    if (y & 1)
      res = 1ll * res * x % P;
  return res;
}
int inc(int x, int y) { return ((x += y) >= P) ? x - P : x; }
int dec(int x, int y) { return ((x -= y) < 0) ? x + P : x; }
vector<int> rev, rt;
int lim = 1;
void init(const int &len) {
  int l = 0;
  lim = 1;
  while (lim <= len) {
    lim <<= 1, l++;
  }
  rev.resize(lim), rt.resize(lim);
  for (int i = 0; i < lim; i++)
    rev[i] = rev[i >> 1] >> 1 | (i & 1) << l - 1;
  for (int len = 1; len < lim; len <<= 1) {
    int w = power(G, (P ^ 1) / (len << 1));
    rt[len] = 1;
    for (int i = 1; i < len; i++) {
      rt[i + len] = 1ll * rt[i + len - 1] * w % P;
    }
  }
}
void ntt(vector<int> &f) {
  f.resize(lim);
  for (int i = 0; i < lim; i++)
    if (i < rev[i]) {
      swap(f[i], f[rev[i]]);
    }
  for (int len = 1; len < lim; len <<= 1) {
    for (int i = 0; i < lim; i += len << 1) {
      for (int j = 0; j < len; j++) {
        int x = f[i + j], y = 1ll * f[i + j + len] * rt[j + len] % P;
        f[i + j] = inc(x, y), f[i + j + len] = dec(x, y);
      }
    }
  }
}

vector<int> operator*(vector<int> f, vector<int> g) {
  int n = f.size(), m = g.size(), inv;
  init(n + m - 2), inv = power(lim, P - 2), ntt(f), ntt(g);
  for (int i = 0; i < lim; i++)
    f[i] = 1ll * f[i] * g[i] % P;
  reverse(f.begin() + 1, f.end()), ntt(f), f.resize(n + m - 1);
  for (int &x : f)
    x = 1ll * x * inv % P;
  return f;
}
} // namespace Poly
using namespace Poly;

FWT

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
int n, e;
const int P = 998244353;
const int inv2 = (P + 1) / 2;
void convolution_or(vector<int> &f) {
  for (int j = 0; j < e; j++) {
    for (int i = 0; i < n; i++) {
      if (i >> j & 1) {
        f[i] += f[i ^ 1 << j];
        if (f[i] >= P) {
          f[i] -= P;
        }
      }
    }
  }
}
void envolution_or(vector<int> &f) {
  for (int j = 0; j < e; j++) {
    for (int i = 0; i < n; i++) {
      if (i >> j & 1) {
        f[i] -= f[i ^ 1 << j];
        if (f[i] < 0) {
          f[i] += P;
        }
      }
    }
  }
}
void convolution_and(vector<int> &f) {
  for (int j = 0; j < e; j++) {
    for (int i = 0; i < n; i++) {
      if (i >> j & 1) {
        f[i ^ 1 << j] += f[i];
        if (f[i ^ 1 << j] >= P) {
          f[i ^ 1 << j] -= P;
        }
      }
    }
  }
}
void envolution_and(vector<int> &f) {
  for (int j = 0; j < e; j++) {
    for (int i = 0; i < n; i++) {
      if (i >> j & 1) {
        f[i ^ 1 << j] -= f[i];
        if (f[i ^ 1 << j] < 0) {
          f[i ^ 1 << j] += P;
        }
      }
    }
  }
}
void convolution_xor(vector<int> &f) {
  for (int j = 0; j < e; j++) {
    for (int i = 0; i < n; i++) {
      if (i >> j & 1) {
        int x = f[i], y = f[i ^ 1 << j];
        f[i] = y - x;
        if (f[i] < 0) {
          f[i] += P;
        }
        f[i ^ 1 << j] = x + y;
        if (f[i ^ 1 << j] >= P) {
          f[i ^ 1 << j] -= P;
        }
      }
    }
  }
}
void envolution_xor(vector<int> &f) {
  for (int j = 0; j < e; j++) {
    for (int i = 0; i < n; i++) {
      if (i >> j & 1) {
        int x = f[i], y = f[i ^ 1 << j];
        f[i] = y - x;
        if (f[i] < 0) {
          f[i] += P;
        }
        f[i] = (long long)f[i] * inv2 % P;
        f[i ^ 1 << j] = x + y;
        if (f[i ^ 1 << j] >= P) {
          f[i ^ 1 << j] -= P;
        }
        f[i ^ 1 << j] = (long long)f[i ^ 1 << j] * inv2 % P;
      }
    }
  }
}

Z-algo

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include <bits/stdc++.h>
using namespace std;
vector<int> getZ(const string &s) { // s[:Z[i]] = s[i:i+Z[i]]
  vector<int> Z(s.size());
  int N = s.size();
  Z[0] = N;
  for (int i = 1, l = 0, r = 0; i < N; i++) {
    if (i < r) {
      Z[i] = min(Z[i - l], r - i);
    }
    while (i + Z[i] < N && s[i + Z[i]] == s[Z[i]]) {
      Z[i] += 1;
    }
    if (i + Z[i] > r) {
      r = i + Z[i];
      l = i;
    }
  }
  return Z;
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  string a, b;
  cin >> a >> b;
  auto Z = getZ(b + a);
  int N = a.size();
  int M = b.size();
  long long ans = M + 1;
  for (int i = 1; i < M; i++) {
    ans ^= 1ll * (i + 1) * (min(Z[i], M - i) + 1);
  }
  cout << ans << "\n";
  ans = 0;
  for (int i = 0; i < N; i++) {
    ans ^= 1ll * (i + 1) * (min(Z[i + M], M) + 1);
  }
  cout << ans << "\n";
}

kmp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <bits/stdc++.h>
using namespace std;
int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  string s1, s2;
  cin >> s1 >> s2;
  int n = (int)s1.size();
  int m = (int)s2.size();
  vector<int> nxt(m, -1);
  for (int i = 1, j = -1; i < m; i++) {
    while (~j && s2[i] != s2[j + 1]) {
      j = nxt[j];
    }
    if (s2[i] == s2[j + 1]) {
      j++;
    }
    nxt[i] = j;
  }
  for (int i = 0, j = -1; i < n; i++) {
    while (~j && s1[i] != s2[j + 1]) {
      j = nxt[j];
    }
    if (s1[i] == s2[j + 1]) {
      j++;
    }
    if (j == m - 1) {
      cout << i - m + 2 << "\n";
      j = nxt[j];
    }
  }
  for (int i = 0; i < m; i++) {
    cout << nxt[i] + 1 << " \n"[i + 1 == m];
  }
}

SAM

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include <bits/stdc++.h>
using namespace std;
const int N = 1048576 * 2;
int ch[N][26];
int fa[N];
int len[N];
int val[N];
int cnt = 1, lst = 1;
void extend(int c) {
  int p = lst, np = lst = ++cnt;
  val[np] = 1;
  len[np] = len[p] + 1;
  while (!ch[p][c]) {
    ch[p][c] = np;
    p = fa[p];
  }
  if (!p) {
    fa[np] = 1;
  } else {
    int q = ch[p][c];
    if (len[q] == len[p] + 1) {
      fa[np] = q;
    } else {
      int nq = ++cnt;
      len[nq] = len[p] + 1;
      memcpy(ch[nq], ch[q], sizeof ch[q]);
      fa[nq] = fa[q];
      fa[q] = fa[np] = nq;
      while (ch[p][c] == q) {
        ch[p][c] = nq;
        p = fa[p];
      }
    }
  }
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  string s;
  cin >> s;
  int n = (int)s.size();
  for (int i = 0; i < n; i++) {
    extend(s[i] - 'a');
  }
  vector<vector<int>> g(cnt + 1);
  for (int i = 1; i <= cnt; i++) {
    g[fa[i]].push_back(i);
  }
  long long ans = 0;
  function<void(int)> dfs = [&](int u) {
    for (auto v : g[u]) {
      dfs(v);
      val[u] += val[v];
    }
    if (val[u] > 1) {
      ans = max(ans, (long long)val[u] * len[u]);
    }
  };
  dfs(1);
  cout << ans << "\n";
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
// 广义 SAM
#include <bits/stdc++.h>
using namespace std;
const int N = 1048576 * 2;
int ch[N][26];
int fa[N];
int len[N];
int val[N];
int cnt = 1;
int extend(int c, int lst) {
  int p = lst, np = lst = ++cnt;
  val[np] = 1;
  len[np] = len[p] + 1;
  while (!ch[p][c]) {
    ch[p][c] = np;
    p = fa[p];
  }
  if (!p) {
    fa[np] = 1;
  } else {
    int q = ch[p][c];
    if (len[q] == len[p] + 1) {
      fa[np] = q;
    } else {
      int nq = ++cnt;
      len[nq] = len[p] + 1;
      memcpy(ch[nq], ch[q], sizeof ch[q]);
      fa[nq] = fa[q];
      fa[q] = fa[np] = nq;
      while (ch[p][c] == q) {
        ch[p][c] = nq;
        p = fa[p];
      }
    }
  }
  return np;
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  vector<array<int, 26>> son;
  son.emplace_back();
  int t;
  cin >> t;
  while (t--) {
    string s;
    cin >> s;
    int p = 0;
    for (char ch : s) {
      int c = ch - 'a';
      if (!son[p][c]) {
        son[p][c] = son.size();
        son.emplace_back();
      }
      p = son[p][c];
    }
  }
  queue<int> q;
  vector<int> pos(son.size());
  pos[0] = 1;
  q.emplace(0);
  while (!q.empty()) {
    int u = q.front();
    q.pop();
    for (int i = 0; i < 26; i++) {
      int v = son[u][i];
      if (v == 0) {
        continue;
      }
      pos[v] = extend(i, pos[u]);
      q.emplace(v);
    }
  }
  long long ans = 0;
  for (int i = 2; i <= cnt; i++) {
    ans += len[i] - len[fa[i]];
  }
  cout << ans << "\n";
  cout << cnt << "\n";
}

PAM

$cnt_i$ 表示 $i$ 节点的表示的字符串出现了多少次，$len_i$ 表示 $i$ 节点的长度，$num_i$ 表示以 $i$ 节点表示的字符串的后缀有多少个回文串。

$fail_i$ 表示 $i$ 节点指向的是这个节点的最长回文后缀。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#include <bits/stdc++.h>
using namespace std;
const int N = 2000000;
struct PAM {
  PAM() { init(); }
  int fail[N + 2];
  int len[N + 2];
  int cnt[N + 2];
  int num[N + 2];
  int s[N + 2];
  struct Edge {
    int v, nxt, w;
  } e[N + 2];
  int head[N + 2];
  int ec;
  void link(int u, int v, int w) {
    e[++ec] = {v, head[u], w};
    head[u] = ec;
  }
  int n, p, last;
  void init() {
    n = 0;
    p = 0;
    ec = 0;
    s[0] = -1;
    newnode(0);
    newnode(-1);
    last = 0;
    fail[0] = 1;
  }
  int newnode(int l) {
    head[p] = 0;
    cnt[p] = 0;
    num[p] = 0;
    len[p] = l;
    return p++;
  }
  int getfail(int x) {
    while (s[n - len[x] - 1] != s[n]) {
      x = fail[x];
    }
    return x;
  }
  int find(int cur, int c) {
    for (int i = head[cur]; i; i = e[i].nxt) {
      if (e[i].w == c) {
        return e[i].v;
      }
    }
    return 0;
  }
  void insert(int c) {
    s[++n] = c;
    int cur = getfail(last);
    if (!find(cur, c)) {
      int now = newnode(len[cur] + 2);
      fail[now] = find(getfail(fail[cur]), c);
      link(cur, now, c);
      num[now] = num[fail[now]] + 1;
    }
    last = find(cur, c);
    cnt[last]++;
  }
} pt;

int main() {
  string s;
  cin >> s;
  int N = s.size();
  int ans = 0;
  for (int i = 0; i < N; i++) {
    int c = s[i] - 97;
    c = (c + ans) % 26;
    pt.insert(c);
    cout << (ans = pt.num[pt.last]) << " \n"[i + 1 == N];
  }
}

ACAM

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#include <cstdio>
#include <cstring>
#include <queue>
#include <vector>
#define pb emplace_back
using namespace std;

int read() {
  int x = 0;
  char c = getchar();
  while (c < 48)
    c = getchar();
  while (c > 47)
    x = x * 10 + (c - 48), c = getchar();
  return x;
}

const int maxn = 2e6 + 52;

int n, len = 0;
char s[maxn];
int fa[maxn], ch[maxn][26], fail[maxn], cnt = 1;
int ed[maxn];

void rs() {
  scanf("%s", s);
  len = strlen(s);
}

int ins() {
  int p = 1;
  for (int i = 0; i < len; i++) {
    int c = s[i] - 'a';
    if (!ch[p][c])
      ch[p][c] = ++cnt, fa[ch[p][c]] = p;
    p = ch[p][c];
  }
  return p;
}

std::vector<int> g[maxn];
int sz[maxn], idx = 0;
void dfs(int u) {
  for (int v : g[u])
    dfs(v), sz[u] += sz[v];
}

int main() {
  n = read();
  for (int i = 1; i <= n; i++)
    ed[i] = (rs(), ins());
  std::queue<int> q;
  for (int i = 0; i < 26; i++)
    if (ch[1][i])
      fail[ch[1][i]] = 1, q.push(ch[1][i]);
    else
      ch[1][i] = 1;
  while (!q.empty()) {
    int u = q.front();
    q.pop();
    for (int i = 0; i < 26; i++)
      if (ch[u][i])
        fail[ch[u][i]] = ch[fail[u]][i], q.push(ch[u][i]);
      else
        ch[u][i] = ch[fail[u]][i];
  }
  rs();
  int p = 1;
  for (int i = 0; s[i]; i++)
    p = ch[p][s[i] - 'a'], ++sz[p];
  for (int i = 2; i <= cnt; i++)
    g[fail[i]].pb(i);
  dfs(1);
  for (int i = 1; i <= n; i++)
    printf("%d\n", sz[ed[i]]);
  return 0;
}

manacher

$p_i$ 为回文长度。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
vector<int> manacher(const string &s) {
  vector<int> p(s.size() * 2 + 1);
  string t = "~";
  t += "-";
  for (int i = 0; i < (int)s.size(); i++) {
    t += s[i];
    t += "-";
  }
  int n = (int)t.size();
  int m = -1, r = -1;
  for (int i = 0; i < n; i++) {
    if (i <= r) {
      p[i] = min(p[m * 2 - i], r - i + 1);
    }
    while (i - p[i] >= 0 && i + p[i] < n && t[i + p[i]] == t[i - p[i]]) {
      ++p[i];
    }
    if (i + p[i] > r) {
      r = i + p[i] - 1;
      m = i;
    }
    --p[i];
  }
  string().swap(t);
  return p;
}

SA

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
#include <bits/stdc++.h>
using namespace std;
int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  string s;
  cin >> s;
  int n = (int)s.size();
  vector<int> cnt(128, 0);
  vector<int> a(n);
  vector<int> b(n);
  vector<int> sa(n, 0);
  for (int i = 0; i < n; i++) {
    cnt[a[i] = s[i]]++;
  }
  for (int i = 1; i < 128; i++) {
    cnt[i] += cnt[i - 1];
  }
  for (int i = n - 1; i >= 0; i--) {
    sa[--cnt[a[i]]] = i;
  }
  int m = 128;
  for (int k = 1; k <= n; k *= 2) {
    int t = 0;
    for (int i = n - k; i < n; i++) {
      b[t++] = i;
    }
    for (int i = 0; i < n; i++) {
      if (sa[i] >= k) {
        b[t++] = sa[i] - k;
      }
    }
    cnt.resize(m);
    for (int i = 0; i < m; i++) {
      cnt[i] = 0;
    }
    for (int i = 0; i < n; i++) {
      ++cnt[a[i]];
    }
    for (int i = 1; i < m; i++) {
      cnt[i] += cnt[i - 1];
    }
    for (int i = n - 1; i >= 0; i--) {
      sa[--cnt[a[b[i]]]] = b[i];
    }
    vector<int> new_a(n);
    new_a[sa[0]] = 0;
    int num = 0;
    for (int i = 1; i < n; i++) {
      new_a[sa[i]] =
          (a[sa[i]] == a[sa[i - 1]] && a[sa[i] + k] == a[sa[i - 1] + k])
              ? num
              : ++num;
    }
    a.swap(new_a);
    if (num + 1 == n) {
      break;
    } else {
      m = num + 1;
    }
  }
  for (int i = 0; i < n; i++) {
    cout << sa[i] + 1 << " \n"[i + 1 == n];
  }
  vector<int> rk = a;
  vector<int> ht(n, 0);
  int k = 0;
  for (int i = 0; i < n; i++) {
    if (!rk[i]) {
      continue;
    }
    if (k) {
      k -= 1;
    }
    int j = sa[rk[i] - 1];
    while (i + k < n && j + k < n && s[i + k] == s[j + k]) {
      k++;
    }
    ht[rk[i]] = k;
  }
  for (int i = 0; i < n; i++) {
    cout << ht[i] << " \n"[i + 1 == n];
  }
}

SCC

$O(\min(n+m, \frac{n^2}{w}))$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
template <class BS> struct kosaraju {
  int n, c;
  vector<BS> e1, e2;
  BS vis;
  kosaraju(vector<vector<int>> &e) {
    n = (int)e.size();
    e1.resize(n), e2.resize(n);
    rep(u, 0, n) for (auto v : e[u]) {
      e1[u].set(v);
      e2[v].set(u);
    }
    rep(u, 0, n) vis.set(u);
    scc.resize(n, -1);
    rep(i, 0, n) if (vis[i]) dfs1(i);
    c = 0;
    rep(u, 0, n) vis.set(u);
    for (auto i : r | views::reverse)
      if (scc[i] == -1)
        dfs2(i), c++;
  }
  vector<int> r;
  void dfs1(int u) {
    vis[u] = 0;
    auto cand = vis & e1[u];
    for (int v = cand._Find_first(); v < n; v = cand._Find_next(v)) {
      dfs1(v);
    }
    r.emplace_back(u);
  }
  vector<int> scc;
  void dfs2(int u) {
    vis[u] = 0;
    scc[u] = c;
    auto cand = vis & e2[u];
    for (int v = cand._Find_first(); v < n; v = cand._Find_next(v))
      if (scc[v] == -1)
        dfs2(v);
  }
  const int &operator[](const int &x) { return scc[x]; }
};

using BS = bitset<>;

二分图匹配

$O(\frac{N^3}{w})$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
template <typename BS> struct BipartiteMatching_Dense {
  int N1, N2;
  vector<BS> &adj;
  vector<int> match_1, match_2;
  vector<int> que;
  vector<int> prev;
  BS vis;
  BipartiteMatching_Dense(vector<BS> &adj, int N1, int N2)
      : N1(N1), N2(N2), adj(adj), match_1(N1, -1), match_2(N2, -1) {
    for (int s = 0; s < N1; s++)
      bfs(s);
  }
  void bfs(int s) {
    if (match_1[s] != -1)
      return;
    que.resize(N1), prev.resize(N1);
    int l = 0, r = 0;
    vis.set(), prev[s] = -1;
    que[r++] = s;
    while (l < r) {
      int u = que[l++];
      BS cand = vis & adj[u];
      for (int v = cand._Find_first(); v < N2; v = cand._Find_next(v)) {
        vis[v] = 0;
        if (match_2[v] != -1) {
          que[r++] = match_2[v];
          prev[match_2[v]] = u;
          continue;
        }
        int a = u, b = v;
        while (a != -1) {
          int t = match_1[a];
          match_1[a] = b, match_2[b] = a, a = prev[a], b = t;
        }
        return;
      }
    }
    return;
  }
  vector<pair<int, int>> matching() {
    vector<pair<int, int>> res;
    for (int v = 0; v < N1; v++)
      if (match_1[v] != -1)
        res.eb(v, match_1[v]);
    return res;
  }
  pair<vector<int>, vector<int>> vertex_cover() {
    vector<int> que(N1);
    int l = 0, r = 0;
    vis.set();
    vector<bool> done(N1);
    for (int i = 0; i < N1; i++) {
      if (match_1[i] == -1)
        done[i] = 1, que[r++] = i;
    }
    while (l < r) {
      int a = que[l++];
      BS cand = adj[a] & vis;
      for (int b = cand._Find_first(); b < N2; b = cand._Find_next(b)) {
        vis[b] = 0;
        int to = match_2[b];
        assert(to != -1);
        if (!done[to])
          done[to] = 1, que[r++] = to;
      }
    }
    vector<int> left, right;
    for (int i = 0; i < N1; i++)
      if (!done[i])
        left.eb(i);
    for (int i = 0; i < N2; i++)
      if (!vis[i])
        right.eb(i);
    return {left, right};
  }
};
using bs = bitset<>;

KM 二分图最大权匹配

From uoj rank1

想改成最小权的话 $A_{u,v} = \inf - a_{u,v}$ 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
#include <bits/stdc++.h>

using namespace std;

#define int long long
#define endl '\n'

#define PII pair<int, int>
#define fi first
#define se second

const int N = 407, INF = 1e9 + 7, NPOS = -1;
struct Matrix {
  int n;
  int a[N][N];
};
struct KuhnMunkres : Matrix {
  int hl[N], hr[N], slk[N];
  int fl[N], fr[N], vl[N], vr[N], pre[N], q[N], ql, qr;
  int check(int i) {
    if (vl[i] = 1, fl[i] != NPOS)
      return vr[q[qr++] = fl[i]] = 1;
    while (i != NPOS)
      swap(i, fr[fl[i] = pre[i]]);
    return 0;
  }
  void bfs(int s) {
    fill(slk, slk + n, INF), fill(vl, vl + n, 0), fill(vr, vr + n, 0);
    for (vr[q[ql = 0] = s] = qr = 1;;) {
      for (int d; ql < qr;)
        for (int i = 0, j = q[ql++]; i < n; ++i)
          if (!vl[i] && slk[i] >= (d = hl[i] + hr[j] - a[i][j]))
            if (pre[i] = j, d)
              slk[i] = d;
            else if (!check(i))
              return;
      int d = INF;
      for (int i = 0; i < n; ++i)
        if (!vl[i] && d > slk[i])
          d = slk[i];
      for (int i = 0; i < n; ++i) {
        if (vl[i])
          hl[i] += d;
        else
          slk[i] -= d;
        if (vr[i])
          hr[i] -= d;
      }
      for (int i = 0; i < n; ++i)
        if (!vl[i] && !slk[i] && !check(i))
          return;
    }
  }
  void ask() {
    fill(fl, fl + n, NPOS), fill(fr, fr + n, NPOS), fill(hr, hr + n, 0);
    for (int i = 0; i < n; ++i)
      hl[i] = *max_element(a[i], a[i] + n);
    for (int j = 0; j < n; ++j)
      bfs(j);
  }
} km;
struct Istream {
  char b[20 << 20], *i, *e;
  Istream(FILE *in) : i(b), e(b + fread(b, sizeof(*b), sizeof(b) - 1, in)) {}
  Istream &operator>>(int &val) {
    // return val=strtoll(i,&i,10),*this;
    while (*i < '0')
      ++i;
    for (val = 0; *i >= '0'; ++i)
      val = (val << 3) + (val << 1) + (*i - '0');
    return *this;
  }
} kin(stdin);
#define cin kin

void solve() {
  int nl, nr, m, u, v;
  for (cin >> nl >> nr >> m; m--; cin >> km.a[u][v])
    cin >> u >> v;
  km.n = max(nl, nr) + 1, km.ask();
  long long ans = 0;
  for (int i = 1; i <= nl; ++i)
    ans += km.a[i][km.fl[i]];
  cout << ans << '\n';
  for (int i = 1; i <= nl; ++i)
    cout << (km.a[i][km.fl[i]] ? km.fl[i] : 0) << ' ';
}

signed main() {
  // ios::sync_with_stdio(false); cin.tie(); cout.tie();
  solve();
}

dsu

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
struct unionfind {
  vector<int> p;
  unionfind(int N) { p = vector<int>(N, -1); }
  int root(int x) { return p[x] < 0 ? x : p[x] = root(p[x]); }
  bool same(int x, int y) { return root(x) == root(y); }
  void unite(int x, int y) {
    x = root(x);
    y = root(y);
    if (x != y) {
      if (p[x] < p[y]) {
        swap(x, y);
      }
      p[y] += p[x];
      p[x] = y;
    }
  }
  int size(int x) { return -p[root(x)]; }
};

ST 表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <bits/stdc++.h>
using namespace std;
int ST[18][100000];
int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int n, m;
  cin >> n >> m;
  vector<int> a(n);
  for (int i = 0; i < n; i++) {
    cin >> a[i];
    ST[0][i] = a[i];
  }
  for (int j = 1; j < 18; j++) {
    for (int i = 0; i + (1 << j - 1) < n; i++) {
      ST[j][i] = max(ST[j - 1][i], ST[j - 1][i + (1 << j - 1)]);
    }
  }
  for (int i = 0; i < m; i++) {
    int l, r;
    cin >> l >> r;
    --l;
    int L = __lg(r - l);
    cout << max(ST[L][l], ST[L][r - (1 << L)]) << "\n";
  }
  return 0;
}

最小斯坦纳树

在一个图里面选出一个包含 ${p}$ 的子图，使得边权最小。

子图是一棵树（易证）。$dp_{i,s}$ 表示经过 $i$ 且包含集合 $s$。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
#include <bits/stdc++.h>
using namespace std;
const int INF = 1000000000;
struct stain_tree {
  int n;
  vector<vector<pair<int, int>>> e;
  stain_tree(vector<vector<pair<int, int>>> &E) {
    e = E;
    n = (int)e.size();
  }
  int solve(const vector<int> &p) {
    int k = (int)p.size();
    if (!k) {
      return 0;
    }
    vector<vector<int>> dp(n, vector<int>(1 << k, INF));
    for (int i = 0; i < k; i++) {
      dp[p[i]][1 << i] = 0;
    }
    for (int s = 0; s < 1 << k; s++) {
      for (int i = 0; i < n; i++) {
        for (int t = s; t; --t &= s) {
          dp[i][s] = min(dp[i][s], dp[i][t] + dp[i][s ^ t]);
        }
      }
      vector<bool> vis(n);
      vector<int> dis(n);
      priority_queue<pair<int, int>, vector<pair<int, int>>,
                     greater<pair<int, int>>>
          q;
      for (int i = 0; i < n; i++) {
        dis[i] = dp[i][s];
        q.emplace(dp[i][s], i);
      }
      while (!q.empty()) {
        auto t = q.top();
        q.pop();
        int u = t.second;
        if (vis[u]) {
          continue;
        }
        vis[u] = 1;
        for (auto x : e[u]) {
          int v = x.first;
          int w = x.second;
          if (dis[v] > dis[u] + w) {
            dis[v] = dis[u] + w;
            q.emplace(dis[v], v);
          }
        }
      }
      for (int i = 0; i < n; i++) {
        dp[i][s] = dis[i];
      }
    }
    return dp[p[0]][(1 << k) - 1];
  }
};
int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  int n, m, k;
  cin >> n >> m >> k;
  vector<vector<pair<int, int>>> E(n);
  for (int i = 0; i < m; i++) {
    int u, v, w;
    cin >> u >> v >> w;
    --u;
    --v;
    E[u].emplace_back(v, w);
    E[v].emplace_back(u, w);
  }
  stain_tree st(E);
  vector<int> p(k);
  for (int i = 0; i < k; i++) {
    cin >> p[i];
    --p[i];
  }
  cout << st.solve(p) << "\n";
  return 0;
}

最小树形图

给定包含 $n$ 个节点，$m$ 条有向边的一个图，找到以 $r$ 为根节点的最小树形图，并输出每条边的权值之和。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9;
pair<int, vector<int>> solve(int n, int r, vector<array<int, 3>> e) {
  int ans = 0;
  vector<int> in(n, INF), pre(n);
  for (int i = 0; i < e.size(); i++) {
    auto [u, v, w] = e[i];
    if (u != v && w < in[v]) {
      in[v] = w;
      pre[v] = i;
    }
  }
  for (int i = 0; i < n; i++) {
    if (in[i] >= INF && i != r) {
      return {-1, vector<int>()};
    }
  }
  for (int i = 0; i < n; i++) {
    if (i != r) {
      ans += in[i];
    }
  }
  int c = 0;
  vector<int> id(n, -1), vis(n, -1);
  vis[r] = r;
  for (int i = 0; i < n; i++) {
    if (vis[i] == -1) {
      int cur = i;
      while (vis[cur] == -1) {
        vis[cur] = i;
        cur = e[pre[cur]][0];
      }
      if (vis[cur] == i) {
        int u = cur;
        while (id[u] == -1) {
          id[u] = c;
          u = e[pre[u]][0];
        }
        c += 1;
      }
    }
  }
  if (!c) {
    std::vector<int> res;
    for (int i = 0; i < n; i++) {
      if (i != r) {
        res.emplace_back(pre[i]);
      }
    }
    return {ans, res};
  } else {
    int cyc = c;
    for (int i = 0; i < n; i++) {
      if (id[i] == -1) {
        id[i] = c++;
      }
    }
    std::vector<array<int, 3>> newe;
    for (int i = 0; i < e.size(); i++) {
      auto [u, v, w] = e[i];
      newe.emplace_back(array<int, 3>{id[u], id[v], w - in[v]});
    }
    int newans = 0;
    std::vector<int> res;
    std::tie(newans, res) = solve(c, id[r], newe);
    if (newans == -1) {
      return {-1, std::vector<int>()};
    } else {
      ans += newans;
      for (int i = 0; i < c - 1; i++) {
        int v = e[res[i]][1];
        if (id[v] < cyc) {
          int u = e[pre[v]][0];
          while (u != v) {
            res.emplace_back(pre[u]);
            u = e[pre[u]][0];
          }
        }
      }
      return {ans, res};
    }
  }
}
int main() {
  int n, m, r;
  cin >> n >> m >> r;
  --r;
  vector<array<int, 3>> e(m);
  for (int i = 0; i < m; i++) {
    int u, v, w;
    cin >> u >> v >> w;
    --u;
    --v;
    e[i] = {u, v, w};
  }

  cout << solve(n, r, e).first << "\n";
}

rho

$O(n^{1/4})$。

T=350 n<=1e18, 280ms

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
struct m64 {
  using i64 = int64_t;
  using u64 = uint64_t;
  using u128 = __uint128_t;

  inline static u64 m, r, n2; // r * m = -1 (mod 1<<64), n2 = 1<<128 (mod m)
  static void set_mod(u64 m) {
    assert((m & 1) == 1);
    m64::m = m;
    n2 = -u128(m) % m;
    r = m;
    FOR(_, 5) r *= 2 - m * r;
    r = -r;
    assert(r * m == -1ull);
  }
  static u64 reduce(u128 b) { return (b + u128(u64(b) * r) * m) >> 64; }

  u64 x;
  m64() : x(0) {}
  m64(u64 x) : x(reduce(u128(x) * n2)){};
  u64 val() const {
    u64 y = reduce(x);
    return y >= m ? y - m : y;
  }
  m64 &operator+=(m64 y) {
    x += y.x - (m << 1);
    x = (i64(x) < 0 ? x + (m << 1) : x);
    return *this;
  }
  m64 &operator-=(m64 y) {
    x -= y.x;
    x = (i64(x) < 0 ? x + (m << 1) : x);
    return *this;
  }
  m64 &operator*=(m64 y) {
    x = reduce(u128(x) * y.x);
    return *this;
  }
  m64 operator+(m64 y) const { return m64(*this) += y; }
  m64 operator-(m64 y) const { return m64(*this) -= y; }
  m64 operator*(m64 y) const { return m64(*this) *= y; }
  bool operator==(m64 y) const {
    return (x >= m ? x - m : x) == (y.x >= m ? y.x - m : y.x);
  }
  bool operator!=(m64 y) const { return not operator==(y); }
  m64 pow(u64 n) const {
    m64 y = 1, z = *this;
    for (; n; n >>= 1, z *= z)
      if (n & 1)
        y *= z;
    return y;
  }
};

bool primetest(const uint64_t x) {
  using u64 = uint64_t;
  if (x == 2 or x == 3 or x == 5 or x == 7)
    return true;
  if (x % 2 == 0 or x % 3 == 0 or x % 5 == 0 or x % 7 == 0)
    return false;
  if (x < 121)
    return x > 1;
  const u64 d = (x - 1) >> __builtin_ctzll(x - 1);
  m64::set_mod(x);
  const m64 one(1), minus_one(x - 1);
  auto ok = [&](u64 a) {
    auto y = m64(a).pow(d);
    u64 t = d;
    while (y != one and y != minus_one and t != x - 1)
      y *= y, t <<= 1;
    if (y != minus_one and t % 2 == 0)
      return false;
    return true;
  };
  if (x < (1ull << 32)) {
    for (u64 a : {2, 7, 61})
      if (not ok(a))
        return false;
  } else {
    for (u64 a : {2, 325, 9375, 28178, 450775, 9780504, 1795265022}) {
      if (x <= a)
        return true;
      if (not ok(a))
        return false;
    }
  }
  return true;
}

mt19937_64 rng_mt{random_device{}()};
ll rnd(ll n) { return uniform_int_distribution<ll>(0, n - 1)(rng_mt); }

ll rho(ll n, ll c) {
  m64::set_mod(n);
  assert(n > 1);
  const m64 cc(c);
  auto f = [&](m64 x) { return x * x + cc; };
  m64 x = 1, y = 2, z = 1, q = 1;
  ll g = 1;
  const ll m = 1LL << (__lg(n) / 5); // ?
  for (ll r = 1; g == 1; r <<= 1) {
    x = y;
    FOR(_, r) y = f(y);
    for (ll k = 0; k < r and g == 1; k += m) {
      z = y;
      FOR(_, min(m, r - k)) y = f(y), q *= x - y;
      g = gcd(q.val(), n);
    }
  }
  if (g == n)
    do {
      z = f(z);
      g = gcd((x - z).val(), n);
    } while (g == 1);
  return g;
}

ll find_prime_factor(ll n) {
  assert(n > 1);
  if (primetest(n))
    return n;
  FOR(_, 100) {
    ll m = rho(n, rnd(n));
    if (primetest(m))
      return m;
    n = m;
  }
  cerr << "failed" << endl;
  assert(false);
  return -1;
}

vc<pair<ll, int>> factor(ll n) {
  assert(n >= 1);
  vc<pair<ll, int>> pf;
  FOR3(p, 2, 100) {
    if (p * p > n)
      break;
    if (n % p == 0) {
      ll e = 0;
      do {
        n /= p, e += 1;
      } while (n % p == 0);
      pf.eb(p, e);
    }
  }
  while (n > 1) {
    ll p = find_prime_factor(n);
    ll e = 0;
    do {
      n /= p, e += 1;
    } while (n % p == 0);
    pf.eb(p, e);
  }
  sort(all(pf));
  return pf;
}