由于牛客的渲染问题，你可以点此链接进入我的博客查看

A 小L的三角尺

因为斜边长度 关于 是一个凸函数，所以我们贪心选择当前能够带来最大斜边长度减少量的尺子进行打磨。我们用一个优先队列来维护打磨 单位后斜边长度减少最多的三角形。

当 很大但是 很小的时候可能会有精度问题，所以我们把分子有理化，这样分母会变成两者之和，就不会因减法而产生精度问题。

struct Node {
    ld val, nxt;
    int idx;

    bool operator<(const Node other) const {
        return val < other.val;
    }
};

void solve() {
    int n, w;
    cin >> n >> w;
    vector<ll> a(n), b(n), cur(n);
    vector<ld> h(n);
    priority_queue<Node> pq;
    for (int i = 0; i < n; ++i) {
        cin >> a[i] >> b[i];
        h[i] = sqrt(1.0l * a[i] * a[i] + 1.0l * b[i] * b[i]);
        if (b[i] > 0) {
            ld nxt = sqrt(1.0l * a[i] * a[i] + 1.0l * (b[i] - 1) * (b[i] - 1));
            ld gain = 1.0l * (2 * b[i] - 1) / (h[i] + nxt);
            pq.push({gain, nxt, i});
        }
    }
    while (w > 0 && !pq.empty()) {
        auto u = pq.top();
        pq.pop();
        int i = u.idx;
        cur[i]++;
        w--;
        h[i] = u.nxt;

        ll rem = b[i] - cur[i];
        if (rem > 0) {
            ld nxt = sqrt(1.0l * a[i] * a[i] + 1.0l * (rem - 1) * (rem - 1));
            ld gain = 1.0l * (2 * rem - 1) / (h[i] + nxt);
            pq.push({gain, nxt, i});
        }
    }

    ld sum = 0;
    for (int i = 0; i < n; ++i) {
        sum += sqrt(1.0l * a[i] * a[i] + 1.0l * (b[i] - cur[i]) * (b[i] - cur[i]));
    }
    cout << sum << endl;
}

B 小L的彩球

我们把彩球的放置情况记为一个 序列，相邻不同的对数就等于段数（ 段和 段的个数之和） 。若段数为 。若首位为 ，则 的段数为 ， 的段数为 ；首位为 则相反。把 个 分成 段（每段至少 个）的方案数为 ，计算一下即可。

void solve() {
    int n, x, t;
    cin >> n >> x >> t;
    int r = t + 1;
    if (r > n) {
        cout << 0 << endl;
        return;
    }
    auto calc = [&](int m, int r) -> Z {
        if (r == 0)
            return (m == 0) ? 1 : 0;
        if (m < r)
            return 0;
        return C.C(m - 1, r - 1);
    };
    Z ans = 0;
    cout << calc(x, (r + 1) / 2) * calc(n - x, r - (r + 1) / 2) + calc(n - x, (r + 1) / 2) * calc(x, r - (r + 1) / 2) << endl;
}

C 小L的线段树

如果直接模拟题目描述的递归过程，当大量上层节点被毁坏时，查询可能会退化到访问大量底层节点，导致超时。所以我们可以为每个节点维护一个值 ，表示当该节点被查询区间完全包含时，该子树产生的总代价。

• 初始状态：所有节点未被毁坏，（因为一旦遇到该节点，计数 并停止）。

• 节点 被毁坏后：该节点不再提供“阻断”作用，查询会穿透它到达子节点。因此，此时 变为其左右子节点 之和，即 。

• 查询：

  • 当查询区间完全包含当前节点 时，直接返回 。这利用了预处理的值，避免了深入遍历已毁坏节点的子树。
  • 当部分包含时，按照题目：。

• 更新：

  • 当摧毁一个节点 u 时，将其标记为毁坏，并更新 。
  • 该节点的改变可能会影响其已毁坏的父节点的 值。因为如果父节点也是毁坏的，父节点的 依赖于子节点的 。因此，在递归回溯的过程中，我们需要更新路径上所有已毁坏节点的 值。

