算法竞赛模板

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

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

并查集#

1
struct DSU {
2
  int tot;
3
  vector<int> pa, size;
4
  DSU(int n) : pa(n+1), size(n+1, 1), tot(n) {
5
    iota(pa.begin(),pa.end(),0);
6
  }
7

8
  int find(int x){
9
    while (x!=pa[x]){
10
      x=pa[x]=pa[pa[x]];
11
    }
12
    return x;
13
  }
14
  int operator[](int x) {return find(x);}
15

16
  void unite(int x, int y) {
17
    x=find(x),y=find(y);
18
    if (x==y) return;
19
    tot--;
20
    if (size[x]<size[y]) swap(x,y);
21
    pa[y]=x;
22
    size[x]+=size[y];
23
  }
24
};

ST 表#

1
template<typename T=int, class Func = std::function<T(T, T)>>
2
struct ST {
3
  int n;
4
  vector<vector<T>> st;
5
  vector<int> lg;
6
  Func op;
7
  ST(vector<T>& a, Func _op=[](T x, T y){ return max(x,y); }): n(a.size()-1), lg(a.size()), op(_op){
8
    lg[0]=lg[1]=0;
9
    for (int i=2;i<=n;i++) lg[i]=lg[i>>1]+1;
10
    st.resize(lg[n]+1);
11
    for (int i=0;i<=lg[n];i++) st[i].resize(a.size());
12
    for (int i=1;i<=n;i++) st[0][i]=a[i];
13
    for (int i=1;i<=lg[n];i++){
14
      for (int j=1;j+(1<<i)-1<=n;j++){
15
        st[i][j]=op(st[i-1][j],st[i-1][j+(1<<(i-1))]);
16
      }
17
    }
18
  }
19

20
  T query(int l,int r){
21
    int p=lg[r-l+1];
22
    return op(st[p][l],st[p][r-(1<<p)+1]);
23
  }
24
  T operator()(int l,int r){
25
    return query(l,r);
26
  }
27
};

树状数组#

1
template<typename T=int>
2
struct fenwick {
3
  int n;
4
  vector<T> t;
5
  fenwick(int _n): n(_n), t(_n+1){}
6
  fenwick(vector<T>& a): n(a.size()-1), t(a.size()){
7
    for (int i=1;i<=n;i++){
8
      t[i]+=a[i];
9
      if (i+(i&(-i))<=n){
10
        t[i+(i&(-i))]+=t[i];
11
      }
12
    }
13
  }
14

15
  T query(int p){
16
    T res=T{};
17
    while(p){
18
      res+=t[p];
19
      p-=(p&(-p));
20
    }
21
    return res;
22
  }
23
  T operator[](int p){
24
    return query(p);
25
  }
26
  T operator()(int l,int r){
27
    if (l>r) swap(l,r);
28
    return query(r)-query(l-1);
29
  }
30

31
  void add(int p,T x){
32
    while(p<=n){
33
      t[p]+=x;
34
      p+=(p&(-p));
35
    }
36
  }
37
};

矩阵 + 快速幂#

1
template <typename T = long long, int p = 1000000007>
2
struct matrix {
3
  int n, m;
4
  std::vector<std::vector<T>> a;
5
  matrix(int _n = 0, int _m = 0, T x = T{}) : n(_n), m(_m), a(_n, std::vector<T>(_m, 0)) {
6
    for (int i = 0; i < std::min(n, m); ++i) a[i][i] = x;
7
  }
8
  std::vector<T>& operator[](int i) { return a[i]; }
9
  const std::vector<T>& operator[](int i) const { return a[i]; }
10

11
  matrix operator*(const matrix& b) const {
12
    matrix ret(n, b.m);
13
    for (int i = 0; i < n; ++i) {
14
      for (int k = 0; k < m; ++k) {
15
        if (!a[i][k]) continue;
16
        long long val = a[i][k];
17
        for (int j = 0; j < b.m; ++j) {
18
          ret[i][j] = (ret[i][j] + val * b.a[k][j]) % p;
19
        }
20
      }
21
    }
22
    return ret;
23
  }
24

25
  matrix pow(long long b) const {
26
    matrix base = *this;
27
    matrix ret(n, n, T{1});
28
    while (b) {
29
      if (b & 1LL) ret = ret * base;
30
      base = base * base;
31
      b >>= 1LL;
32
    }
33
    return ret;
34
  }
35
};

