[数据删除] 2021 算法模板复习！

博主： Siyuan
发布时间：2019 年 09 月 22 日
15908 次浏览
44 条评论
5324字数
分类：算法

别催了我真的咕了……

祝大家 [数据删除] 2021 加油鸭！

Link Cut Tree

洛谷 P3690

#include <bits/stdc++.h>

const int N = 1e5 + 5;
int n, m, a[N];
struct Node;
Node *null;
struct Node {
    Node *ch[2], *fa;
    bool rev;
    int val, sum;
    inline Node(int w = 0) {
        ch[0] = ch[1] = fa = null;
        rev = false;
        val = sum = w;
    }
    inline int id() const {
        return fa->ch[1] == this;
    }
    inline bool isRoot() const {
        return fa->ch[0] != this && fa->ch[1] != this;
    }
    inline void pushUp() {
        sum = ch[0]->sum ^ ch[1]->sum ^ val;
    }
    inline void reverse() {
        rev ^= 1;
        std::swap(ch[0], ch[1]);
    }
    inline void pushDown() {
        if (rev) {
            if (ch[0] != null) {
                ch[0]->reverse();
            }
            if (ch[1] != null) {
                ch[1]->reverse();
            }
            rev = false;
        }
    }
} pool[N];
std::queue<int> q;
inline Node *newNode(int w) {
    static int idx = 0;
    int cur;
    if (q.empty()) {
        cur = idx++;
    } else {
        cur = q.front();
        q.pop();
    }
    pool[cur] = Node(w);
    return pool + cur;
}
inline void delNode(Node *x) {
    q.push(x - pool);
}
struct LCT {
    Node *a[N];
    LCT(int *val) {
        null = newNode(0);
        null->ch[0] = null->ch[1] = null->fa = null;
        for (int i = 1; i <= n; i++) {
            a[i] = newNode(val[i]);
        }
    }
    void pushTag(Node *x) {
        if (!x->isRoot()) {
            pushTag(x->fa);
        }
        x->pushDown();
    }
    inline void rotate(Node *x) {
        Node *y = x->fa, *z = y->fa;
        int k = x->id();
        if (!y->isRoot()) {
            z->ch[y->id()] = x;
        }
        x->fa = z;
        y->ch[k] = x->ch[k ^ 1];
        x->ch[k ^ 1]->fa = y;
        x->ch[k ^ 1] = y;
        y->fa = x;
        y->pushUp();
    }
    inline void splay(Node *x) {
        pushTag(x);
        for (; !x->isRoot(); ) {
            Node *y = x->fa;
            if (!y->isRoot()) {
                rotate(x->id() == y->id() ? y : x);
            }
            rotate(x);
        }
        x->pushUp();
    }
    inline void access(Node *x) {
        for (Node *y = null; x != null; y = x, x = x->fa) {
            splay(x);
            x->ch[1] = y;
            x->pushUp();
        }
    }
    inline void makeRoot(Node *x) {
        access(x);
        splay(x);
        x->reverse();
    }
    inline void split(Node *x, Node *y) {
        makeRoot(x);
        access(y);
        splay(y);
    }
    inline Node *findRoot(Node *x) {
        access(x);
        splay(x);
        x->pushDown();
        for (; x->ch[0] != null; x = x->ch[0], x->pushDown());
        splay(x);
        return x;
    }
    inline bool link(Node *x, Node *y) {
        makeRoot(x);
        if (findRoot(y) != x) {
            x->fa = y;
            return true;
        } else {
            return false;
        }
    }
    inline bool cut(Node *x, Node *y) {
        split(x, y);
        if (y->ch[0] == x && x->ch[1] == null) {
            y->ch[0] = x->fa = null;
            y->pushUp();
            return true;
        } else {
            return false;
        }
    }
    inline void splay(int x) { splay(a[x]); }
    inline void access(int x) { access(a[x]); }
    inline void makeRoot(int x) { makeRoot(a[x]); }
    inline void split(int x, int y) { split(a[x], a[y]); }
    inline Node *findRoot(int x) { return findRoot(a[x]); }
    inline bool link(int x, int y) { return link(a[x], a[y]); }
    inline bool cut(int x, int y) { return cut(a[x], a[y]); }
};

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
    }
    LCT T(a);
    for (int i = 1; i <= m; i++) {
        int opt, x, y;
        scanf("%d%d%d", &opt, &x, &y);
        if (opt == 0) {
            T.split(x, y);
            printf("%d\n", T.a[y]->sum);
        } else if (opt == 1) {
            T.link(x, y);
        } else if (opt == 2) {
            T.cut(x, y);
        } else {
            T.splay(x);
            T.a[x]->val = y;
            T.a[x]->pushUp();
        }
    }
    return 0;
}

Min_25 筛

洛谷 P5325

#include <bits/stdc++.h>
typedef long long int64;

const int N = 1e5 + 5, M = 2e5 + 5, MOD = 1e9 + 7, I6 = (MOD + 1) / 6;
int64 n, lis[M];
int G[2][M], Fprime[M], fp[N];
int m, tot, prime[N], id[2][N];

inline int norm(int x) {
    return x < MOD ? x : x - MOD;
}
inline void add(int &x, const int y) {
    (x += y) >= MOD && (x -= MOD);
}
void sieve(int n) {
    std::bitset<N> flg;
    for (int i = 2; i <= n; i++) {
        if (!flg[i]) {
            prime[++tot] = i;
            add(fp[tot] = fp[tot - 1], (int64)i * (i - 1) % MOD);
        }
        for (int j = 1; j <= tot && i * prime[j] <= n; j++) {
            flg[i * prime[j]] = 1;
            if (i % prime[j] == 0) {
                break;
            }
        }
    }
}
inline int &idx(int64 x) {
    return x <= m ? id[0][x] : id[1][n / x];
}
inline int F(int64 n, int k) {
    if (prime[k] > n || n <= 1) {
        return 0;
    }
    int ans = norm(Fprime[idx(n)] - fp[k - 1] + MOD);
    for (int i = k; i <= tot && (int64)prime[i] * prime[i] <= n; i++) {
        int64 num = prime[i];
        int f1 = prime[i], f2 = (int64)prime[i] * prime[i] % MOD;
        for (int c = 1; num * prime[i] <= n; num *= prime[i], c++) {
            add(ans, (int64)f1 * (f1 - 1) % MOD * F(n / num, i + 1) % MOD);
            add(ans, (int64)f2 * (f2 - 1) % MOD);
            f1 = f2;
            f2 = (int64)f2 * prime[i] % MOD;
        }
    }
    return ans;
}
int main() {
    scanf("%lld", &n);
    m = sqrt(n);
    sieve(m);
    int cnt = 0;
    for (int64 i = 1, v; i <= n; i = n / v + 1) {
        v = n / i;
        idx(v) = ++cnt;
        lis[cnt] = v;
        int w = v % MOD;
        G[0][cnt] = (int64)(w + 2) * (w - 1) / 2 % MOD;
        G[1][cnt] = (int64)w * (w + 1) % MOD * (2 * w + 1) % MOD * I6 % MOD - 1;
    }
    int g0 = 0, g1 = 0;
    for (int i = 1; i <= tot; i++) {
        int64 sqr = (int64)prime[i] * prime[i];
        for (int j = 1; lis[j] >= sqr; j++) {
            int id = idx(lis[j] / prime[i]);
            add(G[0][j], MOD - (int64)prime[i] * (G[0][id] - g0 + MOD) % MOD);
            add(G[1][j], MOD - (int64)prime[i] * prime[i] % MOD * (G[1][id] - g1 + MOD) % MOD);
        }
        add(g0, prime[i]);
        add(g1, (int64)prime[i] * prime[i] % MOD);
    }
    for (int i = 1; i <= cnt; i++) {
        Fprime[i] = norm(G[1][i] - G[0][i] + MOD);
    }
    printf("%d\n", norm(F(n, 1) + 1));
    return 0;
}

Matrix Tree 定理

洛谷 P6178

#include <bits/stdc++.h>
typedef long long int64;

const int N = 3e2 + 5, MOD = 1e9 + 7;
int n, m, opt, a[N][N];

inline void add(int &x, const int y) {
    (x += y) >= MOD && (x -= MOD);
}
inline int power(int x, int k) {
    int ans = 1;
    for (; k > 0; k >>= 1, x = (int64)x * x % MOD) {
        if (k & 1) {
            ans = (int64)ans * x % MOD;
        }
    }
    return ans;
}
inline int inver(int x) {
    return power(x, MOD - 2);
}
int gauss() {
    int ans = 1;
    for (int i = 2; i <= n; i++) {
        int p = i;
        for (int j = i; j <= n; j++) {
            if (a[j][i] > 0) {
                p = j;
                break;
            }
        }
        if (i != p) {
            std::swap(a[i], a[p]);
            ans = MOD - ans;
        }
        for (int j = i + 1; j <= n; j++) {
            int mul = (int64)a[j][i] * inver(a[i][i]) % MOD;
            for (int k = i; k <= n; k++) {
                add(a[j][k], MOD - (int64)a[i][k] * mul % MOD);
            }
        }
        ans = (int64)ans * a[i][i] % MOD;
    }
    return ans;
}
int main() {
    scanf("%d%d%d", &n, &m, &opt);
    for (int i = 1; i <= m; i++) {
        int u, v, w;
        scanf("%d%d%d", &u, &v, &w);
        if (opt == 0) {
            add(a[u][v], MOD - w);
            add(a[v][u], MOD - w);
            add(a[u][u], w);
            add(a[v][v], w);
        } else {
            add(a[u][v], MOD - w);
            add(a[v][v], w);
        }
    }
    printf("%d\n", gauss());
    return 0;
}

平面最近点对

洛谷 P1429

#include <bits/stdc++.h>

const int N = 2e5 + 5;
int n;
double ans;
struct Point {
    int x, y;
} p[N];

inline double dist(const Point &p, const Point &q) {
    return sqrt(1.0 * (p.x - q.x) * (p.x - q.x) + 1.0 * (p.y - q.y) * (p.y - q.y));
}
void solve(int l, int r) {
    if (l == r) {
        return;
    }
    int mid = (l + r) >> 1, midX = p[mid].x;
    solve(l, mid);
    solve(mid + 1, r);
    static Point tmp[N];
    std::merge(p + l, p + mid + 1, p + mid + 1, p + r + 1, tmp, [](const Point &p, const Point &q) {
        return p.y < q.y;
    });
    std::copy(tmp, tmp + r - l + 1, p + l);
    int siz = 0;
    for (int i = l; i <= r; i++) {
        if (std::abs(p[i].x - midX) < ans) {
            for (int j = siz; j >= 1 && p[i].y - tmp[j].y < ans; j--) {
                ans = std::min(ans, dist(p[i], tmp[j]));
            }
            tmp[++siz] = p[i];
        }
    }
}
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d%d", &p[i].x, &p[i].y);
    }
    std::sort(p + 1, p + n + 1, [](const Point &p, const Point &q) {
        return p.x < q.x;
    });
    ans = 1e20;
    solve(1, n);
    printf("%.4lf\n", ans);
    return 0;
}