void solve() {
    int n;
    cin >> n;
    int N = 4 * n + 5;
    vector<bool> flg(N);
    vector<int> val(N);
    function<void(int, int, int)> build = [&](int x, int l, int r) {
        val[x] = 1;
        flg[x] = 0;
        if (l == r)
            return;
        int mid = (l + r) >> 1;
        build(2 * x, l, mid);
        build(2 * x + 1, mid + 1, r);
    };

    build(1, 1, n);

    function<void(int, int, int, int, int)> update = [&](int x, int l, int r, int ql, int qr) {
        if (l == ql && r == qr) {
            if (!flg[x]) {
                flg[x] = true;
                val[x] = val[2 * x] + val[2 * x + 1];
            }
            return;
        }

        int mid = (l + r) >> 1;
        if (qr <= mid)
            update(2 * x, l, mid, ql, qr);
        else
            update(2 * x + 1, mid + 1, r, ql, qr);

        if (flg[x]) {
            val[x] = val[2 * x] + val[2 * x + 1];
        }
    };

    function<int(int, int, int, int, int)> ask = [&](int x, int l, int r, int ql, int qr) {
        if (ql <= l && r <= qr) {
            return val[x];
        }

        int res = flg[x] ? 0 : 1;
        int mid = (l + r) >> 1;
        if (ql <= mid)
            res += ask(2 * x, l, mid, ql, qr);
        if (qr > mid)
            res += ask(2 * x + 1, mid + 1, r, ql, qr);
        return res;
    };

    for (int i = 0; i < n; ++i) {
        int op, l, r;
        cin >> op >> l >> r;
        if (op == 1) {
            update(1, 1, n, l, r);
        } else {
            cout << ask(1, 1, n, l, r) << "\n";
        }
    }
}

D 小L的扩展

可以转化为求图中所有节点被感染的最短时间。每个格子看作一个节点，相邻格子之间有边。黑色从格子 扩散到相邻格子 需要 个单位时间。

• 如果 是普通白格子，它被染黑的时间是 。
• 如果 是蓝格子，它在时刻 之前不能被染黑。因此，它被染黑的时间至少是 。

综合来看，从邻居 扩散到 的时间为 。使用 求解即可。

constexpr ll INF = 4e18;

int dx[] = {-1, 1, 0, 0}, dy[] = {0, 0, -1, 1};

void solve() {
    int n, m, a, b;
    cin >> n >> m >> a >> b;

    int N = n * m;
    vector<ll> T(N), dist(N, INF);

    priority_queue<PLL> pq;

    auto id = [&](int x, int y) {
        return x * m + y;
    };

    for (int i = 0; i < a; ++i) {
        int x, y;
        cin >> x >> y;
        x--, y--;
        dist[id(x, y)] = 0;
        pq.push({0, id(x, y)});
    }

    for (int i = 0; i < b; ++i) {
        int x, y, t;
        cin >> x >> y >> t;
        x--, y--;
        T[id(x, y)] = t;
    }

    auto check = [&](int x, int y) {
        return 0 <= x && x < n && 0 <= y && y < m;
    };

    while (pq.size()) {
        auto [d, u] = pq.top();
        pq.pop();
        d = -d;
        if (d > dist[u])
            continue;

        int x = u / m, y = u % m;

        for (int i = 0; i < 4; ++i) {
            int nx = x + dx[i], ny = y + dy[i];

            if (check(nx, ny)) {
                int v = id(nx, ny);

                ll time = max(d + 1, T[v]);

                if (time < dist[v]) {
                    dist[v] = time;
                    pq.push({-time, v});
                }
            }
        }
    }

    ll ans = 0;
    for (int i = 0; i < N; ++i) {
        ans = max(ans, dist[i]);
    }

    cout << ans << endl;
}

E 小L的空投

题目中水位 随天数增加而严格单调递增，这意味着随着时间推移，越来越多的城市被淹没（从图中移除）。但是在图中删除节点并维护连通块是比较复杂的操作。不过如果我们从第 天倒着处理到第 天，水位的变化就变成了从高到低。这意味着原本被淹没的城市会逐渐“浮出水面”（加入图中），我们可以用并查集来处理。

首先将所有城市按照高度 从大到小排序，将查询（每天的水位）存储下来。从第 天开始倒序循环到第 1 天。设当前天的水位为 。利用一个指针遍历排序后的城市数组，将所有高度 且尚未加入的城市激活：

• 初始化 的并查集（大小为 1），标记 为有效。
• 若 所在的连通块大小（初始为 1） ，则总空投数 。
• 遍历 的所有邻居 ，如果 也是有效的（即之前已经加入图中），则在并查集中合并 和 。