Modint#

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

5
  Mint(T _v = T{}) {
6
    v = _v % mod;
7
    if (v < 0) v += mod;
8
  }
9

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

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

17
  Mint pow(long long e) const {
18
    Mint res(1), base(v);
19
    while (e > 0) {
20
      if (e & 1) res = res * base;
21
      base = base * base;
22
      e >>= 1;
23
    }
24
    return res;
25
  }
26

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

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

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

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

39
  friend istream& operator>>(istream &is, Mint &m) {
40
    long long x; is >> x;
41
    m = Mint(x);
42
    return is;
43
  }
44

45
  friend ostream& operator<<(ostream &os, const Mint &m) {
46
    return os << m.v;
47
  }
48
};
49

50
using Z=Mint<long long,998244353>;

区间加线段树#

1
template <typename T=int>
2
struct segtree {
3
  vector<T> tree, lazy;
4
  int n;
5
  void push(int cl, int cr, int p) {
6
    int cm = cl + (cr - cl) / 2;
7
    if (cl != cr && lazy[p]) {
8
      lazy[p * 2] += lazy[p];
9
      lazy[p * 2 + 1] += lazy[p];
10
      tree[p * 2] += lazy[p] * (cm - cl + 1);
11
      tree[p * 2 + 1] += lazy[p] * (cr - cm);
12
      lazy[p] = 0;
13
    }
14
  }
15
  T query(int l, int r, int cl, int cr, int p) {
16
    if (l <= cl && cr <= r) return tree[p];
17
    int m = cl + (cr - cl) / 2;
18
    T sum = T{};
19
    push(cl, cr, p);
20
    if (l <= m) sum += query(l, r, cl, m, p * 2);
21
    if (r > m) sum += query(l, r, m + 1, cr, p * 2 + 1);
22
    return sum;
23
  }
24

25
  void add(int l, int r, T val, int cl, int cr, int p) {
26
    if (l <= cl && cr <= r) {
27
      lazy[p] += val;
28
      tree[p] += (cr - cl + 1) * val;
29
      return;
30
    }
31
    int m = cl + (cr - cl) / 2;
32
    push(cl, cr, p);
33
    if (l <= m) add(l, r, val, cl, m, p * 2);
34
    if (r > m) add(l, r, val, m + 1, cr, p * 2 + 1);
35
    tree[p] = tree[p * 2] + tree[p * 2 + 1];
36
  }
37

38
  void build(int s, int t, int p, vector<T> &arr) {
39
    if (s == t) {
40
      tree[p] = arr[s];
41
      return;
42
    }
43
    int m = s + (t - s) / 2;
44
    build(s, m, p * 2, arr);
45
    build(m + 1, t, p * 2 + 1, arr);
46
    tree[p] = tree[p * 2] + tree[p * 2 + 1];
47
  }
48

49
  void build(int s, int t, int p, T init) {
50
    if (s == t) {
51
      tree[p] = init;
52
      return;
53
    }
54
    int m = s + (t - s) / 2;
55
    build(s, m, p * 2, init);
56
    build(m + 1, t, p * 2 + 1, init);
57
    tree[p] = tree[p * 2] + tree[p * 2 + 1];
58
  }
59

60
  segtree(vector<T> &arr): n(arr.size()), tree(arr.size()<<2), lazy(arr.size()<<2) {
61
    build(0, n-1, 1, arr);
62
  }
63
  segtree(int _n,T init): n(_n), tree(_n<<2), lazy(_n<<2) {
64
    build(0, n-1, 1, init);
65
  }
66
  T query(int l, int r) { return query(l, r, 0, n-1, 1); }
67
  T operator()(int l,int r){ return query(l,r);}
68
  void add(int l, int r, T val) { add(l, r, val, 0, n-1, 1); }
69
};

区间推平线段树#