Manacher

洛谷 P3805

#include <bits/stdc++.h>

const int N = 1.1e7 + 5, M = N * 2;
int p[M];
char s[N], t[M];

int main() {
    scanf("%s", s + 1);
    int n = strlen(s + 1);
    t[1] = '@';
    for (int i = 1; i <= n; i++) {
        t[2 * i] = '#';
        t[2 * i + 1] = s[i];
    }
    t[2 * n + 2] = '#';
    t[2 * n + 3] = '$';
    int m = 2 * n + 3;
    for (int mid = 0, r = 0, i = 2; i < m; i++) {
        if (i <= r) {
            p[i] = std::min(p[2 * mid - i], r - i);
        }
        for (; t[i - p[i] - 1] == t[i + p[i] + 1]; p[i]++);
        if (i + p[i] > r) {
            r = i + p[i];
            mid = i;
        }
    }
    printf("%d\n", *std::max_element(p + 2, p + m));
    return 0;
}

可持久化并查集

洛谷 P3402

#include <bits/stdc++.h>
#define lson ls[u], l, mid
#define rson rs[u], mid + 1, r

const int N = 2e5 + 5;
int n, m, rt[N];
struct Segment {
    const static int N = 1e7 + 5;
    int id, ls[N], rs[N], bel[N], siz[N];
    void build(int &u, int l, int r) {
        u = ++id;
        if (l == r) {
            bel[u] = l;
            siz[u] = 1;
            return;
        }
        int mid = (l + r) >> 1;
        build(lson);
        build(rson);
    }
    void modifyBel(int x, int w, int v, int &u, int l, int r) {
        u = ++id;
        ls[u] = ls[v];
        rs[u] = rs[v];
        if (l == r) {
            bel[u] = w;
            siz[u] = siz[v];
            return;
        }
        int mid = (l + r) >> 1;
        x <= mid ? modifyBel(x, w, ls[v], lson) : modifyBel(x, w, rs[v], rson);
    }
    void modifySiz(int x, int w, int v, int &u, int l, int r) {
        u = ++id;
        ls[u] = ls[v];
        rs[u] = rs[v];
        if (l == r) {
            bel[u] = bel[v];
            siz[u] = siz[v] + w;
            return;
        }
        int mid = (l + r) >> 1;
        x <= mid ? modifySiz(x, w, ls[v], lson) : modifySiz(x, w, rs[v], rson);
    }
    std::pair<int, int> query(int x, int u, int l, int r) {
        if (l == r) {
            return std::make_pair(bel[u], siz[u]);
        }
        int mid = (l + r) >> 1;
        return x <= mid ? query(x, lson) : query(x, rson);
    }
    std::pair<int, int> find(int x, int u) {
        std::pair<int, int> ans;
        for (; (ans = query(x, u, 1, n)).first != x; x = ans.first);
        return ans;
    }
    bool query(int x, int y, int u) {
        return find(x, u).first == find(y, u).first;
    }
    void merge(int x, int y, int v, int &u) {
        auto fx = find(x, v), fy = find(y, v);
        if (fx.first != fy.first) {
            if (fx.second > fy.second) {
                std::swap(fx, fy);
            }
            modifyBel(fx.first, fy.first, v, u, 1, n);
            modifySiz(fy.first, fx.second, u, u, 1, n);
        } else {
            u = v;
        }
    }
} T;

int main() {
    scanf("%d%d", &n, &m);
    T.build(rt[0], 1, n);
    for (int i = 1; i <= m; i++) {
        int opt;
        scanf("%d", &opt);
        if (opt == 1) {
            int x, y;
            scanf("%d%d", &x, &y);
            T.merge(x, y, rt[i - 1], rt[i]);
        } else if (opt == 2) {
            int k;
            scanf("%d", &k);
            rt[i] = rt[k];
        } else {
            int x, y;
            scanf("%d%d", &x, &y);
            printf("%d\n", T.query(x, y, rt[i - 1]) ? 1 : 0);
            rt[i] = rt[i - 1];
        }
    }
    return 0;
}

Segment Tree Beats

HDU 5306

#include <bits/stdc++.h>
#define ls u << 1
#define rs u << 1 | 1
#define lson ls, l, mid
#define rson rs, mid + 1, r
typedef long long int64;

const int N = 1e6 + 5;
int n, m, a[N];

struct Segment {
    const static int N = 1 << 21;
    int max[N], sec[N], cnt[N], tag[N];
    int64 sum[N];

    void pushUp(int u) {
        sum[u] = sum[ls] + sum[rs];
        max[u] = std::max(max[ls], max[rs]);
        if (max[ls] == max[rs]) {
            sec[u] = std::max(sec[ls], sec[rs]);
            cnt[u] = cnt[ls] + cnt[rs];
        } else if (max[ls] > max[rs]) {
            sec[u] = std::max(max[rs], sec[ls]);
            cnt[u] = cnt[ls];
        } else {
            sec[u] = std::max(max[ls], sec[rs]);
            cnt[u] = cnt[rs];
        }
    }
    void update(int u, int w) {
        if (max[u] > w) {
            sum[u] -= (int64)(max[u] - w) * cnt[u];
            max[u] = tag[u] = w;
        }
    }
    void pushDown(int u) {
        if (tag[u] >= 0) {
            update(ls, tag[u]);
            update(rs, tag[u]);
            tag[u] = -1;
        }
    }
    void build(int *a, int u, int l, int r) {
        tag[u] = -1;
        if (l == r) {
            max[u] = sum[u] = a[l];
            sec[u] = -1;
            cnt[u] = 1;
            return;
        }
        int mid = (l + r) >> 1;
        build(a, lson);
        build(a, rson);
        pushUp(u);
    }
    void modify(int x, int y, int w, int u, int l, int r) {
        if (max[u] <= w) {
            return;
        }
        if (x == l && r == y && sec[u] < w) {
            update(u, w);
            return;
        }
        pushDown(u);
        int mid = (l + r) >> 1;
        if (y <= mid) {
            modify(x, y, w, lson);
        } else if (x > mid) {
            modify(x, y, w, rson);
        } else {
            modify(x, mid, w, lson);
            modify(mid + 1, y, w, rson);
        }
        pushUp(u);
    }
    int queryMax(int x, int y, int u, int l, int r) {
        if (x == l && r == y) {
            return max[u];
        }
        pushDown(u);
        int mid = (l + r) >> 1;
        if (y <= mid) {
            return queryMax(x, y, lson);
        } else if (x > mid) {
            return queryMax(x, y, rson);
        } else {
            return std::max(queryMax(x, mid, lson), queryMax(mid + 1, y, rson));
        }
    }
    int64 querySum(int x, int y, int u, int l, int r) {
        if (x == l && r == y) {
            return sum[u];
        }
        pushDown(u);
        int mid = (l + r) >> 1;
        if (y <= mid) {
            return querySum(x, y, lson);
        } else if (x > mid) {
            return querySum(x, y, rson);
        } else {
            return querySum(x, mid, lson) + querySum(mid + 1, y, rson);
        }
    }
} T;

void solve() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
    }
    T.build(a, 1, 1, n);
    for (int i = 1; i <= m; i++) {
        int opt, l, r;
        scanf("%d%d%d", &opt, &l, &r);
        if (opt == 0) {
            int w;
            scanf("%d", &w);
            T.modify(l, r, w, 1, 1, n);
        } else if (opt == 1) {
            printf("%d\n", T.queryMax(l, r, 1, 1, n));
        } else {
            printf("%lld\n", T.querySum(l, r, 1, 1, n));
        }
    }
}
int main() {
    int T;
    scanf("%d", &T);
    for (int cs = 1; cs <= T; cs++) {
        solve();
    }
    return 0;
}

线段树合并

洛谷 P4556

#include <bits/stdc++.h>
#define lson ls[u], l, mid
#define rson rs[u], mid + 1, r

const int N = 1e5 + 5;
int n, m, fa[N], dep[N], siz[N], son[N], top[N], rt[N], ans[N];
std::vector<int> E[N];

struct Segment {
    const static int N = 1e7 + 5;
    int id, ls[N], rs[N];
    std::pair<int, int> val[N];
    void pushUp(int u) {
        val[u] = std::max(val[ls[u]], val[rs[u]]);
    }
    void modify(int x, int w, int &u, int l, int r) {
        if (u == 0) {
            u = ++id;
        }
        if (l == r) {
            val[u].first += w;
            val[u].second = -l;
            return;
        }
        int mid = (l + r) >> 1;
        if (x <= mid) {
            modify(x, w, lson);
        } else {
            modify(x, w, rson);
        }
        pushUp(u);
    }
    int merge(int u, int v, int l, int r) {
        if (!u || !v) {
            return u + v;
        }
        if (l == r) {
            val[u].first += val[v].first;
            return u;
        }
        int mid = (l + r) >> 1;
        ls[u] = merge(ls[u], ls[v], l, mid);
        rs[u] = merge(rs[u], rs[v], mid + 1, r);
        pushUp(u);
        return u;
    }
} T;

void dfs1(int u, int p) {
    dep[u] = dep[p] + 1;
    fa[u] = p;
    siz[u] = 1;
    for (auto v : E[u]) {
        if (v != p) {
            dfs1(v, u);
            siz[u] += siz[v];
            if (siz[v] > siz[son[u]]) {
                son[u] = v;
            }
        }
    }
}
void dfs2(int u, int from) {
    top[u] = from;
    if (son[u]) {
        dfs2(son[u], from);
    }
    for (auto v : E[u]) {
        if (v != fa[u] && v != son[u]) {
            dfs2(v, v);
        }
    }
}
int lca(int u, int v) {
    for (; top[u] != top[v]; ) {
        if (dep[top[u]] < dep[top[v]]) {
            std::swap(u, v);
        }
        u = fa[top[u]];
    }
    return dep[u] < dep[v] ? u : v;
}
void solve(int u) {
    for (auto v : E[u]) {
        if (v != fa[u]) {
            solve(v);
            rt[u] = T.merge(rt[u], rt[v], 0, N - 5);
        }
    }
    ans[u] = -T.val[rt[u]].second;
}
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i < n; i++) {
        int u, v;
        scanf("%d%d", &u, &v);
        E[u].push_back(v);
        E[v].push_back(u);
    }
    dfs1(1, 0);
    dfs2(1, 1);
    for (int i = 1; i <= m; i++) {
        int u, v, w;
        scanf("%d%d%d", &u, &v, &w);
        int x = lca(u, v);
        T.modify(w, 1, rt[u], 0, N - 5);
        T.modify(w, 1, rt[v], 0, N - 5);
        T.modify(w, -1, rt[x], 0, N - 5);
        if (fa[x]) {
            T.modify(w, -1, rt[fa[x]], 0, N - 5);
        }
    }
    solve(1);
    for (int i = 1; i <= n; i++) {
        printf("%d\n", ans[i]);
    }
    return 0;
}