合并时，找到两个集合的根节点。合并前，如果某集合大小 ，说明它之前贡献了 1 个空投，合并后这个集合不再独立存在，需要先减去贡献。合并两个集合，更新大小。合并后，如果新集合大小 ，说明新连通块符合条件，增加贡献。

最后按顺序输出第 天到第 天的答案即可。

void solve() {
    int n, m, x, d;
    cin >> n >> m >> x >> d;

    vector<int> h(n + 1);
    for (int i = 1; i <= n; ++i) {
        cin >> h[i];
    }

    vector<vector<int>> g(n + 1);
    for (int i = 0; i < m; ++i) {
        int u, v;
        cin >> u >> v;
        g[u].pb(v);
        g[v].pb(u);
    }

    vector<int> H(x + 1);
    for (int i = 1; i <= x; ++i) {
        cin >> H[i];
    }

    vector<int> p(n);
    iota(all(p), 1);
    sort(all(p), [&](int a, int b) {
        return h[a] > h[b];
    });

    DSU dsu(n);
    vector<bool> f(n + 1);
    int cur = 0;
    vector<int> ans(x + 1);

    int ptr = 0;

    for (int i = x; i >= 1; --i) {
        int level = H[i];

        while (ptr < n && h[p[ptr]] > level) {
            int u = p[ptr];
            f[u] = 1;

            if (1 >= d)
                cur++;

            for (int v : g[u]) {
                if (f[v]) {
                    int ru = dsu.find(u), rv = dsu.find(v);

                    if (ru != rv) {
                        if (dsu.siz[ru] >= d)
                            cur--;
                        if (dsu.siz[rv] >= d)
                            cur--;

                        dsu.merge(ru, rv);

                        if (dsu.siz[ru] >= d)
                            cur++;
                    }
                }
            }
            ptr++;
        }
        ans[i] = cur;
    }

    for (int i = 1; i <= x; ++i) {
        cout << ans[i] << endl;
    }
}

F 小L的极大团

根据期望的线性性，总期望等于所有可能的顶点子集成为极大团的概率之和， 。

由于图中的顶点是等价的，对于大小相同的子集，它们成为极大团的概率是相同的。因此我们可以枚举子集的大小 ：

极大团的连通性我们不用考虑，极大性我们可以使用容斥原理来处理。设 为 内部的边数， 为图中总的可选的边数。我们需要从 条边中选 条。

对于外部的 个顶点，设属性 表示“外部顶点 与 中的所有顶点相连”。我们要计算的是没有任何一个外部顶点满足 的方案数，根据容斥原理：

当固定 个外部点与 全连时，我们需要强制选中的边数 ​ 为：

• 内部的边：
• 个外部点与 的连边：

如果 ，则方案数为 。否则，剩下的边可以从 条边中任选 条，方案数为 。

因此，固定集合 成为极大团的概率为：

把这个公式带入总期望公式：

其中 可以化简为为 。

但是由于 非常大，我们的组合数学模板肯定不能预处理这么大的数字，但是 ，我们只需要计算 的下降 阶乘的逆元即可。

void solve() {
    int n, k;
    cin >> n >> k;
    Z m = Z(n) * (n - 1) / 2;
    vector<Z> prod(k + 1), inv(k + 1);
    prod[0] = 1;
    for (int i = 0; i < k; ++i) {
        prod[i + 1] = prod[i] * (m - i);
    }

    inv[k] = prod[k].inv();

    for (int i = k - 1; i >= 0; --i) {
        inv[i] = inv[i + 1] * (m - i);
    }

    Z ans = 0;

    for (int s = 1; s <= n; ++s) {
        ll e = 1ll * s * (s - 1) / 2;
        if (e > k)
            break;
        Z sum = 0;

        int mx = min((int)(k - e) / s, n - s);

        for (int j = 0; j <= mx; ++j) {
            int L = e + j * s;

            Z t = C.C(n - s, j);
            if (j & 1)
                t = -t;

            sum += t * C.A(k, L) * inv[L];
        }

        ans += C.C(n, s) * sum;
    }

    cout << ans << endl;
}

G 小L的散步