1
template <typename T=int>
2
struct segtree {
3
  vector<T> tree, lazy;
4
  vector<bool> if_lazy;
5
  int n;
6
  void push(int cl, int cr, int p) {
7
    int cm = cl + (cr - cl) / 2;
8
    if (cl != cr && if_lazy[p]) {
9
      lazy[p * 2] = lazy[p],if_lazy[p*2] = 1;
10
      lazy[p * 2 + 1] = lazy[p],if_lazy[p*2+1] = 1;
11
      tree[p * 2] = lazy[p] * (cm - cl + 1);
12
      tree[p * 2 + 1] = lazy[p] * (cr - cm);
13
      lazy[p] = 0;
14
      if_lazy[p] = 0;
15
    }
16
  }
17

18
  T query(int l, int r, int cl, int cr, int p) {
19
    if (l <= cl && cr <= r) return tree[p];
20
    int m = cl + (cr - cl) / 2;
21
    T sum = T{};
22
    push(cl, cr, p);
23
    if (l <= m) sum += query(l, r, cl, m, p * 2);
24
    if (r > m) sum += query(l, r, m + 1, cr, p * 2 + 1);
25
    return sum;
26
  }
27

28
  void modify(int l, int r, T val, int cl, int cr, int p) {
29
    if (l <= cl && cr <= r) {
30
      lazy[p] = val;
31
      if_lazy[p] = 1;
32
      tree[p] = (cr - cl + 1) * val;
33
      return;
34
    }
35
    int m = cl + (cr - cl) / 2;
36
    push(cl, cr, p);
37
    if (l <= m) modify(l, r, val, cl, m, p * 2);
38
    if (r > m) modify(l, r, val, m + 1, cr, p * 2 + 1);
39
    tree[p] = tree[p * 2] + tree[p * 2 + 1];
40
  }
41

42
  void build(int s, int t, int p, vector<T> &arr) {
43
    if (s == t) {
44
      tree[p] = arr[s];
45
      return;
46
    }
47
    int m = s + (t - s) / 2;
48
    build(s, m, p * 2, arr);
49
    build(m + 1, t, p * 2 + 1, arr);
50
    tree[p] = tree[p * 2] + tree[p * 2 + 1];
51
  }
52

53
  void build(int s, int t, int p, T init) {
54
    if (s == t) {
55
      tree[p] = init;
56
      return;
57
    }
58
    int m = s + (t - s) / 2;
59
    build(s, m, p * 2, init);
60
    build(m + 1, t, p * 2 + 1, init);
61
    tree[p] = tree[p * 2] + tree[p * 2 + 1];
62
  }
63

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

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

区间加 + 推平线段树#

1
template <typename T=int>
2
struct segtree {
3
  vector<T> tree, lazy, setv;
4
  vector<char> has;
5
  int n;
6
  void push(int cl, int cr, int p) {
7
    if (cl == cr) {
8
      if (has[p]) { has[p] = 0; lazy[p] = T{}; }
9
      return;
10
    }
11
    if (has[p]) {
12
      has[p * 2] = 1; has[p * 2 + 1] = 1;
13
      setv[p * 2] = setv[p]; setv[p * 2 + 1] = setv[p];
14
      lazy[p * 2] = T{}; lazy[p * 2 + 1] = T{};
15
      tree[p * 2] = setv[p];
16
      tree[p * 2 + 1] = setv[p];
17
      has[p] = 0;
18
    }
19
    if (lazy[p] != T{}) {
20
      if (has[p * 2]) setv[p * 2] += lazy[p]; else lazy[p * 2] += lazy[p];
21
      if (has[p * 2 + 1]) setv[p * 2 + 1] += lazy[p]; else lazy[p * 2 + 1] += lazy[p];
22
      tree[p * 2] += lazy[p];
23
      tree[p * 2 + 1] += lazy[p];
24
      lazy[p] = T{};
25
    }
26
  }
27
  T query(int l, int r, int cl, int cr, int p) {
28
    if (l <= cl && cr <= r) return tree[p];
29
    int m = cl + (cr - cl) / 2;
30
    T sum = T{};
31
    push(cl, cr, p);
32
    if (l <= m) sum = max(sum, query(l, r, cl, m, p * 2));
33
    if (r > m) sum = max(sum, query(l, r, m + 1, cr, p * 2 + 1));
34
    return sum;
35
  }
36

37
  void add(int l, int r, T val, int cl, int cr, int p) {
38
    if (l <= cl && cr <= r) {
39
      if (has[p]) setv[p] += val; else lazy[p] += val;
40
      tree[p] += val;
41
      return;
42
    }
43
    int m = cl + (cr - cl) / 2;
44
    push(cl, cr, p);
45
    if (l <= m) add(l, r, val, cl, m, p * 2);
46
    if (r > m) add(l, r, val, m + 1, cr, p * 2 + 1);
47
    tree[p] = max(tree[p * 2], tree[p * 2 + 1]);
48
  }
49

50
  void assign(int l, int r, T val, int cl, int cr, int p) {
51
    if (l <= cl && cr <= r) {
52
      has[p] = 1;
53
      setv[p] = val;
54
      lazy[p] = T{};
55
      tree[p] = val;
56
      return;
57
    }
58
    int m = cl + (cr - cl) / 2;
59
    push(cl, cr, p);
60
    if (l <= m) assign(l, r, val, cl, m, p * 2);
61
    if (r > m) assign(l, r, val, m + 1, cr, p * 2 + 1);
62
    tree[p] = max(tree[p * 2], tree[p * 2 + 1]);
63
  }
64

65
  segtree(int _n): n(_n), tree(_n<<2), lazy(_n<<2), setv(_n<<2), has((_n<<2)) {
66
  }
67
  T query(int l, int r) { return query(l, r, 0, n-1, 1); }
68
  void add(int l, int r, T val) { add(l, r, val, 0, n-1, 1); }
69
  void assign(int l, int r, T val) { assign(l, r, val, 0, n-1, 1); }
70
};

单点修改线段树#

1
template <typename T=int>
2
struct segtree {
3
  vector<T> tree;
4
  int n;
5
  T query(int l, int r, int cl, int cr, int p) {
6
    if (l <= cl && cr <= r) return tree[p];
7
    int m = cl + (cr - cl) / 2;
8
    T sum = T{};
9
    if (l <= m) sum += query(l, r, cl, m, p * 2);
10
    if (r > m) sum += query(l, r, m + 1, cr, p * 2 + 1);
11
    return sum;
12
  }
13

14
  void add(int idx, T val, int cl, int cr, int p) {
15
    if (cl == cr && cr == idx) {
16
      tree[p] += val;
17
      return;
18
    }
19
    int m = cl + (cr - cl) / 2;
20
    if (idx <= m) add(idx, val, cl, m, p * 2);
21
    if (idx > m) add(idx, val, m + 1, cr, p * 2 + 1);
22
    tree[p] = tree[p * 2] + tree[p * 2 + 1];
23
  }
24

25
  void modify(int idx, T val, int cl, int cr, int p) {
26
    if (cl == cr && cr == idx) {
27
      tree[p] = val;
28
      return;
29
    }
30
    int m = cl + (cr - cl) / 2;
31
    if (idx <= m) modify(idx, val, cl, m, p * 2);
32
    if (idx > m) modify(idx, val, m + 1, cr, p * 2 + 1);
33
    tree[p] = tree[p * 2] + tree[p * 2 + 1];
34
  }
35

36
  void build(int s, int t, int p, vector<T> &arr) {
37
    if (s == t) {
38
      tree[p] = arr[s];
39
      return;
40
    }
41
    int m = s + (t - s) / 2;
42
    build(s, m, p * 2, arr);
43
    build(m + 1, t, p * 2 + 1, arr);
44
    tree[p] = tree[p * 2] + tree[p * 2 + 1];
45
  }
46

47
  void build(int s, int t, int p, T init) {
48
    if (s == t) {
49
      tree[p] = init;
50
      return;
51
    }
52
    int m = s + (t - s) / 2;
53
    build(s, m, p * 2, init);
54
    build(m + 1, t, p * 2 + 1, init);
55
    tree[p] = tree[p * 2] + tree[p * 2 + 1];
56
  }
57

58
  segtree(vector<T> &arr): n(arr.size()), tree(arr.size()<<2) {
59
    build(0, n-1, 1, arr);
60
  }
61
  segtree(int _n,T init): n(_n), tree(_n<<2) {
62
    build(0, n-1, 1, init);
63
  }
64
  T query(int l, int r) { return query(l, r, 0, n-1, 1); }
65
  T operator()(int l,int r){ return query(l,r);}
66
  void add(int idx, T val) { add(idx, val, 0, n-1, 1); }
67
  void modify(int idx, T val) { modify(idx, val, 0, n-1, 1); }
68
};

Lucas 定理#

1
template<typename T=long long>
2
struct lucas
3
{
4
  vector<T>fa,inv;
5
  T p;
6
  lucas(T _p): p(_p), fa(_p), inv(_p){
7
    fa[0]=inv[0]=1;
8
    for (T i=1;i<p;i++){
9
      fa[i]=fa[i-1]*i%p;
10
      inv[i]=qpow(fa[i],p-2);
11
    }
12
  }
13
  T qpow(T a,T b){
14
    T res=1;
15
    while(b){
16
        if (b&1) res=res*a%p;
17
        a=a*a%p;
18
        b>>=1;
19
    }
20
    return res;
21
  }
22
  T c(T a,T b){
23
    if (b>a) return 0;
24
    return fa[a]*inv[a-b]%p*inv[b]%p;
25
  }
26
  T get(T a,T b){
27
    if (not b) return 1;
28
    return get(a/p,b/p)*c(a%p,b%p)%p;
29
  }
30
  T operator()(T a,T b){ return get(a,b); }
31
};

Manacher#

1
struct Manacher {
2
  vector<int>p;
3
  int n;
4
  Manacher(string &_s): n(_s.size()*2+2), p(_s.size()*2+2,1) {
5
    string s="$|";
6
    s.reserve(n);
7
    for (auto&&c:_s){
8
      s+=c;
9
      s+='|';
10
    }
11
    for (int t=1,r=0,mid=0;t<n;t++){
12
      if (t<=r) p[t]=min(p[mid*2-t],r-t+1);
13
      while (p[t]<=t and t+p[t]<n and s[t-p[t]]==s[t+p[t]]) p[t]++;
14
      if (p[t]+t>r) r=p[t]+t-1,mid=t;
15
    }
16
  }
17
  bool query(int l,int r){
18
    // 1-indexed
19
    l=l*2,r=r*2;
20
    int mid=(l+r)/2;
21
    return p[mid]>=(r-mid+1);
22
  }
23
  bool operator()(int l,int r){ return query(l,r); }
24
  int operator[](int i){ return p[i]; }
25
};

预处理的 KMP#

1
struct KMP {
2
  vector<vector<int>>nxt;
3
  int n,st,ed;
4
  KMP(string &p,int _st='a',int _ed='z'): n(p.size()), st(_st), ed(_ed), nxt(_ed-_st+1,vector(p.size(),0)) {
5
    int pre=0;
6
    nxt[p[0]-st][0]=1;
7
    for (int i=1;i<n;i++){
8
      for (int j=st;j<=ed;j++){
9
        if (j==p[i])
10
          nxt[j-st][i]=i+1;
11
        else
12
          nxt[j-st][i]=nxt[j-st][pre];
13
      }
14
      pre=nxt[p[i]-st][pre];
15
    }
16
  }
17
  int find_first(string &s){
18
    int cur=0;
19
    for (int i=0;i<s.length();i++){
20
      cur=nxt[s[i]-st][cur];
21
      if (cur==n)
22
        return i-n+1;
23
    }
24
    return -1;
25
  }
26
  int find_largest(string &s){
27
    int cur=0,ret=0;
28
    for (int i=0;i<s.length();i++){
29
      cur=nxt[s[i]-st][cur];
30
      if (cur==n)
31
        return n;
32
      if (cur>ret)
33
        ret=cur;
34
    }
35
    return ret;
36
  }
37
};

Z 函数 / 扩展 KMP#

1
struct exKMP {
2
  vector<int>z;
3
  int n;
4
  exKMP(string &p): n(p.size()), z(p.size()) {
5
    int l=0;
6
    for (int i=1;i<n;i++){
7
      if (l+z[l]>i) z[i]=min(z[i-l],l+z[l]-i);
8
      while (i+z[i]<n and p[z[i]]==p[i+z[i]]) z[i]++;
9
      if (i+z[i]>l+z[l]) l=i;
10
    }
11
  }
12
  int query(int i){ return (i==0?n:z[i]); }
13
  int operator[](int i){ return query(i); }
14
};

MillerRabin 快速质数判定#

1
template<typename T=__int128>
2
struct MillerRabin{
3
  vector<T> p{2,3,5,7,11,13,17,19,23,29,31,37};
4
  MillerRabin (){}
5
  T qpow(T a,T b,T p){
6
    T res=1;
7
    while(b){
8
        if (b&1) res=res*a%p;
9
        a=a*a%p;
10
        b>>=1;
11
    }
12
    return res;
13
  }
14
  bool check(T x){
15
    if (x<=37){
16
      for (auto&&i:p) if (i==x) return 1;
17
      return 0;
18
    }
19
    T u=x-1,t=0;
20
    while (not (u&1))
21
      (u>>=1),t++;
22
    for (auto&&i:p){
23
      T v=qpow(i,u,x);
24
      if (v==1) continue;
25
      T s=0;
26
      for (;s<t;s++){
27
        if (v==x-1) break;
28
        v=(v*v)%x;
29
      }
30
      if (s==t) return 0;
31
    }
32
    return 1;
33
  }
34
  bool operator()(T x){ return check(x); }
35
};

NTT 快速数论变换#

1
template<int mod, int root, typename T = long long>
2
class NTTProc {
3
private:
4
  T qpow(T base, T exp) const {
5
    T res = 1;
6
    base %= mod;
7
    while (exp > 0) {
8
      if (exp % 2 == 1) res = (res * base) % mod;
9
      base = (base * base) % mod;
10
      exp /= 2;
11
    }
12
    return res;
13
  }
14
  T qinv(T x) const {
15
    return qpow(x, mod - 2);
16
  }
17
  inline static const T inv_root = NTTProc<mod, root, T>().qinv((T)root);
18
  void trans(vector<T>& a, bool invert) {
19
    int n = a.size();
20
    for (int i = 1, j = 0; i < n; i++) {
21
      int bit = n >> 1;
22
      for (; j & bit; bit >>= 1) {
23
        j ^= bit;
24
      }
25
      j ^= bit;
26
      if (i < j) {
27
        swap(a[i], a[j]);
28
      }
29
    }
30
    for (int len = 2; len <= n; len <<= 1) {
31
      T wlen = qpow(invert ? inv_root : root, (mod - 1) / len);
32
      for (int i = 0; i < n; i += len) {
33
        T w = 1;
34
        for (int j = 0; j < len / 2; j++) {
35
          T u = a[i + j];
36
          T v = (a[i + j + len / 2] * w) % mod;
37
          a[i + j] = (u + v) % mod;
38
          a[i + j + len / 2] = (u - v + mod) % mod;
39
          w = (w * wlen) % mod;
40
        }
41
      }
42
    }
43
    if (invert) {
44
      T n_inv = qinv(n);
45
      for (T& x : a) {
46
        x = (x * n_inv) % mod;
47
      }
48
    }
49
  }
50
public:
51
  NTTProc() = default;
52
  vector<T> mul(vector<T>& a, vector<T>& b) {
53
    if (a.empty() || b.empty()) return {};
54
    int n = a.size() + b.size() - 1;
55
    int mx = 1;
56
    while (mx < n) {
57
      mx <<= 1;
58
    }
59
    a.resize(mx);
60
    b.resize(mx);
61
    trans(a, false);
62
    trans(b, false);
63
    vector<T> c(mx);
64
    for (int i = 0; i < mx; i++) {
65
      c[i] = (a[i] * b[i]) % mod;
66
    }
67
    trans(c, true);
68
    c.resize(n);
69
    return c;
70
  }
71
  vector<T> operator()(vector<T>& a,vector<T>& b) {
72
    return mul(a, b);
73
  }
74
};
75

76
NTTProc<998244353,3> ntt;

FFT 快速傅里叶变换#

1
template<typename T = double>
2
class complex {
3
public:
4
  using value_type = T;
5
  T re, im;
6

7
  constexpr complex(T real = T(), T imag = T()) : re(real), im(imag) {}
8

9
  constexpr complex operator+(const complex& o) const { return complex(re + o.re, im + o.im); }
10
  constexpr complex operator-(const complex& o) const { return complex(re - o.re, im - o.im); }
11
  constexpr complex operator*(const complex& o) const { return complex(re * o.re - im * o.im, re * o.im + im * o.re); }
12
  constexpr complex& operator+=(const complex& o) { re += o.re; im += o.im; return *this; }
13
  constexpr complex& operator-=(const complex& o) { re -= o.re; im -= o.im; return *this; }
14
  constexpr complex& operator*=(const complex& o) { T nr = re * o.re - im * o.im; im = re * o.im + im * o.re; re = nr; return *this; }
15

16
  constexpr complex operator*(T s) const { return complex(re * s, im * s); }
17
  constexpr complex& operator*=(T s) { re *= s; im *= s; return *this; }
18
  friend constexpr complex operator*(T s, const complex& z) { return z * s; }
19

20
  static complex unit(T theta) { return complex(std::cos(theta), std::sin(theta)); }
21
};
22

23
template <typename C = ::complex<>, typename T = long long>
24
class FFTProc {
25
private:
26
  void trans(vector<C>& a, bool invert) const {
27
    int n = static_cast<int>(a.size());
28
    for (int i = 1, j = 0; i < n; ++i) {
29
      int bit = n >> 1;
30
      for (; j & bit; bit >>= 1) j ^= bit;
31
      j ^= bit;
32
      if (i < j) swap(a[i], a[j]);
33
    }
34
    const double PI = std::acos(-1.0);
35
    for (int len = 2; len <= n; len <<= 1) {
36
      double ang = 2 * PI / len * (invert ? -1.0 : 1.0);
37
      C wlen = C::unit(static_cast<typename C::value_type>(ang));
38
      for (int i = 0; i < n; i += len) {
39
        C w(static_cast<typename C::value_type>(1), static_cast<typename C::value_type>(0));
40
        for (int j = 0; j < (len >> 1); ++j) {
41
          C u = a[i + j];
42
          C v = a[i + j + (len >> 1)] * w;
43
          a[i + j] = u + v;
44
          a[i + j + (len >> 1)] = u - v;
45
          w *= wlen;
46
        }
47
      }
48
    }
49
    if (invert) {
50
      auto inv_n = static_cast<typename C::value_type>(1.0 / n);
51
      for (auto& x : a) x *= inv_n;
52
    }
53
  }
54
public:
55
  FFTProc() = default;
56

57
  vector<T> mul(const vector<T>& a, const vector<T>& b) const {
58
    if (a.empty() || b.empty()) return {};
59
    int n = static_cast<int>(a.size() + b.size() - 1);
60
    int mx = 1;
61
    while (mx < n) mx <<= 1;
62

63
    vector<C> fa(mx), fb(mx);
64
    for (size_t i = 0; i < a.size(); ++i) fa[i] = C(static_cast<typename C::value_type>(a[i]), static_cast<typename C::value_type>(0));
65
    for (size_t i = 0; i < b.size(); ++i) fb[i] = C(static_cast<typename C::value_type>(b[i]), static_cast<typename C::value_type>(0));
66

67
    trans(fa, false);
68
    trans(fb, false);
69
    for (int i = 0; i < mx; ++i) fa[i] *= fb[i];
70
    trans(fa, true);
71

72
    vector<T> c(n);
73
    for (int i = 0; i < n; ++i) {
74
      double val = static_cast<double>(fa[i].re);
75
      c[i] = static_cast<T>(std::llround(val));
76
    }
77
    return c;
78
  }
79

80
  vector<T> operator()(const vector<T>& a, const vector<T>& b) const { return mul(a, b); }
81
};
82

83
FFTProc<> fft;

线性基#

1
using u64=uint64_t;
2
template<int MX=31>
3
struct LinearBasis {
4
  array<u64,MX> b{},msk{};
5
  vector<int> idx;
6
  void insert(u64 x,int p) {
7
    u64 cur=0,nxt=1ull<<idx.size();
8
    for (int i=MX-1;i>=0;--i) {
9
      if (((x>>i)&1)==0) continue;
10
      if (not b[i]){
11
        b[i]=x;
12
        msk[i]=cur|nxt;
13
        idx.push_back(p);
14
        return;
15
      }
16
      x^=b[i];
17
      cur^=msk[i];
18
    }
19
  }
20
  array<u64,2> max(){
21
    u64 ans=0,res=0;
22
    for (int i=MX-1;i>=0;--i) {
23
      if (not b[i]) continue;
24
      u64 nxt=ans^b[i];
25
      if (nxt>ans){
26
        ans=nxt;
27
        res^=msk[i];
28
      }
29
    }
30
    return {ans,res};
31
  }
32
  array<u64,2> find(int tar){
33
    u64 x=tar,res=0;
34
    for (int i=MX-1;i>=0;--i) {
35
      if (((x>>i)&1)==0) continue;
36
      if (not b[i]){
37
        return {0ull,0ull};
38
      }
39
      x^=b[i];
40
      res^=msk[i];
41
    }
42
    return {1ull,res};
43
  }
44
};

拉格朗日插值定理 / 重心拉格朗日#

1
template <class T>
2
struct Lag {
3
  static vector<T> coef(const vector<array<T,2>>& p) {
4
    int n = (int)p.size();
5
    if (n == 0) return {};
6
    if (n == 1) return {p[0][1]};
7
    vector<T> x(n), y(n);
8
    for (int i = 0; i < n; ++i) { x[i] = p[i][0]; y[i] = p[i][1]; }
9
    vector N(1, T(1));
10
    for (int i = 0; i < n; ++i) N = mul(N, x[i]);
11
    vector a(n, T(0));
12
    for (int i = 0; i < n; ++i) {
13
      T d = T(1);
14
      for (int j = 0; j < n; ++j) if (j != i) d *= (x[i] - x[j]);
15
      vector q = div(N, x[i]);
16
      T s = y[i] / d;
17
      for (int k = 0; k < n; ++k) a[k] += q[k] * s;
18
    }
19
    return a;
20
  }
21
  static T eval_eq(const vector<array<T,2>>& p, const T& x) {
22
    int n = (int)p.size();
23
    if (n == 0) return T(0);
24
    if (n == 1) return p[0][1];
25

26
    T s = p[0][0];
27
    T h = p[1][0] - p[0][0];
28
    for (int i = 0; i < n; ++i) {
29
      if (x == s + T(i) * h) return p[i][1];
30
    }
31
    T t = (x - s) / h;
32
    T w0 = ((n - 1) & 1) ? T(0) - T(1) : T(1);
33
    for (int r = 1; r <= n - 1; ++r) w0 /= T(r);
34
    T num = T(0), den = T(0), wi = w0;
35
    for (int i = 0; i < n; ++i) {
36
      T ti = wi / (t - T(i));
37
      num += ti * p[i][1];
38
      den += ti;
39
      if (i + 1 < n) wi = (T(0) - wi) * T(n - 1 - i) / T(i + 1);
40
    }
41
    return num / den;
42
  }
43
  static vector<T> operator()(const vector<array<T,2>>& p) {
44
    return coef(p);
45
  }
46
  // x 等差时
47
  static vector<T> operator()(const vector<array<T,2>>& p, const T& x) {
48
    return eval_eq(p,x);
49
  }
50
private:
51
  static vector<T> mul(const vector<T>& a, const T& r) {
52
    vector b(a.size() + 1, T(0));
53
    for (int i = (int)a.size() - 1; i >= 0; --i) b[i + 1] += a[i];
54
    T nr = T(0) - r;
55
    for (int i = 0; i < (int)a.size(); ++i) b[i] += a[i] * nr;
56
    return b;
57
  }
58
  static vector<T> div(const vector<T>& a, const T& r) {
59
    int n = (int)a.size() - 1;
60
    if (n < 0) return {};
61
    vector q(n, T(0));
62
    T cur = a[n];
63
    for (int k = n - 1; k >= 1; --k) {
64
      q[k] = cur;
65
      cur = a[k] + cur * r;
66
    }
67
    if (n >= 1) q[0] = cur;
68
    return q;
69
  }
70
};
71

72
using Z=Mint<long long,998244353>;
73
Lag<Z> lag={};
74
// Lag<double> lag={};

平衡树#

1
#include<bits/extc++.h>
2
template<typename T=int>
3
using rbtree=__gnu_pbds::tree<T,__gnu_pbds::null_type,less<T>,__gnu_pbds::rb_tree_tag,__gnu_pbds::tree_order_statistics_node_update>;
4
/* order_of_key()
5
 * find_by_order() iterator
6
 */

exgcd#

1
def exgcd(a,b):
2
  ps,s,pt,t,pr,r=1,0,0,1,a,b
3
  while r:
4
    q=pr//r
5
    pr,r=r,pr-q*r
6
    pt,t=t,pt-q*t
7
    ps,s=s,ps-q*s
8
  return pr,ps,pt