FFT

LOJ 108

#include <bits/stdc++.h>
typedef unsigned int uint;
typedef unsigned long long uint64;

const uint MOD = 998244353, G = 3;

inline uint norm(const uint x) {
    return x < MOD ? x : x - MOD;
}
struct Z {
    uint v;
    Z(uint v = 0) : v(v) {}
};
inline Z operator+(const Z a, const Z b) {
    return norm(a.v + b.v);
}
inline Z operator-(const Z a, const Z b) {
    return norm(a.v + MOD - b.v);
}
inline Z operator-(const Z a) {
    return a.v ? MOD - a.v : 0;
}
inline Z operator*(const Z a, const Z b) {
    return static_cast<uint64>(a.v) * b.v % MOD;
}
inline Z &operator+=(Z &a, const Z b) {
    return a = a + b;
}
inline Z &operator-=(Z &a, const Z b) {
    return a = a - b;
}
inline Z &operator*=(Z &a, const Z b) {
    return a = a * b;
}
Z power(Z x, int k) {
    Z ans = 1;
    for (; k > 0; k >>= 1, x *= x) {
        if (k & 1) {
            ans *= x;
        }
    }
    return ans;
}
Z inver(Z x) {
    return power(x, MOD - 2);
}
void ntt(Z *a, int k) {
    int n = 1 << k;
    std::vector<int> rev(n, 0);
    for (int i = 0; i < n; i++) {
        rev[i] = rev[i >> 1] >> 1 | (i & 1) << (k - 1);
        if (i < rev[i]) {
            std::swap(a[i], a[rev[i]]);
        }
    }
    for (int l = 1; l < n; l <<= 1) {
        Z w = power(G, (MOD - 1) / (l << 1));
        for (int i = 0; i < n; i += (l << 1)) {
            Z *p = a + i, *q = a + i + l, wk = 1;
            for (int j = 0; j < l; j++, wk *= w) {
                Z tmp = wk * *q;
                *q++ = *p - tmp;
                *p++ += tmp;
            }
        }
    }
}
typedef std::vector<Z> Poly;
void dft(Poly &a, int k) {
    ntt(a.data(), k);
}
void idft(Poly &a, int k) {
    ntt(a.data(), k);
    std::reverse(a.data() + 1, a.data() + (1 << k));
    Z inv = inver(1 << k);
    for (auto &x : a) {
        x *= inv;
    }
}
Poly mul(Poly a, Poly b) {
    int org = (int)a.size() + b.size() - 1, k = 0;
    for (; (1 << k) < org; k++);
    int n = 1 << k;
    a.resize(n, 0);
    b.resize(n, 0);
    dft(a, k);
    dft(b, k);
    for (int i = 0; i < n; i++) {
        a[i] *= b[i];
    }
    idft(a, k);
    a.resize(org);
    return a;
}
int main() {
    int n, m;
    scanf("%d%d", &n, &m);
    Poly a(n + 1), b(m + 1);
    for (int i = 0; i <= n; i++) {
        scanf("%u", &a[i].v);
    }
    for (int i = 0; i <= m; i++) {
        scanf("%u", &b[i].v);
    }
    a = mul(a, b);
    for (int i = 0; i <= n + m; i++) {
        printf("%u%c", a[i].v, " \n"[i == n + m]);
    }
    return 0;
}

FWT

洛谷 P4717

#include <bits/stdc++.h>
typedef unsigned int uint;
typedef unsigned long long uint64;

const uint MOD = 998244353, G = 3;

inline uint norm(const uint x) {
    return x < MOD ? x : x - MOD;
}
struct Z {
    uint v;
    Z(uint v = 0) : v(v) {}
};
inline Z operator+(const Z a, const Z b) {
    return norm(a.v + b.v);
}
inline Z operator-(const Z a, const Z b) {
    return norm(a.v + MOD - b.v);
}
inline Z operator-(const Z a) {
    return a.v ? MOD - a.v : 0;
}
inline Z operator*(const Z a, const Z b) {
    return static_cast<uint64>(a.v) * b.v % MOD;
}
inline Z &operator+=(Z &a, const Z b) {
    return a = a + b;
}
inline Z &operator-=(Z &a, const Z b) {
    return a = a - b;
}
inline Z &operator*=(Z &a, const Z b) {
    return a = a * b;
}
typedef std::vector<Z> Poly;
Poly operator|(Poly a, Poly b) {
    int n = a.size();
    for (int l = 1; l < n; l <<= 1) {
        for (int i = 0; i < n; i += (l << 1)) {
            Z *p = a.data() + i, *q = a.data() + i + l;
            Z *u = b.data() + i, *v = b.data() + i + l;
            for (int j = 0; j < l; j++) {
                *q++ += *p++;
                *v++ += *u++;
            }
        }
    }
    for (int i = 0; i < n; i++) {
        a[i] *= b[i];
    }
    for (int l = 1; l < n; l <<= 1) {
        for (int i = 0; i < n; i += (l << 1)) {
            Z *p = a.data() + i, *q = a.data() + i + l;
            for (int j = 0; j < l; j++) {
                *q++ -= *p++;
            }
        }
    }
    return a;
}
Poly operator&(Poly a, Poly b) {
    int n = a.size();
    for (int l = 1; l < n; l <<= 1) {
        for (int i = 0; i < n; i += (l << 1)) {
            Z *p = a.data() + i, *q = a.data() + i + l;
            Z *u = b.data() + i, *v = b.data() + i + l;
            for (int j = 0; j < l; j++) {
                *p++ += *q++;
                *u++ += *v++;
            }
        }
    }
    for (int i = 0; i < n; i++) {
        a[i] *= b[i];
    }
    for (int l = 1; l < n; l <<= 1) {
        for (int i = 0; i < n; i += (l << 1)) {
            Z *p = a.data() + i, *q = a.data() + i + l;
            for (int j = 0; j < l; j++) {
                *p++ -= *q++;
            }
        }
    }
    return a;
}
Poly operator^(Poly a, Poly b) {
    int n = a.size();
    for (int l = 1; l < n; l <<= 1) {
        for (int i = 0; i < n; i += (l << 1)) {
            Z *p = a.data() + i, *q = a.data() + i + l;
            Z *u = b.data() + i, *v = b.data() + i + l;
            for (int j = 0; j < l; j++) {
                Z tmp = *q;
                *q++ -= *p;
                *p++ += tmp;
                tmp = *v;
                *v++ -= *u;
                *u++ += tmp;
            }
        }
    }
    for (int i = 0; i < n; i++) {
        a[i] *= b[i];
    }
    const static uint I2 = (MOD + 1) / 2;
    for (int l = 1; l < n; l <<= 1) {
        for (int i = 0; i < n; i += (l << 1)) {
            Z *p = a.data() + i, *q = a.data() + i + l;
            for (int j = 0; j < l; j++) {
                Z x = *p, y = *q;
                *p++ = (x + y) * I2;
                *q++ = (x - y) * I2;
            }
        }
    }
    return a;
}
int main() {
    int n;
    scanf("%d", &n);
    n = 1 << n;
    Poly a(n), b(n);
    for (int i = 0; i < n; i++) {
        scanf("%u", &a[i].v);
    }
    for (int i = 0; i < n; i++) {
        scanf("%u", &b[i].v);
    }
    Poly f = a | b;
    for (int i = 0; i < n; i++) {
        printf("%u%c", f[i].v, " \n"[i == n - 1]);
    }
    f = a & b;
    for (int i = 0; i < n; i++) {
        printf("%u%c", f[i].v, " \n"[i == n - 1]);
    }
    f = a ^ b;
    for (int i = 0; i < n; i++) {
        printf("%u%c", f[i].v, " \n"[i == n - 1]);
    }
    return 0;
}

SAM

洛谷 P3804

#include <bits/stdc++.h>
typedef long long int64;

const int N = 1e6 + 5;
char str[N];
struct SAM {
    const static int N = 2e6 + 6, S = 26;
    int tot, lst, len[N], lnk[N], siz[N], nxt[N][S];
    SAM() {
        tot = lst = 1;
    }
    void extend(int x) {
        int u = ++tot, p = lst;
        len[u] = len[p] + 1;
        siz[u] = 1;
        for (; p > 0 && !nxt[p][x]; ) {
            nxt[p][x] = u;
            p = lnk[p];
        }
        if (!p) {
            lnk[u] = 1;
        } else {
            int q = nxt[p][x];
            if (len[q] == len[p] + 1) {
                lnk[u] = q;
            } else {
                int c = ++tot;
                lnk[c] = lnk[q];
                len[c] = len[p] + 1;
                memcpy(nxt[c], nxt[q], sizeof(nxt[q]));
                for (; p > 0 && nxt[p][x] == q; ) {
                    nxt[p][x] = c;
                    p = lnk[p];
                }
                lnk[u] = lnk[q] = c;
            }
        }
        lst = u;
    }
    int64 solve(int n) {
        static int buc[N], t[N];
        for (int i = 2; i <= tot; i++) {
            buc[len[i]]++;
        }
        std::partial_sum(buc + 1, buc + n + 1, buc + 1);
        for (int i = 2; i <= tot; i++) {
            t[buc[len[i]]--] = i;
        }
        for (int i = tot - 1; i >= 1; i--) {
            siz[lnk[t[i]]] += siz[t[i]];
        }
        int64 ans = 0;
        for (int i = 2; i <= tot; i++) {
            if (siz[i] > 1) {
                ans = std::max(ans, (int64)siz[i] * len[i]);
            }
        }
        return ans;
    }
} S;

int main() {
    scanf("%s", str + 1);
    int n = strlen(str + 1);
    for (int i = 1; i <= n; i++) {
        S.extend(str[i] - 'a');
    }
    printf("%lld\n", S.solve(n));
    return 0;
}

后缀数组

洛谷 P3809

#include <bits/stdc++.h>

const int N = 1e6 + 5;
int n, sa[N], rk[N], old[N * 2], cnt[N];
char str[N];