将所有缝隙的位置记为前缀和数组 （第 个缝隙位置为 ，包含最后一个石块的右端点）。小L每次站位（初始位置和每一步走完后）记录脚后跟位置 ，脚掌覆盖严格区间 （边界不算踩中）。只要存在 中的某个元素满足 ，就踩中缝隙。

因为 单调递增，对每个 二分找到第一个 ，若它存在且 则判为踩中。

void solve() {
    int n, m, l;
    cin >> n >> m >> l;
    vector<int> a(n), b(m);
    vector<ll> S;
    ll sum = 0;
    for (int i = 0; i < n; ++i)
        cin >> a[i], sum += a[i], S.pb(sum);
    for (int i = 0; i < m; ++i)
        cin >> b[i];
    auto check = [&](ll p) -> bool {
        auto it = upper_bound(all(S), p);
        if (it == S.end())
            return 0;
        return *it < p + l;
    };
    ll pos = 0;
    if (check(pos)) {
        cout << "YES" << endl;
        return;
    }
    for (int i = 0; i < m; ++i) {
        pos += b[i];
        if (check(pos)) {
            cout << "YES" << endl;
            return;
        }
    }
    cout << "NO" << endl;
}

H 小L的数组

我们用 表示当前可能出现的数字的集合，初始 。然后我们根据两种操作： 和 来更新数字集合即可。

void solve() {
    int n;
    cin >> n;
    vector<int> a(n), b(n);
    for (int i = 0; i < n; ++i)
        cin >> a[i];
    for (int i = 0; i < n; ++i)
        cin >> b[i];
    array<bool, 2048> dp{}, ndp{};
    dp[0] = 1;
    for (int i = 0; i < n; ++i) {
        fill(all(ndp), 0);
        int ai = a[i], bi = b[i];
        for (int x = 0; x < 2048; ++x) {
            if (!dp[x])
                continue;
            int y1 = max(0, x - a[i]);
            ndp[y1] = 1;
            int y2 = x ^ b[i];
            ndp[y2] = 1;
        }
        dp.swap(ndp);
    }
    int ans = 0;
    for (int x = 2047; x >= 0; --x) {
        if (dp[x]) {
            ans = x;
            break;
        }
    }
    cout << ans << endl;
}

I 小L的构造2

差点就写完了，这道题的原题我还写过题解的（CF Round 1065 Div3 D/E）。

我们把数字分成两类，一类是 和 的倍数，作为好数，另一类就是剩余的数，记为坏数。然后我们用 的倍数， 的倍数， 的倍数作为好数序列。为了保证 个里面有 组公因数大于 ，我们使用坏好好的方式构造整个序列即可。

void solve() {
    int n;
    cin >> n;
    if (n == 4) {
        cout << "3 4 2 1" << endl;
        return;
    }
    vector<int> b, g, s6, s3;
    for (int i = 1; i <= n; ++i) {
        if (i % 6 == 0)
            s6.eb(i);
        else if (i % 2 == 0)
            b.eb(i);
        else if (i % 3 == 0)
            s3.eb(i);
        else
            g.eb(i);
    }
    if (s6.empty())
        g.insert(all(g), s3.end());
    else {
        b.insert(b.end(), all(s6));
        b.insert(b.end(), all(s3));
    }
    if (g.size() > b.size() / 2 + 1) {
        cout << -1 << endl;
        return;
    }
    int j = 0;
    for (auto x : g) {
        cout << x << " ";
        for (int _ = 1; _ <= 2; ++_)
            if (j < b.size())
                cout << b[j++] << " ";
    }
    while (j < b.size())
        cout << b[j++] << " ";
}

J 小L的字符串

总代价为

第一部分 是常数，所以我们只需要计算有多少个 满足 即可。由于 为 数量级，所以我们考虑使用 实现。

• 我们把这个问题分解为枚举字符 ：对于所有 的位置，统计有多少个对应的 满足 。
• 令 为 中等于 的位置的指示向量（反转后）， 为 中小于 的位置的指示向量（扩展为 长度）。
• 它们的卷积结果的第 项即为移位 时的匹配数。
• 为了加速，我们利用累加性质： 。
• 我们倒序枚举字符 ，维护 的后缀和的频域形式，与 的频域形式相乘并累加，最后做一次逆 ​ 即可。

using cd = complex<double>;
const double PI = acos(-1);

