别催了我真的咕了……

祝大家 [数据删除] 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 日 12 : 44 PM