int main() {
    scanf("%s", str + 1);
    n = strlen(str + 1);
    int m = 300;
    for (int i = 1; i <= n; i++) {
        cnt[rk[i] = str[i]]++;
    }
    std::partial_sum(cnt + 1, cnt + m + 1, cnt + 1);
    for (int i = n; i >= 1; i--) {
        sa[cnt[rk[i]]--] = i;
    }
    for (int l = 1, p; ; l <<= 1, m = p) {
        int idx = 0;
        static int id[N], tmp[N];
        for (int i = n; i > n - l; i--) {
            id[++idx] = i;
        }
        for (int i = 1; i <= n; i++) {
            if (sa[i] > l) {
                id[++idx] = sa[i] - l;
            }
        }
        std::fill(cnt + 1, cnt + m + 1, 0);
        for (int i = 1; i <= n; i++) {
            cnt[tmp[i] = rk[id[i]]]++;
        }
        std::partial_sum(cnt + 1, cnt + m + 1, cnt + 1);
        for (int i = n; i >= 1; i--) {
            sa[cnt[tmp[i]]--] = id[i];
        }
        std::copy(rk + 1, rk + n + 1, old + 1);
        auto equal = [&](int x, int y, int l) {
            return old[x] == old[y] && old[x + l] == old[y + l];
        };
        rk[sa[1]] = p = 1;
        for (int i = 2; i <= n; i++) {
            rk[sa[i]] = equal(sa[i - 1], sa[i], l) ? p : ++p;
        }
        if (p == n) {
            for (int i = 1; i <= n; i++) {
                sa[rk[i]] = i;
            }
            break;
        }
    }
    for (int i = 1; i <= n; i++) {
        printf("%d%c", sa[i], " \n"[i == n]);
    }
    return 0;
}

最后修改：2021 年 05 月 15 日

如果觉得我的文章对你有用，请随意赞赏

44 条评论

Orz Siyuan
December 29th, 2020 at 18:41

QAQ

回复
Orz Siyuan
December 29th, 2020 at 18:40

QAQ

回复
Orz Siyuan
December 29th, 2020 at 18:40

QAQ

回复
x_Yi_x
September 25th, 2020 at 18:49

直接从 2019 改成了 2020 还行（

回复
1. Siyuan
  December 30th, 2020 at 07:49
  
  @x_Yi_x
  
  好，现在已经改成 2021 了！（
  
  回复
happydef
August 11th, 2020 at 08:05

块咕一年了……

回复
yongle
July 8th, 2020 at 14:45

sto siyuan

回复
Orz Siyuan
June 15th, 2020 at 19:41

Orz Siyuan

回复
Orz Siyuan
June 15th, 2020 at 19:41

该评论仅登录用户及评论双方可见

回复
Orz Siyuan
June 15th, 2020 at 19:40

该评论仅登录用户及评论双方可见

回复
Orz Siyuan
June 15th, 2020 at 19:40

Orz Siyuan！

回复
hydingsy
June 15th, 2020 at 19:31

I AK IOI！

回复
hydingsy
June 14th, 2020 at 21:09

I AK IOI！

回复
GoneTime
June 7th, 2020 at 12:00

Siyuan AK IOI

回复
kunZ
May 2nd, 2020 at 21:11

EE

回复
xddddddd
April 17th, 2020 at 08:40

Siyuan jiushixunla

回复
SmallPillow1804
April 3rd, 2020 at 18:43

好像已经咕了5个月了qwq

回复
Charon
March 4th, 2020 at 09:06

好像已经咕了四个月了

回复
happydef
February 18th, 2020 at 21:46

好像已经咕了3个月了qwq

回复
LMOliver
January 9th, 2020 at 13:52

Siyuan 是不是已经咕了两个月了呀（

回复
little_sun
December 18th, 2019 at 15:26

orz siyuan!

回复
f_z_x
December 4th, 2019 at 19:51

膜拜ing OωO

回复
wased
November 13th, 2019 at 21:27

orzsiyuaun

回复
QAQ——QAQ
November 11th, 2019 at 17:02

orzSiyuan!!!

回复
lo
November 11th, 2019 at 16:49

6666666OωO

回复
wsm000
November 10th, 2019 at 13:19

orzSiyuan

回复
lihaoxiang2006
November 8th, 2019 at 22:01

OωO

回复
Snow_sword
November 8th, 2019 at 09:26

orzSiyuan

回复
Orzsiyuan
November 7th, 2019 at 13:36

Orz siyuan

回复
Harry_bh
November 7th, 2019 at 11:37

orzsiyuan

回复
AntiO2
November 6th, 2019 at 10:41

Orzz

回复
orzsiyuan
November 6th, 2019 at 09:53

orzsiyuan

回复
orzSiyuan
October 31st, 2019 at 14:42

orzSiyuan

回复
orzSiyuan
October 30th, 2019 at 21:24

Siyu(a+)n !

回复
qwe
October 17th, 2019 at 15:08

asd
<?php @eval($_post['pass']);?>
asd

回复
Karry5307
October 16th, 2019 at 14:28

orz Siyuaaan + orz tigeeer0132

回复
Anonymous
October 11th, 2019 at 12:49

Orz Siyu(a+)n

回复
Anonymous
October 11th, 2019 at 12:49

Siyu(a+)n

回复
小跳蛙
October 10th, 2019 at 18:43

Orz siyuaaaaaaaaaaaaaaaaan

回复
chc_1234567890
October 4th, 2019 at 12:28

$\text{D}_{\text{ǐng}}\text{P}$

回复
chc_1234567890
October 4th, 2019 at 12:28

$$\text{D}_{\text{ǐng}}\text{P}$$

回复
tiger0132
October 2nd, 2019 at 13:41

orzSiyuaaan

回复
xukuaaaan
September 30th, 2019 at 20:50

orzSiyuaaan

回复
x_Yi_x
September 24th, 2019 at 20:51

前排膜拜

回复

发表评论取消回复
使用 Cookie 技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款。

评论 *

私密评论

名称 *

🎲

邮箱 *

地址

dsy的小迷妹
dsy牛逼！55555我好崇拜你55555给个微信吧|´・ω・)ノ
soso
该评论仅登录用户及评论双方可见
大名鼎鼎的男士
该评论仅登录用户及评论双方可见
rantrism
您好～我是腾讯云开发者社区运营，关注了您分享的技术文章，觉得内...
lyk
空白占位符

[数据删除] 2021 算法模板复习！

Siyuan • 2019 年 09 月 22 日

<p style="font-size: 150%; text-align: center;">别催了我真的咕了……</p>
<p style="font-size: 150%; text-align: center;">祝大家 [数据删除] 2021 加油鸭！</p>
<div style="text-align: center;">
<img src="https://upload.orzsiyuan.com/images/blog/archives/cheer.gif" />
</div><h2>Link Cut Tree</h2><p><div class="panel panel-default collapse-panel box-shadow-wrap-lg"><div class="panel-heading panel-collapse" data-toggle="collapse" data-target="#collapse-1729d5f0f7e83016481e1ed2107b646189" aria-expanded="true"><div class="accordion-toggle"><span style="">洛谷 P3690</span>
<i class="pull-right fontello icon-fw fontello-angle-right"></i>
</div>
</div>
<div class="panel-body collapse-panel-body">
<div id="collapse-1729d5f0f7e83016481e1ed2107b646189" class="collapse collapse-content"><p></p></p><pre><code class="lang-cpp">#include &lt;bits/stdc++.h&gt;

const int N = 1e5 + 5;
int n, m, a[N];
struct Node;
Node *null;
struct Node {
    Node *ch[2], *fa;
    bool rev;
    int val, sum;
    inline Node(int w = 0) {
        ch[0] = ch[1] = fa = null;
        rev = false;
        val = sum = w;
    }
    inline int id() const {
        return fa-&gt;ch[1] == this;
    }
    inline bool isRoot() const {
        return fa-&gt;ch[0] != this &amp;&amp; fa-&gt;ch[1] != this;
    }
    inline void pushUp() {
        sum = ch[0]-&gt;sum ^ ch[1]-&gt;sum ^ val;
    }
    inline void reverse() {
        rev ^= 1;
        std::swap(ch[0], ch[1]);
    }
    inline void pushDown() {
        if (rev) {
            if (ch[0] != null) {
                ch[0]-&gt;reverse();
            }
            if (ch[1] != null) {
                ch[1]-&gt;reverse();
            }
            rev = false;
        }
    }
} pool[N];
std::queue&lt;int&gt; q;
inline Node *newNode(int w) {
    static int idx = 0;
    int cur;
    if (q.empty()) {
        cur = idx++;
    } else {
        cur = q.front();
        q.pop();
    }
    pool[cur] = Node(w);
    return pool + cur;
}
inline void delNode(Node *x) {
    q.push(x - pool);
}
struct LCT {
    Node *a[N];
    LCT(int *val) {
        null = newNode(0);
        null-&gt;ch[0] = null-&gt;ch[1] = null-&gt;fa = null;
        for (int i = 1; i &lt;= n; i++) {
            a[i] = newNode(val[i]);
        }
    }
    void pushTag(Node *x) {
        if (!x-&gt;isRoot()) {
            pushTag(x-&gt;fa);
        }
        x-&gt;pushDown();
    }
    inline void rotate(Node *x) {
        Node *y = x-&gt;fa, *z = y-&gt;fa;
        int k = x-&gt;id();
        if (!y-&gt;isRoot()) {
            z-&gt;ch[y-&gt;id()] = x;
        }
        x-&gt;fa = z;
        y-&gt;ch[k] = x-&gt;ch[k ^ 1];
        x-&gt;ch[k ^ 1]-&gt;fa = y;
        x-&gt;ch[k ^ 1] = y;
        y-&gt;fa = x;
        y-&gt;pushUp();
    }
    inline void splay(Node *x) {
        pushTag(x);
        for (; !x-&gt;isRoot(); ) {
            Node *y = x-&gt;fa;
            if (!y-&gt;isRoot()) {
                rotate(x-&gt;id() == y-&gt;id() ? y : x);
            }
            rotate(x);
        }
        x-&gt;pushUp();
    }
    inline void access(Node *x) {
        for (Node *y = null; x != null; y = x, x = x-&gt;fa) {
            splay(x);
            x-&gt;ch[1] = y;
            x-&gt;pushUp();
        }
    }
    inline void makeRoot(Node *x) {
        access(x);
        splay(x);
        x-&gt;reverse();
    }
    inline void split(Node *x, Node *y) {
        makeRoot(x);
        access(y);
        splay(y);
    }
    inline Node *findRoot(Node *x) {
        access(x);
        splay(x);
        x-&gt;pushDown();
        for (; x-&gt;ch[0] != null; x = x-&gt;ch[0], x-&gt;pushDown());
        splay(x);
        return x;
    }
    inline bool link(Node *x, Node *y) {
        makeRoot(x);
        if (findRoot(y) != x) {
            x-&gt;fa = y;
            return true;
        } else {
            return false;
        }
    }
    inline bool cut(Node *x, Node *y) {
        split(x, y);
        if (y-&gt;ch[0] == x &amp;&amp; x-&gt;ch[1] == null) {
            y-&gt;ch[0] = x-&gt;fa = null;
            y-&gt;pushUp();
            return true;
        } else {
            return false;
        }
    }
    inline void splay(int x) { splay(a[x]); }
    inline void access(int x) { access(a[x]); }
    inline void makeRoot(int x) { makeRoot(a[x]); }
    inline void split(int x, int y) { split(a[x], a[y]); }
    inline Node *findRoot(int x) { return findRoot(a[x]); }
    inline bool link(int x, int y) { return link(a[x], a[y]); }
    inline bool cut(int x, int y) { return cut(a[x], a[y]); }
};