void fft(vector<cd> &a, bool invert) {
    int n = a.size();

    for (int i = 1, j = 0; i < n; i++) {
        int bit = n >> 1;
        for (; j & bit; bit >>= 1)
            j ^= bit;
        j ^= bit;
        if (i < j)
            swap(a[i], a[j]);
    }

    for (int len = 2; len <= n; len <<= 1) {
        double ang = 2 * PI / len * (invert ? -1 : 1);
        cd wlen(cos(ang), sin(ang));
        for (int i = 0; i < n; i += len) {
            cd w(1);
            for (int j = 0; j < len / 2; j++) {
                cd u = a[i + j], v = a[i + j + len / 2] * w;
                a[i + j] = u + v;
                a[i + j + len / 2] = u - v;
                w *= wlen;
            }
        }
    }

    if (invert) {
        for (cd &x : a)
            x /= n;
    }
}

void solve() {
    int n;
    string s, t;
    cin >> n >> s >> t;

    ll ss = 0, st = 0;
    for (auto v : s)
        ss += v - 'a';
    for (auto v : t)
        st += v - 'a';
    ll diff = st - ss;

    string rev = s;
    reverse(all(rev));

    string tt = t + t;

    int m = 1;
    while (m < n + 2 * n)
        m <<= 1;

    vector<cd> SumFA(m, 0), Res(m, 0), P(m), fac(m), fbc(m);

    for (int c = 25; c >= 0; c--) {
        fill(all(P), cd(0, 0));

        for (int i = 0; i < n; i++) {
            if (rev[i] - 'a' == c)
                P[i].real(1);
        }
        for (int i = 0; i < 2 * n; i++) {
            if (tt[i] - 'a' == c)
                P[i].imag(1);
        }

        fft(P, 0);

        for (int i = 0; i < m; i++) {
            int j = (m - i) & (m - 1);
            cd cp = conj(P[j]);
            fac[i] = (P[i] + cp) * 0.5;
            fbc[i] = (P[i] - cp) * cd(0, -0.5);

            Res[i] += SumFA[i] * fbc[i];

            SumFA[i] += fac[i];
        }
    }

    fft(Res, 1);

    ll mn = -1;

    for (int k = 0; k < n; k++) {
        ll count = (ll)(Res[n - 1 + k].real() + 0.5);

        ll cur = k + diff + 26 * count;

        if (mn == -1 || cur < mn) {
            mn = cur;
        }
    }

    cout << mn << endl;
}

K 小L的游戏1

我们先除去两个人各动一次的组 ，剩余部分如果为 就是在最后一组行动中 加完了，否则检查一下剩余部分是否 即可。

void solve() {
    ll m, n, z;
    cin >> m >> n >> z;
    ll x = z / (m + n) * (m + n);
    if (x == z) {
        cout << 1;
    } else {
        if (x + m >= z)
            cout << 0;
        else
            cout << 1;
    }
}

L 小L的游戏2

令 为在小L回合且当前值为 时，最终最后一次操作由小L完成的概率。按照定义推导并消元（消掉对手）后得到：

其中 。

我们令 ，那么在 时，这个式子为齐次常系数递推，没有边界吸收项。把它写成伴随矩阵 ，满足

其中 。

所以我们先直接 求出 在 的值。已知 后，要得到 只需计算 （矩阵快速幂）。答案就是结果向量的第一个分量。

void solve() {
    int m1, m2, n1, n2;
    ll z;
    cin >> m1 >> m2 >> n1 >> n2 >> z;
    Z p1, q1;
    cin >> p1 >> q1;
    Z p0 = 1 - p1, q0 = 1 - q1;
    int D = max({m1 + n1, m1 + n2, m2 + n1, m2 + n2});
    vector<Z> c(D + 1);
    c[m1 + n1] += p1 * q1;
    c[m1 + n2] += p1 * q0;
    c[m2 + n1] += p0 * q1;
    c[m2 + n2] += p0 * q0;
    vector<Z> L(D), R(D);
    ll st = z - D;
    for (ll x = z - 1; x >= st; --x) {
        int i = x - st;
        Z t1 = x + n1 < z ? L[x + n1 - st] : 0, t2 = x + n2 < z ? L[x + n2 - st] : 0;
        R[i] = q1 * t1 + q0 * t2;
        t1 = x + m1 < z ? R[x + m1 - st] : 1, t2 = x + m2 < z ? R[x + m2 - st] : 1;
        L[i] = p1 * t1 + p0 * t2;
    }
    if (st <= 0) {
        cout << L[-st] << endl;
        return;
    }
    Matrix<Z> T(D, Z(0));
    for (int j = 0; j < D; ++j)
        T[0][j] = c[j + 1];
    for (int i = 1; i < D; ++i)
        T[i][i - 1] = Z(1);

    T = T.ksm(st);
    Matrix<Z> base(D, 1, Z(0));
    for (int i = 0; i < D; ++i)
        base[i][0] = L[i];

    T = T * base;
    cout << T[0][0] << endl;
}

头文件

#include <bits/stdc++.h>
#define pb push_back
#define pf push_front
#define pob pop_back
#define pof pop_front
#define eb emplace_back
#define fi first
#define se second
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define endl "\n"
using namespace std;

using ll = long long;
using ld = long double;
using ui = unsigned;
using ull = unsigned long long;
using i128 = __int128;
using PII = pair<int, int>;
using PLL = pair<ll, ll>;
using TIII = tuple<int, int, int>;
using TLLL = tuple<ll, ll, ll>;

void init() {
}

void solve() {
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    init();

    int t = 1;
    cin >> t;
    cout << fixed << setprecision(15);
    for (int _ = 1; _ <= t; ++_) {
        solve();
    }

    return 0;
}

自动取模

constexpr int MOD = 998244353;

template <class T>
constexpr T ksm(T a, ll b) {
    T res = 1;
    while (b) {
        if (b & 1)
            res *= a;
        b >>= 1;
        a *= a;
    }
    return res;
}

template <int P>
struct MInt {
    int x;
    constexpr MInt() : x() {}
    constexpr MInt(ll x) : x{norm(x % getMod())} {}
    static int Mod;
    constexpr static int getMod() {
        if (P > 0) {
            return P;
        } else {
            return Mod;
        }
    }
    constexpr static void setMod(int Mod_) {
        Mod = Mod_;
    }
    constexpr int norm(int x) const {
        if (x < 0) {
            x += getMod();
        }
        if (x >= getMod()) {
            x -= getMod();
        }
        return x;
    }
    constexpr int val() const {
        return x;
    }
    explicit constexpr operator int() const {
        return x;
    }
    constexpr MInt operator-() const {
        MInt res;
        res.x = norm(getMod() - x);
        return res;
    }
    constexpr MInt inv() const {
        assert(x != 0);
        return ksm(*this, getMod() - 2);
    }
    constexpr MInt &operator*=(MInt rhs) & {
        x = 1LL * x * rhs.x % getMod();
        return *this;
    }
    constexpr MInt &operator+=(MInt rhs) & {
        x = norm(x + rhs.x);
        return *this;
    }
    constexpr MInt &operator-=(MInt rhs) & {
        x = norm(x - rhs.x);
        return *this;
    }
    constexpr MInt &operator/=(MInt rhs) & {
        return *this *= rhs.inv();
    }
    friend constexpr MInt operator*(MInt lhs, MInt rhs) {
        MInt res = lhs;
        res *= rhs;
        return res;
    }
    friend constexpr MInt operator+(MInt lhs, MInt rhs) {
        MInt res = lhs;
        res += rhs;
        return res;
    }
    friend constexpr MInt operator-(MInt lhs, MInt rhs) {
        MInt res = lhs;
        res -= rhs;
        return res;
    }
    friend constexpr MInt operator/(MInt lhs, MInt rhs) {
        MInt res = lhs;
        res /= rhs;
        return res;
    }
    friend constexpr istream &operator>>(istream &is, MInt &a) {
        ll v;
        is >> v;
        a = MInt(v);
        return is;
    }
    friend constexpr ostream &operator<<(ostream &os, const MInt &a) {
        return os << a.val();
    }
    friend constexpr bool operator==(MInt lhs, MInt rhs) {
        return lhs.val() == rhs.val();
    }
    friend constexpr bool operator!=(MInt lhs, MInt rhs) {
        return lhs.val() != rhs.val();
    }
};

template <>
int MInt<0>::Mod = 998244353;

template <int V, int P>
constexpr MInt<P> CInv = MInt<P>(V).inv();

using Z = MInt<MOD>;

组合数学

struct Comb {
    int n;
    vector<Z> _fac, _inv;