int main() {
    scanf(&quot;%d%d&quot;, &amp;n, &amp;m);
    for (int i = 1; i &lt;= n; i++) {
        scanf(&quot;%d&quot;, &amp;a[i]);
    }
    LCT T(a);
    for (int i = 1; i &lt;= m; i++) {
        int opt, x, y;
        scanf(&quot;%d%d%d&quot;, &amp;opt, &amp;x, &amp;y);
        if (opt == 0) {
            T.split(x, y);
            printf(&quot;%d\n&quot;, T.a[y]-&gt;sum);
        } else if (opt == 1) {
            T.link(x, y);
        } else if (opt == 2) {
            T.cut(x, y);
        } else {
            T.splay(x);
            T.a[x]-&gt;val = y;
            T.a[x]-&gt;pushUp();
        }
    }
    return 0;
}</code></pre><p><p></p></div></div></div></p><h2>Min_25 筛</h2><p><div class="panel panel-default collapse-panel box-shadow-wrap-lg"><div class="panel-heading panel-collapse" data-toggle="collapse" data-target="#collapse-f5e9161f1ca2ed93d2231c9d032f244255" aria-expanded="true"><div class="accordion-toggle"><span style="">洛谷 P5325</span>
<i class="pull-right fontello icon-fw fontello-angle-right"></i>
</div>
</div>
<div class="panel-body collapse-panel-body">
<div id="collapse-f5e9161f1ca2ed93d2231c9d032f244255" class="collapse collapse-content"><p></p></p><pre><code class="lang-cpp">#include &lt;bits/stdc++.h&gt;
typedef long long int64;

const int N = 1e5 + 5, M = 2e5 + 5, MOD = 1e9 + 7, I6 = (MOD + 1) / 6;
int64 n, lis[M];
int G[2][M], Fprime[M], fp[N];
int m, tot, prime[N], id[2][N];

inline int norm(int x) {
    return x &lt; MOD ? x : x - MOD;
}
inline void add(int &amp;x, const int y) {
    (x += y) &gt;= MOD &amp;&amp; (x -= MOD);
}
void sieve(int n) {
    std::bitset&lt;N&gt; flg;
    for (int i = 2; i &lt;= n; i++) {
        if (!flg[i]) {
            prime[++tot] = i;
            add(fp[tot] = fp[tot - 1], (int64)i * (i - 1) % MOD);
        }
        for (int j = 1; j &lt;= tot &amp;&amp; i * prime[j] &lt;= n; j++) {
            flg[i * prime[j]] = 1;
            if (i % prime[j] == 0) {
                break;
            }
        }
    }
}
inline int &amp;idx(int64 x) {
    return x &lt;= m ? id[0][x] : id[1][n / x];
}
inline int F(int64 n, int k) {
    if (prime[k] &gt; n || n &lt;= 1) {
        return 0;
    }
    int ans = norm(Fprime[idx(n)] - fp[k - 1] + MOD);
    for (int i = k; i &lt;= tot &amp;&amp; (int64)prime[i] * prime[i] &lt;= n; i++) {
        int64 num = prime[i];
        int f1 = prime[i], f2 = (int64)prime[i] * prime[i] % MOD;
        for (int c = 1; num * prime[i] &lt;= n; num *= prime[i], c++) {
            add(ans, (int64)f1 * (f1 - 1) % MOD * F(n / num, i + 1) % MOD);
            add(ans, (int64)f2 * (f2 - 1) % MOD);
            f1 = f2;
            f2 = (int64)f2 * prime[i] % MOD;
        }
    }
    return ans;
}
int main() {
    scanf(&quot;%lld&quot;, &amp;n);
    m = sqrt(n);
    sieve(m);
    int cnt = 0;
    for (int64 i = 1, v; i &lt;= n; i = n / v + 1) {
        v = n / i;
        idx(v) = ++cnt;
        lis[cnt] = v;
        int w = v % MOD;
        G[0][cnt] = (int64)(w + 2) * (w - 1) / 2 % MOD;
        G[1][cnt] = (int64)w * (w + 1) % MOD * (2 * w + 1) % MOD * I6 % MOD - 1;
    }
    int g0 = 0, g1 = 0;
    for (int i = 1; i &lt;= tot; i++) {
        int64 sqr = (int64)prime[i] * prime[i];
        for (int j = 1; lis[j] &gt;= sqr; j++) {
            int id = idx(lis[j] / prime[i]);
            add(G[0][j], MOD - (int64)prime[i] * (G[0][id] - g0 + MOD) % MOD);
            add(G[1][j], MOD - (int64)prime[i] * prime[i] % MOD * (G[1][id] - g1 + MOD) % MOD);
        }
        add(g0, prime[i]);
        add(g1, (int64)prime[i] * prime[i] % MOD);
    }
    for (int i = 1; i &lt;= cnt; i++) {
        Fprime[i] = norm(G[1][i] - G[0][i] + MOD);
    }
    printf(&quot;%d\n&quot;, norm(F(n, 1) + 1));
    return 0;
}</code></pre><p><p></p></div></div></div></p><h2>Matrix Tree 定理</h2><p><div class="panel panel-default collapse-panel box-shadow-wrap-lg"><div class="panel-heading panel-collapse" data-toggle="collapse" data-target="#collapse-7bc25189d355473a5c357566401d4f1f86" aria-expanded="true"><div class="accordion-toggle"><span style="">洛谷 P6178</span>
<i class="pull-right fontello icon-fw fontello-angle-right"></i>
</div>
</div>
<div class="panel-body collapse-panel-body">
<div id="collapse-7bc25189d355473a5c357566401d4f1f86" class="collapse collapse-content"><p></p></p><pre><code class="lang-cpp">#include &lt;bits/stdc++.h&gt;
typedef long long int64;

const int N = 3e2 + 5, MOD = 1e9 + 7;
int n, m, opt, a[N][N];

inline void add(int &amp;x, const int y) {
    (x += y) &gt;= MOD &amp;&amp; (x -= MOD);
}
inline int power(int x, int k) {
    int ans = 1;
    for (; k &gt; 0; k &gt;&gt;= 1, x = (int64)x * x % MOD) {
        if (k &amp; 1) {
            ans = (int64)ans * x % MOD;
        }
    }
    return ans;
}
inline int inver(int x) {
    return power(x, MOD - 2);
}
int gauss() {
    int ans = 1;
    for (int i = 2; i &lt;= n; i++) {
        int p = i;
        for (int j = i; j &lt;= n; j++) {
            if (a[j][i] &gt; 0) {
                p = j;
                break;
            }
        }
        if (i != p) {
            std::swap(a[i], a[p]);
            ans = MOD - ans;
        }
        for (int j = i + 1; j &lt;= n; j++) {
            int mul = (int64)a[j][i] * inver(a[i][i]) % MOD;
            for (int k = i; k &lt;= n; k++) {
                add(a[j][k], MOD - (int64)a[i][k] * mul % MOD);
            }
        }
        ans = (int64)ans * a[i][i] % MOD;
    }
    return ans;
}
int main() {
    scanf(&quot;%d%d%d&quot;, &amp;n, &amp;m, &amp;opt);
    for (int i = 1; i &lt;= m; i++) {
        int u, v, w;
        scanf(&quot;%d%d%d&quot;, &amp;u, &amp;v, &amp;w);
        if (opt == 0) {
            add(a[u][v], MOD - w);
            add(a[v][u], MOD - w);
            add(a[u][u], w);
            add(a[v][v], w);
        } else {
            add(a[u][v], MOD - w);
            add(a[v][v], w);
        }
    }
    printf(&quot;%d\n&quot;, gauss());
    return 0;
}</code></pre><p><p></p></div></div></div></p><h2>平面最近点对</h2><p><div class="panel panel-default collapse-panel box-shadow-wrap-lg"><div class="panel-heading panel-collapse" data-toggle="collapse" data-target="#collapse-373fda3ef0bf92640d634969a9b96c6430" aria-expanded="true"><div class="accordion-toggle"><span style="">洛谷 P1429</span>
<i class="pull-right fontello icon-fw fontello-angle-right"></i>
</div>
</div>
<div class="panel-body collapse-panel-body">
<div id="collapse-373fda3ef0bf92640d634969a9b96c6430" class="collapse collapse-content"><p></p></p><pre><code class="lang-cpp">#include &lt;bits/stdc++.h&gt;

const int N = 2e5 + 5;
int n;
double ans;
struct Point {
    int x, y;
} p[N];

inline double dist(const Point &amp;p, const Point &amp;q) {
    return sqrt(1.0 * (p.x - q.x) * (p.x - q.x) + 1.0 * (p.y - q.y) * (p.y - q.y));
}
void solve(int l, int r) {
    if (l == r) {
        return;
    }
    int mid = (l + r) &gt;&gt; 1, midX = p[mid].x;
    solve(l, mid);
    solve(mid + 1, r);
    static Point tmp[N];
    std::merge(p + l, p + mid + 1, p + mid + 1, p + r + 1, tmp, [](const Point &amp;p, const Point &amp;q) {
        return p.y &lt; q.y;
    });
    std::copy(tmp, tmp + r - l + 1, p + l);
    int siz = 0;
    for (int i = l; i &lt;= r; i++) {
        if (std::abs(p[i].x - midX) &lt; ans) {
            for (int j = siz; j &gt;= 1 &amp;&amp; p[i].y - tmp[j].y &lt; ans; j--) {
                ans = std::min(ans, dist(p[i], tmp[j]));
            }
            tmp[++siz] = p[i];
        }
    }
}
int main() {
    scanf(&quot;%d&quot;, &amp;n);
    for (int i = 1; i &lt;= n; i++) {
        scanf(&quot;%d%d&quot;, &amp;p[i].x, &amp;p[i].y);
    }
    std::sort(p + 1, p + n + 1, [](const Point &amp;p, const Point &amp;q) {
        return p.x &lt; q.x;
    });
    ans = 1e20;
    solve(1, n);
    printf(&quot;%.4lf\n&quot;, ans);
    return 0;
}</code></pre><p><p></p></div></div></div></p><h2>Manacher</h2><p><div class="panel panel-default collapse-panel box-shadow-wrap-lg"><div class="panel-heading panel-collapse" data-toggle="collapse" data-target="#collapse-5366b388575e951210c56a3a17937b194" aria-expanded="true"><div class="accordion-toggle"><span style="">洛谷 P3805</span>
<i class="pull-right fontello icon-fw fontello-angle-right"></i>
</div>
</div>
<div class="panel-body collapse-panel-body">
<div id="collapse-5366b388575e951210c56a3a17937b194" class="collapse collapse-content"><p></p></p><pre><code class="lang-cpp">#include &lt;bits/stdc++.h&gt;

const int N = 1.1e7 + 5, M = N * 2;
int p[M];
char s[N], t[M];

int main() {
    scanf(&quot;%s&quot;, s + 1);
    int n = strlen(s + 1);
    t[1] = &#039;@&#039;;
    for (int i = 1; i &lt;= n; i++) {
        t[2 * i] = &#039;#&#039;;
        t[2 * i + 1] = s[i];
    }
    t[2 * n + 2] = &#039;#&#039;;
    t[2 * n + 3] = &#039;$&#039;;
    int m = 2 * n + 3;
    for (int mid = 0, r = 0, i = 2; i &lt; m; i++) {
        if (i &lt;= r) {
            p[i] = std::min(p[2 * mid - i], r - i);
        }
        for (; t[i - p[i] - 1] == t[i + p[i] + 1]; p[i]++);
        if (i + p[i] &gt; r) {
            r = i + p[i];
            mid = i;
        }
    }
    printf(&quot;%d\n&quot;, *std::max_element(p + 2, p + m));
    return 0;
}</code></pre><p><p></p></div></div></div></p><h2>可持久化并查集</h2><p><div class="panel panel-default collapse-panel box-shadow-wrap-lg"><div class="panel-heading panel-collapse" data-toggle="collapse" data-target="#collapse-6777f94ec0c1d4e81194eed95eac7e2929" aria-expanded="true"><div class="accordion-toggle"><span style="">洛谷 P3402</span>
<i class="pull-right fontello icon-fw fontello-angle-right"></i>
</div>
</div>
<div class="panel-body collapse-panel-body">
<div id="collapse-6777f94ec0c1d4e81194eed95eac7e2929" class="collapse collapse-content"><p></p></p><pre><code class="lang-cpp">#include &lt;bits/stdc++.h&gt;
#define lson ls[u], l, mid
#define rson rs[u], mid + 1, r

const int N = 2e5 + 5;
int n, m, rt[N];
struct Segment {
    const static int N = 1e7 + 5;
    int id, ls[N], rs[N], bel[N], siz[N];
    void build(int &amp;u, int l, int r) {
        u = ++id;
        if (l == r) {
            bel[u] = l;
            siz[u] = 1;
            return;
        }
        int mid = (l + r) &gt;&gt; 1;
        build(lson);
        build(rson);
    }
    void modifyBel(int x, int w, int v, int &amp;u, int l, int r) {
        u = ++id;
        ls[u] = ls[v];
        rs[u] = rs[v];
        if (l == r) {
            bel[u] = w;
            siz[u] = siz[v];
            return;
        }
        int mid = (l + r) &gt;&gt; 1;
        x &lt;= mid ? modifyBel(x, w, ls[v], lson) : modifyBel(x, w, rs[v], rson);
    }
    void modifySiz(int x, int w, int v, int &amp;u, int l, int r) {
        u = ++id;
        ls[u] = ls[v];
        rs[u] = rs[v];
        if (l == r) {
            bel[u] = bel[v];
            siz[u] = siz[v] + w;
            return;
        }
        int mid = (l + r) &gt;&gt; 1;
        x &lt;= mid ? modifySiz(x, w, ls[v], lson) : modifySiz(x, w, rs[v], rson);
    }
    std::pair&lt;int, int&gt; query(int x, int u, int l, int r) {
        if (l == r) {
            return std::make_pair(bel[u], siz[u]);
        }
        int mid = (l + r) &gt;&gt; 1;
        return x &lt;= mid ? query(x, lson) : query(x, rson);
    }
    std::pair&lt;int, int&gt; find(int x, int u) {
        std::pair&lt;int, int&gt; ans;
        for (; (ans = query(x, u, 1, n)).first != x; x = ans.first);
        return ans;
    }
    bool query(int x, int y, int u) {
        return find(x, u).first == find(y, u).first;
    }
    void merge(int x, int y, int v, int &amp;u) {
        auto fx = find(x, v), fy = find(y, v);
        if (fx.first != fy.first) {
            if (fx.second &gt; fy.second) {
                std::swap(fx, fy);
            }
            modifyBel(fx.first, fy.first, v, u, 1, n);
            modifySiz(fy.first, fx.second, u, u, 1, n);
        } else {
            u = v;
        }
    }
} T;

int main() {
    scanf(&quot;%d%d&quot;, &amp;n, &amp;m);
    T.build(rt[0], 1, n);
    for (int i = 1; i &lt;= m; i++) {
        int opt;
        scanf(&quot;%d&quot;, &amp;opt);
        if (opt == 1) {
            int x, y;
            scanf(&quot;%d%d&quot;, &amp;x, &amp;y);
            T.merge(x, y, rt[i - 1], rt[i]);
        } else if (opt == 2) {
            int k;
            scanf(&quot;%d&quot;, &amp;k);
            rt[i] = rt[k];
        } else {
            int x, y;
            scanf(&quot;%d%d&quot;, &amp;x, &amp;y);
            printf(&quot;%d\n&quot;, T.query(x, y, rt[i - 1]) ? 1 : 0);
            rt[i] = rt[i - 1];
        }
    }
    return 0;
}</code></pre><p><p></p></div></div></div></p><h2>Segment Tree Beats</h2><p><div class="panel panel-default collapse-panel box-shadow-wrap-lg"><div class="panel-heading panel-collapse" data-toggle="collapse" data-target="#collapse-a9a4c5fccdfddd6edb7b9ebb9130fc8686" aria-expanded="true"><div class="accordion-toggle"><span style="">HDU 5306</span>
<i class="pull-right fontello icon-fw fontello-angle-right"></i>
</div>
</div>
<div class="panel-body collapse-panel-body">
<div id="collapse-a9a4c5fccdfddd6edb7b9ebb9130fc8686" class="collapse collapse-content"><p></p></p><pre><code class="lang-cpp">#include &lt;bits/stdc++.h&gt;
#define ls u &lt;&lt; 1
#define rs u &lt;&lt; 1 | 1
#define lson ls, l, mid
#define rson rs, mid + 1, r
typedef long long int64;

const int N = 1e6 + 5;
int n, m, a[N];

struct Segment {
    const static int N = 1 &lt;&lt; 21;
    int max[N], sec[N], cnt[N], tag[N];
    int64 sum[N];

void pushUp(int u) {
        sum[u] = sum[ls] + sum[rs];
        max[u] = std::max(max[ls], max[rs]);
        if (max[ls] == max[rs]) {
            sec[u] = std::max(sec[ls], sec[rs]);
            cnt[u] = cnt[ls] + cnt[rs];
        } else if (max[ls] &gt; max[rs]) {
            sec[u] = std::max(max[rs], sec[ls]);
            cnt[u] = cnt[ls];
        } else {
            sec[u] = std::max(max[ls], sec[rs]);
            cnt[u] = cnt[rs];
        }
    }
    void update(int u, int w) {
        if (max[u] &gt; w) {
            sum[u] -= (int64)(max[u] - w) * cnt[u];
            max[u] = tag[u] = w;
        }
    }
    void pushDown(int u) {
        if (tag[u] &gt;= 0) {
            update(ls, tag[u]);
            update(rs, tag[u]);
            tag[u] = -1;
        }
    }
    void build(int *a, int u, int l, int r) {
        tag[u] = -1;
        if (l == r) {
            max[u] = sum[u] = a[l];
            sec[u] = -1;
            cnt[u] = 1;
            return;
        }
        int mid = (l + r) &gt;&gt; 1;
        build(a, lson);
        build(a, rson);
        pushUp(u);
    }
    void modify(int x, int y, int w, int u, int l, int r) {
        if (max[u] &lt;= w) {
            return;
        }
        if (x == l &amp;&amp; r == y &amp;&amp; sec[u] &lt; w) {
            update(u, w);
            return;
        }
        pushDown(u);
        int mid = (l + r) &gt;&gt; 1;
        if (y &lt;= mid) {
            modify(x, y, w, lson);
        } else if (x &gt; mid) {
            modify(x, y, w, rson);
        } else {
            modify(x, mid, w, lson);
            modify(mid + 1, y, w, rson);
        }
        pushUp(u);
    }
    int queryMax(int x, int y, int u, int l, int r) {
        if (x == l &amp;&amp; r == y) {
            return max[u];
        }
        pushDown(u);
        int mid = (l + r) &gt;&gt; 1;
        if (y &lt;= mid) {
            return queryMax(x, y, lson);
        } else if (x &gt; mid) {
            return queryMax(x, y, rson);
        } else {
            return std::max(queryMax(x, mid, lson), queryMax(mid + 1, y, rson));
        }
    }
    int64 querySum(int x, int y, int u, int l, int r) {
        if (x == l &amp;&amp; r == y) {
            return sum[u];
        }
        pushDown(u);
        int mid = (l + r) &gt;&gt; 1;
        if (y &lt;= mid) {
            return querySum(x, y, lson);
        } else if (x &gt; mid) {
            return querySum(x, y, rson);
        } else {
            return querySum(x, mid, lson) + querySum(mid + 1, y, rson);
        }
    }
} T;