    Comb() : n(0), _fac{1}, _inv{0} {}
    Comb(int n) : Comb() {
        init(n);
    }
    void init(int m) {
        if (m <= n)
            return;
        _fac.resize(m + 1);
        _inv.resize(m + 1);
        for (int i = n + 1; i <= m; i++) {
            _fac[i] = _fac[i - 1] * i;
        }
        _inv[m] = _fac[m].inv();
        for (int i = m; i > n; i--) {
            _inv[i - 1] = _inv[i] * i;
        }
        n = m;
    }
    Z fac(int x) {
        if (x > n)
            init(x);
        return _fac[x];
    }
    Z inv(int x) {
        if (x > n)
            init(x);
        return _inv[x];
    }
    Z C(int x, int y) {
        if (x < 0 || y < 0 || x < y)
            return 0;
        return fac(x) * inv(y) * inv(x - y);
    }
    Z A(int x, int y) {
        if (x < 0 || y < 0 || x < y)
            return 0;
        return fac(x) * inv(x - y);
    }
};

矩阵

template <class Int>
struct Matrix {
    int n, m;
    vector<vector<Int>> a;

    Matrix(int n = 0, int m = 0, Int val = Int())
        : n(n), m(m), a(n, vector<Int>(m, val)) {}

    static Matrix identity(int n) {
        Matrix I(n, n);
        for (int i = 0; i < n; i++)
            I.a[i][i] = Int(1);
        return I;
    }

    vector<Int> &operator[](int i) {
        return a[i];
    }
    const vector<Int> &operator[](int i) const {
        return a[i];
    }

    Matrix operator+(const Matrix &other) const {
        assert(n == other.n && m == other.m);
        Matrix res(n, m);
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++)
                res[i][j] = a[i][j] + other[i][j];
        return res;
    }

    Matrix operator-(const Matrix &other) const {
        assert(n == other.n && m == other.m);
        Matrix res(n, m);
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++)
                res[i][j] = a[i][j] - other[i][j];
        return res;
    }

    Matrix operator*(const Matrix &other) const {
        assert(m == other.n);
        Matrix res(n, other.m, Int(0));
        for (int i = 0; i < n; i++)
            for (int k = 0; k < m; k++)
                for (int j = 0; j < other.m; j++)
                    res[i][j] = res[i][j] + a[i][k] * other[k][j];
        return res;
    }

    Matrix operator*(const Int &k) const {
        Matrix res(n, m);
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++)
                res[i][j] = a[i][j] * k;
        return res;
    }

    Matrix transpose() const {
        Matrix res(m, n);
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++)
                res[j][i] = a[i][j];
        return res;
    }

    Matrix ksm(ll exp) const {
        assert(n == m);
        Matrix base = *this;
        Matrix res = identity(n);
        while (exp > 0) {
            if (exp & 1)
                res = res * base;
            base = base * base;
            exp >>= 1;
        }
        return res;
    }
};

template <class T>
T determinant(int n, Matrix<T> &mat) {
    T det(1, 0);
    int sign = 1;

    for (int i = 0; i < n; i++) {
        int pivot = i;
        while (pivot < n && mat[pivot][i].isZero())
            pivot++;
        if (pivot == n)
            return T();

        if (pivot != i) {
            swap(mat[i], mat[pivot]);
            sign = -sign;
        }

        det *= mat[i][i];
        for (int j = i + 1; j < n; j++) {
            if (!mat[j][i].isZero()) {
                T factor = mat[j][i] / mat[i][i];
                for (int k = i; k < n; k++) {
                    mat[j][k] -= factor * mat[i][k];
                }
            }
        }
    }

    if (sign == -1) {
        det = T() - det;
    }
    return det;
}

并查集

struct DSU {
    vector<int> f, siz;

    DSU() {}
    DSU(int n) {
        init(n);
    }

    void init(int n) {
        f.resize(n + 1);
        iota(f.begin(), f.end(), 0);
        siz.assign(n + 1, 1);
    }

    int find(int x) {
        return f[x] == x ? x : f[x] = find(f[x]);
    }

    void merge(int x, int y) {
        x = find(x), y = find(y);
        if (x == y)
            return;
        f[y] = x;
        siz[x] += siz[y];
    }

    bool same(int x, int y) {
        return find(x) == find(y);
    }

    int size(int x) {
        return siz[find(x)];
    }
};