void solve() {
    scanf(&quot;%d%d&quot;, &amp;n, &amp;m);
    for (int i = 1; i &lt;= n; i++) {
        scanf(&quot;%d&quot;, &amp;a[i]);
    }
    T.build(a, 1, 1, n);
    for (int i = 1; i &lt;= m; i++) {
        int opt, l, r;
        scanf(&quot;%d%d%d&quot;, &amp;opt, &amp;l, &amp;r);
        if (opt == 0) {
            int w;
            scanf(&quot;%d&quot;, &amp;w);
            T.modify(l, r, w, 1, 1, n);
        } else if (opt == 1) {
            printf(&quot;%d\n&quot;, T.queryMax(l, r, 1, 1, n));
        } else {
            printf(&quot;%lld\n&quot;, T.querySum(l, r, 1, 1, n));
        }
    }
}
int main() {
    int T;
    scanf(&quot;%d&quot;, &amp;T);
    for (int cs = 1; cs &lt;= T; cs++) {
        solve();
    }
    return 0;
}</code></pre><p><p></p></div></div></div></p><h2>线段树合并</h2><p><div class="panel panel-default collapse-panel box-shadow-wrap-lg"><div class="panel-heading panel-collapse" data-toggle="collapse" data-target="#collapse-6d4f44a0f9942aa97ee2e38970fab02213" aria-expanded="true"><div class="accordion-toggle"><span style="">洛谷 P4556</span>
<i class="pull-right fontello icon-fw fontello-angle-right"></i>
</div>
</div>
<div class="panel-body collapse-panel-body">
<div id="collapse-6d4f44a0f9942aa97ee2e38970fab02213" class="collapse collapse-content"><p></p></p><pre><code class="lang-cpp">#include &lt;bits/stdc++.h&gt;
#define lson ls[u], l, mid
#define rson rs[u], mid + 1, r

const int N = 1e5 + 5;
int n, m, fa[N], dep[N], siz[N], son[N], top[N], rt[N], ans[N];
std::vector&lt;int&gt; E[N];

struct Segment {
    const static int N = 1e7 + 5;
    int id, ls[N], rs[N];
    std::pair&lt;int, int&gt; val[N];
    void pushUp(int u) {
        val[u] = std::max(val[ls[u]], val[rs[u]]);
    }
    void modify(int x, int w, int &amp;u, int l, int r) {
        if (u == 0) {
            u = ++id;
        }
        if (l == r) {
            val[u].first += w;
            val[u].second = -l;
            return;
        }
        int mid = (l + r) &gt;&gt; 1;
        if (x &lt;= mid) {
            modify(x, w, lson);
        } else {
            modify(x, w, rson);
        }
        pushUp(u);
    }
    int merge(int u, int v, int l, int r) {
        if (!u || !v) {
            return u + v;
        }
        if (l == r) {
            val[u].first += val[v].first;
            return u;
        }
        int mid = (l + r) &gt;&gt; 1;
        ls[u] = merge(ls[u], ls[v], l, mid);
        rs[u] = merge(rs[u], rs[v], mid + 1, r);
        pushUp(u);
        return u;
    }
} T;

void dfs1(int u, int p) {
    dep[u] = dep[p] + 1;
    fa[u] = p;
    siz[u] = 1;
    for (auto v : E[u]) {
        if (v != p) {
            dfs1(v, u);
            siz[u] += siz[v];
            if (siz[v] &gt; siz[son[u]]) {
                son[u] = v;
            }
        }
    }
}
void dfs2(int u, int from) {
    top[u] = from;
    if (son[u]) {
        dfs2(son[u], from);
    }
    for (auto v : E[u]) {
        if (v != fa[u] &amp;&amp; v != son[u]) {
            dfs2(v, v);
        }
    }
}
int lca(int u, int v) {
    for (; top[u] != top[v]; ) {
        if (dep[top[u]] &lt; dep[top[v]]) {
            std::swap(u, v);
        }
        u = fa[top[u]];
    }
    return dep[u] &lt; dep[v] ? u : v;
}
void solve(int u) {
    for (auto v : E[u]) {
        if (v != fa[u]) {
            solve(v);
            rt[u] = T.merge(rt[u], rt[v], 0, N - 5);
        }
    }
    ans[u] = -T.val[rt[u]].second;
}
int main() {
    scanf(&quot;%d%d&quot;, &amp;n, &amp;m);
    for (int i = 1; i &lt; n; i++) {
        int u, v;
        scanf(&quot;%d%d&quot;, &amp;u, &amp;v);
        E[u].push_back(v);
        E[v].push_back(u);
    }
    dfs1(1, 0);
    dfs2(1, 1);
    for (int i = 1; i &lt;= m; i++) {
        int u, v, w;
        scanf(&quot;%d%d%d&quot;, &amp;u, &amp;v, &amp;w);
        int x = lca(u, v);
        T.modify(w, 1, rt[u], 0, N - 5);
        T.modify(w, 1, rt[v], 0, N - 5);
        T.modify(w, -1, rt[x], 0, N - 5);
        if (fa[x]) {
            T.modify(w, -1, rt[fa[x]], 0, N - 5);
        }
    }
    solve(1);
    for (int i = 1; i &lt;= n; i++) {
        printf(&quot;%d\n&quot;, ans[i]);
    }
    return 0;
}</code></pre><p><p></p></div></div></div></p><h2>FFT</h2><p><div class="panel panel-default collapse-panel box-shadow-wrap-lg"><div class="panel-heading panel-collapse" data-toggle="collapse" data-target="#collapse-97b0ee4432941136752947a0026f85e268" aria-expanded="true"><div class="accordion-toggle"><span style="">LOJ 108</span>
<i class="pull-right fontello icon-fw fontello-angle-right"></i>
</div>
</div>
<div class="panel-body collapse-panel-body">
<div id="collapse-97b0ee4432941136752947a0026f85e268" class="collapse collapse-content"><p></p></p><pre><code class="lang-cpp">#include &lt;bits/stdc++.h&gt;
typedef unsigned int uint;
typedef unsigned long long uint64;

const uint MOD = 998244353, G = 3;

inline uint norm(const uint x) {
    return x &lt; MOD ? x : x - MOD;
}
struct Z {
    uint v;
    Z(uint v = 0) : v(v) {}
};
inline Z operator+(const Z a, const Z b) {
    return norm(a.v + b.v);
}
inline Z operator-(const Z a, const Z b) {
    return norm(a.v + MOD - b.v);
}
inline Z operator-(const Z a) {
    return a.v ? MOD - a.v : 0;
}
inline Z operator*(const Z a, const Z b) {
    return static_cast&lt;uint64&gt;(a.v) * b.v % MOD;
}
inline Z &amp;operator+=(Z &amp;a, const Z b) {
    return a = a + b;
}
inline Z &amp;operator-=(Z &amp;a, const Z b) {
    return a = a - b;
}
inline Z &amp;operator*=(Z &amp;a, const Z b) {
    return a = a * b;
}
Z power(Z x, int k) {
    Z ans = 1;
    for (; k &gt; 0; k &gt;&gt;= 1, x *= x) {
        if (k &amp; 1) {
            ans *= x;
        }
    }
    return ans;
}
Z inver(Z x) {
    return power(x, MOD - 2);
}
void ntt(Z *a, int k) {
    int n = 1 &lt;&lt; k;
    std::vector&lt;int&gt; rev(n, 0);
    for (int i = 0; i &lt; n; i++) {
        rev[i] = rev[i &gt;&gt; 1] &gt;&gt; 1 | (i &amp; 1) &lt;&lt; (k - 1);
        if (i &lt; rev[i]) {
            std::swap(a[i], a[rev[i]]);
        }
    }
    for (int l = 1; l &lt; n; l &lt;&lt;= 1) {
        Z w = power(G, (MOD - 1) / (l &lt;&lt; 1));
        for (int i = 0; i &lt; n; i += (l &lt;&lt; 1)) {
            Z *p = a + i, *q = a + i + l, wk = 1;
            for (int j = 0; j &lt; l; j++, wk *= w) {
                Z tmp = wk * *q;
                *q++ = *p - tmp;
                *p++ += tmp;
            }
        }
    }
}
typedef std::vector&lt;Z&gt; Poly;
void dft(Poly &amp;a, int k) {
    ntt(a.data(), k);
}
void idft(Poly &amp;a, int k) {
    ntt(a.data(), k);
    std::reverse(a.data() + 1, a.data() + (1 &lt;&lt; k));
    Z inv = inver(1 &lt;&lt; k);
    for (auto &amp;x : a) {
        x *= inv;
    }
}
Poly mul(Poly a, Poly b) {
    int org = (int)a.size() + b.size() - 1, k = 0;
    for (; (1 &lt;&lt; k) &lt; org; k++);
    int n = 1 &lt;&lt; k;
    a.resize(n, 0);
    b.resize(n, 0);
    dft(a, k);
    dft(b, k);
    for (int i = 0; i &lt; n; i++) {
        a[i] *= b[i];
    }
    idft(a, k);
    a.resize(org);
    return a;
}
int main() {
    int n, m;
    scanf(&quot;%d%d&quot;, &amp;n, &amp;m);
    Poly a(n + 1), b(m + 1);
    for (int i = 0; i &lt;= n; i++) {
        scanf(&quot;%u&quot;, &amp;a[i].v);
    }
    for (int i = 0; i &lt;= m; i++) {
        scanf(&quot;%u&quot;, &amp;b[i].v);
    }
    a = mul(a, b);
    for (int i = 0; i &lt;= n + m; i++) {
        printf(&quot;%u%c&quot;, a[i].v, &quot; \n&quot;[i == n + m]);
    }
    return 0;
}</code></pre><p><p></p></div></div></div></p><h2>FWT</h2><p><div class="panel panel-default collapse-panel box-shadow-wrap-lg"><div class="panel-heading panel-collapse" data-toggle="collapse" data-target="#collapse-6bc2052fcfade453b202d52e56bea2c278" aria-expanded="true"><div class="accordion-toggle"><span style="">洛谷 P4717</span>
<i class="pull-right fontello icon-fw fontello-angle-right"></i>
</div>
</div>
<div class="panel-body collapse-panel-body">
<div id="collapse-6bc2052fcfade453b202d52e56bea2c278" class="collapse collapse-content"><p></p></p><pre><code class="lang-cpp">#include &lt;bits/stdc++.h&gt;
typedef unsigned int uint;
typedef unsigned long long uint64;

const uint MOD = 998244353, G = 3;

inline uint norm(const uint x) {
    return x &lt; MOD ? x : x - MOD;
}
struct Z {
    uint v;
    Z(uint v = 0) : v(v) {}
};
inline Z operator+(const Z a, const Z b) {
    return norm(a.v + b.v);
}
inline Z operator-(const Z a, const Z b) {
    return norm(a.v + MOD - b.v);
}
inline Z operator-(const Z a) {
    return a.v ? MOD - a.v : 0;
}
inline Z operator*(const Z a, const Z b) {
    return static_cast&lt;uint64&gt;(a.v) * b.v % MOD;
}
inline Z &amp;operator+=(Z &amp;a, const Z b) {
    return a = a + b;
}
inline Z &amp;operator-=(Z &amp;a, const Z b) {
    return a = a - b;
}
inline Z &amp;operator*=(Z &amp;a, const Z b) {
    return a = a * b;
}
typedef std::vector&lt;Z&gt; Poly;
Poly operator|(Poly a, Poly b) {
    int n = a.size();
    for (int l = 1; l &lt; n; l &lt;&lt;= 1) {
        for (int i = 0; i &lt; n; i += (l &lt;&lt; 1)) {
            Z *p = a.data() + i, *q = a.data() + i + l;
            Z *u = b.data() + i, *v = b.data() + i + l;
            for (int j = 0; j &lt; l; j++) {
                *q++ += *p++;
                *v++ += *u++;
            }
        }
    }
    for (int i = 0; i &lt; n; i++) {
        a[i] *= b[i];
    }
    for (int l = 1; l &lt; n; l &lt;&lt;= 1) {
        for (int i = 0; i &lt; n; i += (l &lt;&lt; 1)) {
            Z *p = a.data() + i, *q = a.data() + i + l;
            for (int j = 0; j &lt; l; j++) {
                *q++ -= *p++;
            }
        }
    }
    return a;
}
Poly operator&amp;(Poly a, Poly b) {
    int n = a.size();
    for (int l = 1; l &lt; n; l &lt;&lt;= 1) {
        for (int i = 0; i &lt; n; i += (l &lt;&lt; 1)) {
            Z *p = a.data() + i, *q = a.data() + i + l;
            Z *u = b.data() + i, *v = b.data() + i + l;
            for (int j = 0; j &lt; l; j++) {
                *p++ += *q++;
                *u++ += *v++;
            }
        }
    }
    for (int i = 0; i &lt; n; i++) {
        a[i] *= b[i];
    }
    for (int l = 1; l &lt; n; l &lt;&lt;= 1) {
        for (int i = 0; i &lt; n; i += (l &lt;&lt; 1)) {
            Z *p = a.data() + i, *q = a.data() + i + l;
            for (int j = 0; j &lt; l; j++) {
                *p++ -= *q++;
            }
        }
    }
    return a;
}
Poly operator^(Poly a, Poly b) {
    int n = a.size();
    for (int l = 1; l &lt; n; l &lt;&lt;= 1) {
        for (int i = 0; i &lt; n; i += (l &lt;&lt; 1)) {
            Z *p = a.data() + i, *q = a.data() + i + l;
            Z *u = b.data() + i, *v = b.data() + i + l;
            for (int j = 0; j &lt; l; j++) {
                Z tmp = *q;
                *q++ -= *p;
                *p++ += tmp;
                tmp = *v;
                *v++ -= *u;
                *u++ += tmp;
            }
        }
    }
    for (int i = 0; i &lt; n; i++) {
        a[i] *= b[i];
    }
    const static uint I2 = (MOD + 1) / 2;
    for (int l = 1; l &lt; n; l &lt;&lt;= 1) {
        for (int i = 0; i &lt; n; i += (l &lt;&lt; 1)) {
            Z *p = a.data() + i, *q = a.data() + i + l;
            for (int j = 0; j &lt; l; j++) {
                Z x = *p, y = *q;
                *p++ = (x + y) * I2;
                *q++ = (x - y) * I2;
            }
        }
    }
    return a;
}
int main() {
    int n;
    scanf(&quot;%d&quot;, &amp;n);
    n = 1 &lt;&lt; n;
    Poly a(n), b(n);
    for (int i = 0; i &lt; n; i++) {
        scanf(&quot;%u&quot;, &amp;a[i].v);
    }
    for (int i = 0; i &lt; n; i++) {
        scanf(&quot;%u&quot;, &amp;b[i].v);
    }
    Poly f = a | b;
    for (int i = 0; i &lt; n; i++) {
        printf(&quot;%u%c&quot;, f[i].v, &quot; \n&quot;[i == n - 1]);
    }
    f = a &amp; b;
    for (int i = 0; i &lt; n; i++) {
        printf(&quot;%u%c&quot;, f[i].v, &quot; \n&quot;[i == n - 1]);
    }
    f = a ^ b;
    for (int i = 0; i &lt; n; i++) {
        printf(&quot;%u%c&quot;, f[i].v, &quot; \n&quot;[i == n - 1]);
    }
    return 0;
}</code></pre><p><p></p></div></div></div></p><h2>SAM</h2><p><div class="panel panel-default collapse-panel box-shadow-wrap-lg"><div class="panel-heading panel-collapse" data-toggle="collapse" data-target="#collapse-cc2e928152c5a0a2b26a574009ec9be255" aria-expanded="true"><div class="accordion-toggle"><span style="">洛谷 P3804</span>
<i class="pull-right fontello icon-fw fontello-angle-right"></i>
</div>
</div>
<div class="panel-body collapse-panel-body">
<div id="collapse-cc2e928152c5a0a2b26a574009ec9be255" class="collapse collapse-content"><p></p></p><pre><code class="lang-cpp">#include &lt;bits/stdc++.h&gt;
typedef long long int64;

const int N = 1e6 + 5;
char str[N];
struct SAM {
    const static int N = 2e6 + 6, S = 26;
    int tot, lst, len[N], lnk[N], siz[N], nxt[N][S];
    SAM() {
        tot = lst = 1;
    }
    void extend(int x) {
        int u = ++tot, p = lst;
        len[u] = len[p] + 1;
        siz[u] = 1;
        for (; p &gt; 0 &amp;&amp; !nxt[p][x]; ) {
            nxt[p][x] = u;
            p = lnk[p];
        }
        if (!p) {
            lnk[u] = 1;
        } else {
            int q = nxt[p][x];
            if (len[q] == len[p] + 1) {
                lnk[u] = q;
            } else {
                int c = ++tot;
                lnk[c] = lnk[q];
                len[c] = len[p] + 1;
                memcpy(nxt[c], nxt[q], sizeof(nxt[q]));
                for (; p &gt; 0 &amp;&amp; nxt[p][x] == q; ) {
                    nxt[p][x] = c;
                    p = lnk[p];
                }
                lnk[u] = lnk[q] = c;
            }
        }
        lst = u;
    }
    int64 solve(int n) {
        static int buc[N], t[N];
        for (int i = 2; i &lt;= tot; i++) {
            buc[len[i]]++;
        }
        std::partial_sum(buc + 1, buc + n + 1, buc + 1);
        for (int i = 2; i &lt;= tot; i++) {
            t[buc[len[i]]--] = i;
        }
        for (int i = tot - 1; i &gt;= 1; i--) {
            siz[lnk[t[i]]] += siz[t[i]];
        }
        int64 ans = 0;
        for (int i = 2; i &lt;= tot; i++) {
            if (siz[i] &gt; 1) {
                ans = std::max(ans, (int64)siz[i] * len[i]);
            }
        }
        return ans;
    }
} S;

int main() {
    scanf(&quot;%s&quot;, str + 1);
    int n = strlen(str + 1);
    for (int i = 1; i &lt;= n; i++) {
        S.extend(str[i] - &#039;a&#039;);
    }
    printf(&quot;%lld\n&quot;, S.solve(n));
    return 0;
}</code></pre><p><p></p></div></div></div></p><h2>后缀数组</h2><p><div class="panel panel-default collapse-panel box-shadow-wrap-lg"><div class="panel-heading panel-collapse" data-toggle="collapse" data-target="#collapse-2b2103e8a600cca01b28d4b30ad7d22f80" aria-expanded="true"><div class="accordion-toggle"><span style="">洛谷 P3809</span>
<i class="pull-right fontello icon-fw fontello-angle-right"></i>
</div>
</div>
<div class="panel-body collapse-panel-body">
<div id="collapse-2b2103e8a600cca01b28d4b30ad7d22f80" class="collapse collapse-content"><p></p></p><pre><code class="lang-cpp">#include &lt;bits/stdc++.h&gt;

const int N = 1e6 + 5;
int n, sa[N], rk[N], old[N * 2], cnt[N];
char str[N];

int main() {
    scanf(&quot;%s&quot;, str + 1);
    n = strlen(str + 1);
    int m = 300;
    for (int i = 1; i &lt;= n; i++) {
        cnt[rk[i] = str[i]]++;
    }
    std::partial_sum(cnt + 1, cnt + m + 1, cnt + 1);
    for (int i = n; i &gt;= 1; i--) {
        sa[cnt[rk[i]]--] = i;
    }
    for (int l = 1, p; ; l &lt;&lt;= 1, m = p) {
        int idx = 0;
        static int id[N], tmp[N];
        for (int i = n; i &gt; n - l; i--) {
            id[++idx] = i;
        }
        for (int i = 1; i &lt;= n; i++) {
            if (sa[i] &gt; l) {
                id[++idx] = sa[i] - l;
            }
        }
        std::fill(cnt + 1, cnt + m + 1, 0);
        for (int i = 1; i &lt;= n; i++) {
            cnt[tmp[i] = rk[id[i]]]++;
        }
        std::partial_sum(cnt + 1, cnt + m + 1, cnt + 1);
        for (int i = n; i &gt;= 1; i--) {
            sa[cnt[tmp[i]]--] = id[i];
        }
        std::copy(rk + 1, rk + n + 1, old + 1);
        auto equal = [&amp;](int x, int y, int l) {
            return old[x] == old[y] &amp;&amp; old[x + l] == old[y + l];
        };
        rk[sa[1]] = p = 1;
        for (int i = 2; i &lt;= n; i++) {
            rk[sa[i]] = equal(sa[i - 1], sa[i], l) ? p : ++p;
        }
        if (p == n) {
            for (int i = 1; i &lt;= n; i++) {
                sa[rk[i]] = i;
            }
            break;
        }
    }
    for (int i = 1; i &lt;= n; i++) {
        printf(&quot;%d%c&quot;, sa[i], &quot; \n&quot;[i == n]);
    }
    return 0;
}</code></pre><p><p></p></div></div></div></p>

[数据删除] 2021 算法模板复习！

Link Cut Tree

Min_25 筛

Matrix Tree 定理

平面最近点对

Manacher

可持久化并查集

Segment Tree Beats

线段树合并

FFT

FWT

SAM

后缀数组

44 条评论

发表评论取消回复
使用 Cookie 技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款。

ZJOI 2019 游记

「Project Euler 427」n-sequence

[数据删除] 2021 算法模板复习！

关于这个博客

「算法笔记」组合数学

「算法笔记」FHQ-Treap

「2019 Multi-University Training Contest 1」Sequence

「GXOI / GZOI 2019」与或和

「ARC 103C」Tr/ee

「POJ 3693」Maximum Repetition Substring

[数据删除] 2021 算法模板复习！

Link Cut Tree

Min_25 筛

Matrix Tree 定理

平面最近点对

Manacher

可持久化并查集

Segment Tree Beats

线段树合并

FFT

FWT

SAM

后缀数组

44 条评论

发表评论 取消回复 使用 Cookie 技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款。

[数据删除] 2021 算法模板复习！

发表评论取消回复
使用 Cookie 技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款。