ACM九月训练

发表于 2025-09-01 更新于 2025-09-25 分类于 ACM 阅读次数：本文字数： 71k

备战网络赛里！

ABC 421 E

题意

有五个骰子，每个骰子相同，六个面写着 $a_1,a_2,...,a_6$。求进行如下操作后期望的最大值：

投掷 6 个骰子，可以选择保留一些骰子
投掷未保留的骰子，可以选择保留一些骰子
再次骰子未保留的骰子
任意选定一个值 $X$，分数定义为 $nX$，$n$ 是五个骰子中 $X$ 的出现次数。

题解

考虑如何求期望，我们定义一个状态 $f(S,rem)$，$S$ 代表保留的骰子集合，$rem$ 代表剩余操作次数（初始为 3）。

定义 $sz = S.size()$，那么需要投掷的骰子数量为 $cnt = 5-sz$，我们求的期望就是 $\displaystyle \frac{\sum f(S^\prime, rem - 1)}{6^{cnt}}$，我们可以枚举接下来所有骰子的点数，以及每个骰子要不要重投，前者必须考虑所有情况，后者只需要选择最大值。

考虑记忆化搜索，我们枚举所有可能的投掷结果，对于每个结果，枚举所有可能选择保留的投掷，在所有选择中取最大值。

时间复杂度 $O(6^5\times 2^5)$，由于不是所有状态都有 5 个骰子需要重投，实际次数还会低一些。

#include <bits/stdc++.h>

#define int long long
using namespace std;

using i64 = long long;
using u64 = unsigned long long;
using u32 = unsigned;

using u128 = unsigned __int128;
using i128 = __int128;
using ld = long double;

signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    vector<int> a(6);
    for (int i = 0; i < 6; i++) {
        cin >> a[i];
    }
    map<pair<vector<int>, int>, ld> mp;
    auto dfs = [&](auto dfs, vector<int> v, int rem) -> ld {
        sort(v.begin(), v.end());
        if (mp.count({v, rem})) {
            return mp[{v, rem}];
        }
        if (rem == 0) {
            int mx = 0, ut = 0, sum = 0;
            for (auto x : v) {
                if (x != ut) {
                    sum = 0;
                }
                ut = x;
                sum += x;
                mx = max(mx, sum);
            }
            return mx;
        }
        int sz = v.size();
        int base = 1;
        for (int i = 0; i < 5 - sz; i++) {
            base *= 6;
        }
        ld sum = 0;
        int cnt = 5 - sz;
        for (int i = 0; i < base; i++) {
            vector<int> add;
            int sta = i;
            for (int j = 0; j < cnt; j++) {
                add.push_back(a[sta % 6]);
                sta /= 6;
            }
            ld mx = 0;
            for (int mask = 0; mask < (1ll << cnt); mask++) {
                vector<int> v2 = v;
                for (int j = 0; j < cnt; j++) {
                    if (mask >> j & 1) {
                        v2.push_back(add[j]);
                    }
                }
                mx = max(mx, dfs(dfs, v2, rem - 1));
            }
            sum += mx;
        }
        sum /= base;
        mp[{v, rem}] = sum;
        return sum;
    };
    cout << fixed << setprecision(10) << dfs(dfs, {}, 3) << "\n";

    return 0;
}

ABC 421 F

题意

$q$ 次操作，第 $i$ 次操作将 $i$ 插入到 $x$ 所在位置的后面，或者删除 $x,y$ 之间的元素（不含 $x,y$），输出这些元素的和。

$q\le 5\times 10^5$

题解

用一个链表模拟，删除时由于不知道 $x,y$ 相对位置关系，用两个指针分别从 $x,y$ 出发沿着链表一直走。

时间复杂度 $O(q)$

#include <bits/stdc++.h>

#define int long long
using namespace std;

using i64 = long long;
using u64 = unsigned long long;
using u32 = unsigned;

using u128 = unsigned __int128;
using i128 = __int128;
using ld = long double;

signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int q;
    cin >> q;
    vector<int> nxt(q + 1);
    nxt[0] = -1;
    for (int i = 1; i <= q; i++) {
        int op;
        cin >> op;
        if (op == 1) {
            int x;
            cin >> x;
            nxt[i] = nxt[x];
            nxt[x] = i;
        } else {
            int x, y;
            cin >> x >> y;
            int sx = 0, sy = 0;
            int xx = x, yy = y;
            while (true) {
                if (nxt[xx] != -1) {
                    xx = nxt[xx];
                    if (xx == y) {
                        cout << sx << "\n";
                        nxt[x] = y;
                        break;
                    } else {
                        sx += xx;
                    }
                }
                if (nxt[yy] != -1) {
                    yy = nxt[yy];
                    if (yy == x) {
                        cout << sy << "\n";
                        nxt[y] = x;
                        break;
                    } else {
                        sy += yy;
                    }
                }
            }
        }
    }

    return 0;
}

ABC 421 G

题意

给定一个序列 $a$，$m$ 种操作 $[l,r]$，每种操作都可以进行任意次，对区间 $[l,r]$ 加一，代价为 1。求是否能将序列变为非递减序列，如果可以，给出最小代价。

$n,m,a_i\le 300$

题解

区间加一想到差分数组，即令 $d_i = a_i - a_{i - 1}$，区间 $[l,r]$ 加一即 $d_l + 1, d_{r + 1} - 1$。转化为差分数组后，我们的问题就转化为能否通过操作将所有 $d_i$ 都变为大于等于 0。

我们可以建立等价的球盒模型，如果 $d_i \ge 0$，说明第 $i$ 个盒子有球，否则说明第 $i$ 个盒子需要 $-d_i$ 个球。此时可以认为区间修改就是 $d_{r + 1}$ 将一个球给了 $d_l$。

我们考虑建立费用流：指定一个起点 $s$ 和终点 $t$。

对于 $d_i\ge 0$，我们从 $s$ 向 $i$ 连边，容量为 $d_i$，代价为 0，含义是把多余的球交给网络分配。
对于 $d_i < 0$，我们从 $i$ 向 $t$ 连边，容量为 $-d_i$，代价是 0，含义是这个点必须得到 $-d_i$ 个球，流量需要满足其要求。
对于 $m$ 个操作 $[l,r]$，我们从 $r + 1$ 向 $l$ 连边，容量是无穷大，代价是 1，含义是把球从 $r+1$ 搬到 $l$，需要代价。
额外从 $s$ 向 $n + 1$ 连边，容量为无穷大，代价是 0，含义是涉及到 $a_n$ 的区间修改可以任意进行，$d_{n+1}$ 可以减少任意次。

我们跑一次从 $s$ 到 $t$ 的费用流，因为需要满足所有 $d_i < 0$，我们设 $res = \sum_{d_i<0}(-d_i)$ 如果流量小于 $res$，说明不能满足所有 $d_i$，不合法，否则输出代价即可。

时间复杂度：$O(n\max a_i(n + m)\log(n + m))$

#include <bits/stdc++.h>

#define int long long
using namespace std;

using i64 = long long;
using u64 = unsigned long long;
using u32 = unsigned;

using u128 = unsigned __int128;
using i128 = __int128;
using ld = long double;

constexpr int inf = 2e18;

template <class T>
struct MinCostFlow {
    struct _Edge {
        int to;
        T cap;
        T cost;
        _Edge(int to_, T cap_, T cost_) : to(to_), cap(cap_), cost(cost_) {}
    };

    int n;
    std::vector<_Edge> e;
    std::vector<std::vector<int>> g;
    std::vector<T> h, dis;
    std::vector<int> pre;
    bool dijkstra(int s, int t) {
        dis.assign(n + 1, std::numeric_limits<T>::max());
        pre.assign(n + 1, -1);
        std::priority_queue<std::pair<T, int>, std::vector<std::pair<T, int>>,
                            std::greater<std::pair<T, int>>>
            pq;
        dis[s] = 0;
        pq.emplace(0, s);
        while (!pq.empty()) {
            T d = pq.top().first;
            int u = pq.top().second;
            pq.pop();
            if (dis[u] != d) {
                continue;
            }
            for (auto i : g[u]) {
                int v = e[i].to;
                T cap = e[i].cap;
                T cost = e[i].cost;
                if (cap > 0 && dis[v] > d + h[u] - h[v] + cost) {
                    dis[v] = d + h[u] - h[v] + cost;
                    pre[v] = i;
                    pq.emplace(dis[v], v);
                }
            }
        }
        return dis[t] != std::numeric_limits<T>::max();
    }
    MinCostFlow() {}
    MinCostFlow(int n_) { init(n_); }
    void init(int n_) {
        n = n_;
        e.clear();
        g.assign(n + 1, {});
    }
    void addEdge(int u, int v, T cap, T cost) {
        g[u].push_back(e.size());
        e.emplace_back(v, cap, cost);
        g[v].push_back(e.size());
        e.emplace_back(u, 0, -cost);
    }
    std::pair<T, T> flow(int s, int t) {
        T flow = 0;
        T cost = 0;
        h.assign(n + 1, 0);
        while (dijkstra(s, t)) {
            for (int i = 1; i <= n; i++) {
                h[i] += dis[i];
            }
            T aug = std::numeric_limits<T>::max();
            for (int i = t; i != s; i = e[pre[i] ^ 1].to) {
                aug = std::min(aug, e[pre[i]].cap);
            }
            for (int i = t; i != s; i = e[pre[i] ^ 1].to) {
                e[pre[i]].cap -= aug;
                e[pre[i] ^ 1].cap += aug;
            }
            flow += aug;
            cost += aug * h[t];
        }
        return {flow, cost};
    }
    struct Edge {
        int from;
        int to;
        T cap;
        T cost;
        T flow;
    };
    std::vector<Edge> edges() {
        std::vector<Edge> a;
        for (int i = 0; i < e.size(); i += 2) {
            Edge x;
            x.from = e[i + 1].to;
            x.to = e[i].to;
            x.cap = e[i].cap + e[i + 1].cap;
            x.cost = e[i].cost;
            x.flow = e[i + 1].cap;
            a.push_back(x);
        }
        return a;
    }
};

signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n, m;
    cin >> n >> m;
    vector<int> a(n + 1), d(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    for (int i = 1; i <= n; i++) {
        d[i] = a[i] - a[i - 1];
    }
    int s = n + 2, t = s + 1;
    int res = 0;
    MinCostFlow<int> mf(n + 3);
    for (int i = 1; i <= n; i++) {
        if (d[i] >= 0) {
            mf.addEdge(s, i, d[i], 0);
        } else {
            res -= d[i];
            mf.addEdge(i, t, -d[i], 0);
        }
    }
    mf.addEdge(s, n + 1, inf, 0);
    for (int i = 1; i <= m; i++) {
        int l, r;
        cin >> l >> r;
        mf.addEdge(r + 1, l, inf, 1);
    }
    auto [flow, cost] = mf.flow(s, t);
    if (flow < res) {
        cout << -1 << "\n";
    } else {
        cout << cost << "\n";
    }

    return 0;
}

2024 ICPC 网络赛第一场 C

题意

在模 2 的条件下，判断大小为 $n$ 的排列 $p$ 的个数，要求给定 $n$ 组 $[l_i,r_i]$，$l_i\le p_i\le r_i$。

$n\le 10^6$

题解

结论：模 2 意义下的二分图匹配数与该图的行列式相同。

我们建立 $[1,n]$ 每一个数与每一行的对应关系，那么题意就转化为了二分图的大小为 $n$ 的完美匹配的数量的奇偶性。这个问题是难以求解的，我们尝试将关系对应到行列式中，矩阵第 $a_{i,j} = 1$ 对应 $j\in[l_i,r_i]$，否则为 0。而我们知道行列式关于逆序对的定义有 $\det(A) = \sum\limits_{(j_1,j_2,...,j_n)\in S_n}(-1)^{\pi(j_1,j_2,...,j_n)}a_{1,j_1}a_{2,j_2}...a_{n,j_n}$。注意如果我们省去 $(-1)^\pi$，这个式子就是我们的答案，因为此时相当于枚举了所有 $n!$ 种排列，只有它们全部取 1 时才会被统计到答案中，而一个数取 1 也满足这个数与行的对应关系。但是去掉 $(-1)^\pi$ 是一个非常困难的问题，然而在模 2 条件下，二者完全相等，因此我们只需要求出这个行列式的奇偶。

同样，在模 2 条件下，这个行列式取 1 当且仅当它是满秩的。考虑将矩阵左边加一列，上面加一行，只有最左上角的元素是 1，其余添加的元素都是 0，这样行列式不变。我们再进行列初等变换，每一列减去它后一列，这样对于 $i\in[1,n]$，只会剩下 $a_{i,l_i-1} = -1,a_{i,r_i} = 1$。此时矩阵为满秩当且仅当边 $(l_i - 1, r_i)$ 构成的图无环，否则构成环的几条边可以通过行初等变换消除。

我们通过并查集判环即可，时间复杂度 $O(n\alpha(n))$。

还有一种想法是，对于两个区间 $[l_1,r_1],[l_2,r_2]$，如果它们存在一个交集 $[l,r]$，如果最终有至少两个位置都落在它们的交集，那么可以交换这些位置，那么这样的方案对答案就没有贡献了，因为这些位置的排列是偶数种。

那么我们只需要考虑不存在任何两个位置同时落在它们交集里的情况。考虑从左到右递推，首先看 1 填在哪里。假设存在区间 $[1,r_1],[1,r_2],...,[1,r_x],r_1\le r_2\le...\le r_x$。那么要求不存在落在交集，我们只能使用 $[1,r_1]$ 的 1（$r$ 相同的也行），将其余的区间变为 $[r_1 + 1, r_i]$。可以使用堆 + 启发式合并，时间复杂度 $O(n\log^2n)$。

使用并查集判环：

#include <bits/stdc++.h>

#define int long long
using namespace std;

using i64 = long long;
using u64 = unsigned long long;
using u32 = unsigned;

using u128 = unsigned __int128;
using i128 = __int128;
using ld = long double;

struct DSU {
    int n;
    vector<int> p, sz;
    DSU(int n) { init(n); }
    void init(int n_) {
        n = n_;
        p.resize(n + 1);
        sz.resize(n + 1, 1);
        iota(p.begin(), p.end(), 0);
    }
    int find(int x) {
        while (x != p[x]) {
            x = p[x] = p[p[x]];
        }
        return x;
    }
    bool merge(int x, int y) {
        x = find(x);
        y = find(y);
        if (x == y) {
            return false;
        }
        if (sz[x] > sz[y]) {
            swap(x, y);
        }
        p[x] = y;
        sz[y] += sz[x];
        return true;
    }
    bool same(int x, int y) { return find(x) == find(y); }
};

void solve() {
    int n;
    cin >> n;
    DSU dsu(n);
    int ans = 1;
    for (int i = 1; i <= n; i++) {
        int l, r;
        cin >> l >> r;
        l--;
        if (!dsu.merge(l, r)) {
            ans = 0;
        }
    }
    cout << ans << "\n";
}

signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int t;
    cin >> t;
    while (t--) {
        solve();
    }

    return 0;
}

使用堆 + 启发式合并：

#include <bits/stdc++.h>

#define int long long
using namespace std;

using i64 = long long;
using u64 = unsigned long long;
using u32 = unsigned;

using u128 = unsigned __int128;
using i128 = __int128;
using ld = long double;

void solve() {
    int n;
    cin >> n;
    vector<priority_queue<int, vector<int>, greater<>>> pq(n + 2);
    for (int i = 1; i <= n; i++) {
        int l, r;
        cin >> l >> r;
        pq[l].push(r);
    }
    for (int i = 1; i <= n; i++) {
        if (pq[i].empty()) {
            cout << 0 << "\n";
            return;
        }
        int t = pq[i].top();
        pq[i].pop();
        while (!pq[i].empty() && pq[i].top() == t) {
            pq[i].pop();
        }
        if (pq[i].size() > pq[t + 1].size()) {
            swap(pq[i], pq[t + 1]);
        }
        while (!pq[i].empty()) {
            pq[t + 1].push(pq[i].top());
            pq[i].pop();
        }
    }
    cout << 1 << "\n";
}

signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int t;
    cin >> t;
    while (t--) {
        solve();
    }

    return 0;
}

2024 ICPC 网络赛第一场 F

题意

给定一个序列 $a$，求将 $a$ 全部变成最大值的最大操作次数，每次操作可以选择一个区间（不能所有数相同），将这个区间覆盖为区间最大值。

$n\le 2\times 10^5$

题解

考虑单调栈维护每个位置左右第一个比他大的数的位置 $l_i,r_i$。最优的染色策略一定是选择尽量小的区间，而一个较小的数可以类似 $[i,r_i],[i,r_{r_i}],...$ 这样的方式染色，因此可以想到从最大值递推。设 $ans_i$ 表示位置 $i$ 最多染多少次到最大值。设 $fa$ 为 $a_{l_i},a_{r_i}$ 中值较小的对应的 $l_i,r_i$，那么 $ans_i = ans_{fa} + 1$。

时间复杂度 $O(n\log n)$，瓶颈是离散化。

#include <bits/stdc++.h>

#define int long long
using namespace std;

using i64 = long long;
using u64 = unsigned long long;
using u32 = unsigned;

using u128 = unsigned __int128;
using i128 = __int128;
using ld = long double;

void solve() {
    int n;
    cin >> n;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    auto b = a;
    sort(b.begin() + 1, b.end());
    vector<vector<int>> v(n + 1);
    for (int i = 1; i <= n; i++) {
        a[i] = lower_bound(b.begin() + 1, b.end(), a[i]) - b.begin();
        v[a[i]].push_back(i);
    }
    vector<int> ans(n + 1), l(n + 1), r(n + 1), stk;
    for (int i = 1; i <= n; i++) {
        while (!stk.empty() && a[i] >= a[stk.back()]) {
            stk.pop_back();
        }
        l[i] = stk.empty() ? -1 : stk.back();
        stk.push_back(i);
    }
    stk.clear();
    for (int i = n; i >= 1; i--) {
        while (!stk.empty() && a[i] >= a[stk.back()]) {
            stk.pop_back();
        }
        r[i] = stk.empty() ? -1 : stk.back();
        stk.push_back(i);
    }
    for (int i = n; i >= 1; i--) {
        for (auto x : v[i]) {
            int fa;
            if (l[x] == -1 && r[x] == -1) {
                continue;
            } else if (l[x] == -1) {
                fa = r[x];
            } else if (r[x] == -1) {
                fa = l[x];
            } else if (a[l[x]] > a[r[x]]) {
                fa = r[x];
            } else {
                fa = l[x];
            }
            ans[x] = ans[fa] + 1;
        }
    }

    int res = accumulate(ans.begin() + 1, ans.end(), 0ll);
    cout << res << "\n";
}

signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int t;
    cin >> t;
    while (t--) {
        solve();
    }

    return 0;
}

2024 ICPC 网络赛第一场 G

题意

给定长度为 $n$ 的数组 $a$，定义 $b_{l,r}$ 为 $a$ 数组区间 $[l,r]$ 的中位数，$c_{i,j}$ 为 $\{b_{l,r}\},i\le l\le r\le j$ 的中位数，求 $c$ 的中位数。

$n\le 2000$

题解

求中位数的一个经典方法是二分答案，check $mid$ 时定义 $b_i = (a[i]\ge mid)$，如果 1 的数量大于 0 的数量就返回 true。

这里考虑类似的方法，从 $a$ 推到 $b$ 时 $O(n^2)$ 是可以接受的，考虑从 $b$ 到 $c$ 的优化，注意到我们只需要知道 $c$ 中 0 多还是 1 多。我们定义 $pre_{i,j}$ 表示区间 $[i,j]$ 中以 $i$ 为左端点的所有会变成 1 的区间的数量。在计算 $c$ 中数量时，考虑枚举右端点 $j$，再枚举左端点 $i\in[1, j]$，我们钦定 $b$ 中选择的区间都是以左端点开头的，这样不会重复。那么 $[i,j]$ 中 1 的数量就是 $pre_{i,j}$，0 的数量就是 $i - j + 1 - pre_{i,j}$。

时间复杂度：$O(n^2\log n)$

#include <bits/stdc++.h>

#define int long long
using namespace std;

using i64 = long long;
using u64 = unsigned long long;
using u32 = unsigned;

using u128 = unsigned __int128;
using i128 = __int128;
using ld = long double;

signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n;
    cin >> n;
    vector<int> a(n + 1);
    int lo = 2e9, hi = 0;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        lo = min(lo, a[i]);
        hi = max(hi, a[i]);
    }
    int ans = 0;
    while (lo <= hi) {
        int mid = (lo + hi) / 2;
        auto check = [&](int mid) {
            vector<int> b(n + 1);
            for (int i = 1; i <= n; i++) {
                b[i] = a[i] >= mid;
            }
            vector<vector<int>> pre(n + 1, vector<int>(n + 1));
            for (int i = 1; i <= n; i++) {
                int cnt[2]{};
                for (int j = i; j <= n; j++) {
                    cnt[b[j]]++;
                    pre[i][j] = pre[i][j - 1] + (cnt[1] > cnt[0]);
                }
            }
            int tot[2]{};
            for (int i = 1; i <= n; i++) {
                int cnt[2]{};
                for (int j = i; j >= 1; j--) {
                    cnt[1] += pre[j][i];
                    cnt[0] += i - j + 1 - pre[j][i];
                    tot[cnt[1] > cnt[0]]++;
                }
            }
            return tot[1] > tot[0];
        };
        if (check(mid)) {
            ans = mid;
            lo = mid + 1;
        } else {
            hi = mid - 1;
        }
    }
    cout << ans << "\n";

    return 0;
}

2025 ICPC 网络赛第一场 D

题意

给定一棵树，每个节点有权值，将这棵树拆成若干个树，每棵树的权值为树中最大值减去最小值，求拆出来的权值最大值。

题解

树形 dp，设 $dp_{x,0/1,0/1/2/3}$ 代表以 $x$ 为根节点的子树选 / 不选，如果选，不作为最值 / 作为最大值 / 作为最小值 / 这棵子树最大值减最小值的答案。

#include <bits/stdc++.h>

#define int long long
using namespace std;

using i64 = long long;
using u64 = unsigned long long;
using u32 = unsigned;

using u128 = unsigned __int128;
using i128 = __int128;
using ld = long double;

constexpr int N = 1e6 + 5;
constexpr int inf = 3e18;
int dp[N][2][4];

signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n;
    cin >> n;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    vector<vector<int>> adj(n + 1);
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    auto chmax = [&](int &a, int b) {
        if (b > a) {
            a = b;
        }
    };
    auto dfs = [&](this auto &&dfs, int x, int fa) -> void {
        for (int i = 0; i < 2; i++) {
            for (int j = 0; j < 4; j++) {
                dp[x][i][j] = -inf;
            }
        }
        dp[x][0][0] = 0;
        dp[x][1][0] = 0;
        dp[x][1][1] = a[x];
        dp[x][1][2] = -a[x];
        for (auto y : adj[x]) {
            if (y == fa) {
                continue;
            }
            dfs(y, x);
            int ndp[2][4];
            for (int i = 0; i < 2; i++) {
                for (int j = 0; j < 4; j++) {
                    ndp[i][j] = -inf;
                }
            }
            chmax(ndp[0][0], dp[x][0][0] + dp[y][0][0]);
            for (int j = 0; j < 4; j++) {
                chmax(ndp[1][j], dp[x][1][j] + dp[y][0][0]);
            }
            for (int i = 0; i < 4; i++) {
                for (int j = 0; j < 4; j++) {
                    if ((i & j) == 0) {
                        chmax(ndp[1][i | j], dp[x][1][i] + dp[y][1][j]);
                        if ((i | j) != 3) {
                            continue;
                        }
                        chmax(ndp[0][0], dp[x][1][i] + dp[y][1][j]);
                    }
                }
            }
            for (int i = 0; i < 2; i++) {
                for (int j = 0; j < 4; j++) {
                    dp[x][i][j] = ndp[i][j];
                }
            }
        }
    };
    dfs(1, 0);
    cout << dp[1][0][0] << "\n";

    return 0;
}

2025 ICPC 网络赛第一场 F

题意

交互题。有一个机器人初始在 $(x,y)$ 每次向八个方向随机移动，你可以任意选定格子放置障碍，在 1000 次放置中困住机器人。

$0 < x,y\le 20$，坐标不会超过 1000。

题解

一图流。

坐标不会超过 $T = 1000$ 的限制给我们提供了外层正方形，我们如图所示划线即可。但是这样的操作次数是 $T + \dfrac{T}{2} + \dfrac{T}{2} + \dfrac{T}{4} + \dfrac{T}{4} + ... < \frac{T(1-\dfrac{1}{2^n})}{1 - \dfrac{1}{2}} + \dfrac{T}{2} + \dfrac{T}{4} + ... + \dfrac{T}{2^n} < 3T$，会超过限制。

由于初始给定的坐标均在 20 以内，我们参考这个思路自己重新规定边界，需要额外的 $2T$ 次操作，那么我们取 $5T = 1000$ 即 $T = 200$。

重点就在于如何构造外层边界且机器人不能走出去。不妨每次取离机器人切比雪夫距离最近的点，但是这样的话如果机器人在 $y = x$ 上移动，可能导致点在上 / 右分布不均，最后能逃出去。为了防止这种情况，距离相同的话随机取上右。

构造好初始边界后递归放置中间的线即可。

#include <bits/stdc++.h>

#define int long long
using namespace std;

using i64 = long long;
using u64 = unsigned long long;
using u32 = unsigned;

using u128 = unsigned __int128;
using i128 = __int128;
using ld = long double;

mt19937_64 rnd(time(NULL));

signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    array<int, 2> p;
    auto move = [&]() {
        int x, y;
        cin >> x >> y;
        p = {x, y};
        if (x == 0 && y == 0) {
            exit(0);
        }
    };
    auto block = [&](array<int, 2> a) {
        cout << a[0] << " " << a[1] << endl;
        move();
    };
    move();
    auto dis = [&](const array<int, 2> &a, const array<int, 2> &b) {
        return max(abs(a[0] - b[0]), abs(a[1] - b[1]));
    };
    auto build = [&](int t) {
        vector<array<int, 2>> vec;
        for (int i = 1; i <= t; i++) {
            vec.push_back({i, t});
        }
        for (int i = 1; i < t; i++) {
            vec.push_back({t, i});
        }
        for (int i = 1; i <= 2 * t - 1; i++) {
            shuffle(vec.begin(), vec.end(), rnd);
            for (int i = 0; i < vec.size() - 1; i++) {
                if (dis(vec[i], p) < dis(vec[i + 1], p)) {
                    swap(vec[i], vec[i + 1]);
                }
            }
            block(vec.back());
            vec.pop_back();
        }
    };
    build(200);
    auto solve = [&](this auto &&solve, array<int, 2> a,
                     array<int, 2> b) -> void {
        if (a[0] > b[0] || a[1] > b[1]) {
            return;
        }
        if (b[0] - a[0] > b[1] - a[1]) {
            int mid = (a[0] + b[0]) / 2;
            for (int i = a[1]; i <= b[1]; i++) {
                block({mid, i});
            }
            if (p[0] < mid) {
                solve(a, {mid - 1, b[1]});
            } else {
                solve({mid + 1, a[1]}, b);
            }
        } else {
            int mid = (a[1] + b[1]) / 2;
            for (int i = a[0]; i <= b[0]; i++) {
                block({i, mid});
            }
            if (p[1] < mid) {
                solve(a, {b[0], mid - 1});
            } else {
                solve({a[0], mid + 1}, b);
            }
        }
    };
    solve({1, 1}, {199, 199});

    return 0;
}

2025 ICPC 网络赛第一场 J

题意

给定二维平面 $n$ 个点，进行 $m$ 次操作，每次操作让所有点向上下左右任意方向移动一个单位，求最终状态所有点之间曼哈顿距离小于等于 $k$ 有多少种移动方案，模 998244353。

$n\le 50, m\le 10^5, k\le 10$。

题解

看到曼哈顿距离可以思考一下切比雪夫距离：$(x,y)$ 的曼哈顿距离等价于 $(x + y, x - y)$ 的切比雪夫距离，而此时的移动就变成了往左上、左下、右上、右下四个方向，等价于先移动一维，再移动另一维，即两维独立，可以分别考虑，答案为两维答案的乘积。

那么只需要考虑一维，等价于数轴上一些点向左右移动 $m$ 次，最终状态在一个长度为 $k$ 的区间内的方案数，容易想到容斥。设 $f(l,r)$ 为将所有点都移动到区间 $[l,r]$ 的方案数，与一般的容斥不同的是，我们并不能设出一个类似 $g(l,r)$ 含“恰好”关键词的状态。不妨考虑枚举左端点，以 $i$ 为左端点的方案数就是 $f(i,r) - f(i + 1, r)$，那么我们的答案就是 $\sum_{i=-\infty}^{+\infty}(f(i,i + k) - f(i + 1, i + k))$。

再考虑如何求 $f(l,r)$。每个点都是独立的，方案数就是每个点走到 $[l,r]$ 的方案数的乘积，我们枚举每个点初始位置为 $x$ 走到 $i\in[l,r]$ ，那么方案数就是 $m$ 步中取向左 / 向右的步数，我们设向左走了 $lo$ 步，向右走了 $hi$ 步，那么有 $\begin{cases}lo + hi = m\\i - x = hi - lo\end{cases}$ 就可以求解了。

时间复杂度：$O(nmk)$

#include <bits/stdc++.h>

#define int long long
using namespace std;

using i64 = long long;
using u64 = unsigned long long;
using u32 = unsigned;

using u128 = unsigned __int128;
using i128 = __int128;
using ld = long double;

template <class T>
constexpr T power(T a, i64 b) {
    T res = 1;
    for (; b; b /= 2, a *= a) {
        if (b % 2) {
            res *= a;
        }
    }
    return res;
}

constexpr i64 mul(i64 a, i64 b, i64 p) {
    i64 res = a * b - i64(1.L * a * b / p) * p;
    res %= p;
    if (res < 0) {
        res += p;
    }
    return res;
}
template <int P>
struct MInt {
    int x;
    constexpr MInt() : x{} {}
    constexpr MInt(i64 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 power(*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 std::istream &operator>>(std::istream &is, MInt &a) {
        i64 v;
        is >> v;
        a = MInt(v);
        return is;
    }
    friend constexpr std::ostream &operator<<(std::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();

constexpr int P = 998244353;
using Z = MInt<P>;  // 静态模数，题目给定模数
using D = MInt<0>;  // 动态模数，可以 D::setMod(x) 改变

struct Comb {
    int n;
    std::vector<Z> _fac;
    std::vector<Z> _invfac;
    std::vector<Z> _inv;

    Comb() : n{0}, _fac{1}, _invfac{1}, _inv{0} {}
    Comb(int n) : Comb() { init(n); }

    void init(int m) {
        if (m <= n) return;
        _fac.resize(m + 1);
        _invfac.resize(m + 1);
        _inv.resize(m + 1);

        for (int i = n + 1; i <= m; i++) {
            _fac[i] = _fac[i - 1] * i;
        }
        _invfac[m] = _fac[m].inv();
        for (int i = m; i > n; i--) {
            _invfac[i - 1] = _invfac[i] * i;
            _inv[i] = _invfac[i] * _fac[i - 1];
        }
        n = m;
    }

    Z fac(int m) {
        if (m > n) init(2 * m);
        return _fac[m];
    }
    Z invfac(int m) {
        if (m > n) init(2 * m);
        return _invfac[m];
    }
    Z inv(int m) {
        if (m > n) init(2 * m);
        return _inv[m];
    }
    Z binom(int n, int m) {
        if (n < m || m < 0) return 0;
        return fac(n) * invfac(m) * invfac(n - m);
    }
} comb(200000);  // Z 类型全局初始化，D 类型需要局部初始化

signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n, m, k;
    cin >> n >> m >> k;
    vector<int> a(n + 1), b(n + 1);
    for (int i = 1; i <= n; i++) {
        int x, y;
        cin >> x >> y;
        a[i] = x + y;
        b[i] = x - y;
    }
    auto solve = [&](vector<int> &a) {
        Z ans = 0;
        sort(a.begin() + 1, a.end());
        auto calc = [&](int a, int l, int r) {
            Z res = 0;
            for (int i = l; i <= r; i++) {
                int b = i - a + m;
                if (b < 0 || b % 2 != 0) {
                    continue;
                }
                res += comb.binom(m, b / 2);
            }
            return res;
        };
        for (int i = a[n] - m - k; i <= a[1] + m; i++) {
            Z mul = 1;
            for (int j = 1; j <= n; j++) {
                mul *= calc(a[j], i, i + k);
            }
            ans += mul;
            mul = 1;
            for (int j = 1; j <= n; j++) {
                mul *= calc(a[j], i + 1, i + k);
            }
            ans -= mul;
        }
        return ans;
    };
    cout << solve(a) * solve(b) << "\n";

    return 0;
}

CF 2137 G

题意

给定一张有向无环图，$q$ 次询问，Cry 和 River 进行博弈。初始所有点都是蓝色，每次询问有两种操作：1. 将一个节点涂成红色，2. 询问一个节点，Cry 先手，两人轮流沿边移动，如果 River 能走到红色节点，River 胜利；如果能走到无路可走，且该节点不是红色，Cry 胜利，回答 Cry 是否存在必胜策略。

题解

一个点 $v$ 是红色，那么考虑 $u$ 连向 $v$，若在 $u$ 点时轮到 River 移动，则 Cry 必败，因此我们可以建立反图，定义 $dp_{u,0/1}$ 代表 Alice / Bob 在 $u$ 点的状态，为 1 则 Alice 必胜，为 0 则 Alice 必败。考虑状态转移。如果一个点 $v$ 被染成红色，则 $dp_{v,0/1} = 0$，同时反图上 $dp_{u, 1} = 0$。同时若原图中所有 $u\rightarrow v$ 的 $v$ 节点都被标记为必败态，$u$ 点也一定是必败态，我们可以维护出度。

注意到每个节点的每个状态只会被访问一次，我们可以将复杂度均摊到 $O(n)$

#include <bits/stdc++.h>

#define int long long
using namespace std;

using i64 = long long;
using u64 = unsigned long long;
using u32 = unsigned;

using u128 = unsigned __int128;
using i128 = __int128;
using ld = long double;

void solve() {
    int n, m, q;
    cin >> n >> m >> q;
    vector<vector<int>> adj(n + 1);
    vector<int> deg(n + 1);
    for (int i = 1; i <= m; i++) {
        int u, v;
        cin >> u >> v;
        adj[v].push_back(u);
        deg[u]++;
    }
    vector<array<int, 2>> dp(n + 1, {1, 1});
    while (q--) {
        int op, u;
        cin >> op >> u;
        if (op == 2) {
            cout << (dp[u][0] == 1 ? "YES" : "NO") << "\n";
            continue;
        }
        queue<array<int, 2>> q;
        if (dp[u][0] == 1) {
            dp[u][0] = 0;
            q.push({u, 0});
        }
        if (dp[u][1] == 1) {
            dp[u][1] = 0;
            q.push({u, 1});
        }
        while (!q.empty()) {
            auto [u, s] = q.front();
            q.pop();
            if (s == 0) {
                for (auto v : adj[u]) {
                    if (dp[v][1] == 1) {
                        dp[v][1] = 0;
                        q.push({v, 1});
                    }
                }
            } else {
                for (auto v : adj[u]) {
                    deg[v]--;
                    if (deg[v] == 0 && dp[v][0] == 1) {
                        dp[v][0] = 0;
                        q.push({v, 0});
                    }
                }
            }
        }
    }
}

signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int t;
    cin >> t;
    while (t--) {
        solve();
    }

    return 0;
}

CF 2140 C

题意

Alice 和 Bob 博弈，Alice 先手。对于一个数组 $a$，定义 $f(a) = \text{cost} + a_1 - a_2 + a_3 - a_4 + ...a_n$，初始 $\text{cost}$ 为 0。两人都可以选择两个位置 $i < j$ 交换，并给 $\text{cost}$ 加上 $j - i$，也可以选择终结游戏，Alice 想最大化 $f(a)$，Bob 想最小化，求最终 $f(a)$。

题解

如果 Bob 选择交换，那么 Alice 可以交换回去，答案只会变大，因此 Bob 只会终结游戏，只需要考虑第一轮 Alice 的操作。

那么 Alice 可以选择同号的两个位置交换将结果变大，也可以选择异号的两个位置交换。前者选择距离最大的位置即可，后者考虑对 $f(a)$ 的贡献：从 $-a + b$ 变成 $+a - b$，相当于将 $f(a)$ 进行 $+2a - 2b + j - i$，可以将 $2a - i$ 和 $-2b + j$ 拆开处理，从前往后扫描取贡献最大的即可。

#include <bits/stdc++.h>

#define int long long
using namespace std;

using i64 = long long;
using u64 = unsigned long long;
using u32 = unsigned;

using u128 = unsigned __int128;
using i128 = __int128;
using ld = long double;

void solve() {
    int n;
    cin >> n;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    int sum = 0;
    for (int i = 1; i <= n; i++) {
        sum += i & 1 ? a[i] : -a[i];
    }
    int ans = sum;
    ans = max(ans, sum + (n & 1 ? n - 1 : n - 2));
    int mx1 = -3e18, mx2 = -3e18;
    for (int i = 1; i <= n; i++) {
        if (i & 1) {
            mx1 = max(mx1, -2 * a[i] - i);
            ans = max(ans, sum - 2 * a[i] + i + mx2);
        } else {
            mx2 = max(mx2, 2 * a[i] - i);
            ans = max(ans, sum + 2 * a[i] + i + mx1);
        }
    }
    cout << ans << "\n";
}

signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int t;
    cin >> t;
    while (t--) {
        solve();
    }

    return 0;
}

CF 2140 D

题意

给定 $n$ 条线段 $[l,r]$，初始都未被标记。每次操作可以取两条线段，标记他们，并新增一条被标记的线段，端点介于两线段之间。如果只有一条线段，就直接标记它，求操作结束后所有被标记的线段的长度的和的最大值。

题解

取两条线段的话肯定是贪心取右端点减左端点的最大值。如果 $n$ 是偶数，我们只需要最大化 $\sum_{i=1}^\frac{n}{2}r_i - \sum_{i=\frac{n}{2} + 1}^nl_i$，双变量的最值，我们可以先求 $\sum_{i=1}^rr_i$，我们每将一条取 $l$ 的线段当成了取 $r$ 来计算，答案就会多加 $l + r$，因此我们需要减去 $\dfrac{n}{2}$ 个 $l_i + r_i$。取最大值的话我们就可以按照 $l_i + r_i$ 进行排序。

再考虑 $n$ 为奇数的情况，有一条线段不能取到 $l_i$ 或 $r_i$。假设先把它取到，那么我们就再可能取到 $r_i$ 的 $[\lfloor\dfrac{n}{2}\rfloor 1 ,n]$ 找最小的 $r_i$ 减去或在 $[1, \lfloor\dfrac{n}{2}\rfloor] + 1$ 找最大的 $l_i$ 加上。

#include <bits/stdc++.h>

#define int long long
using namespace std;

using i64 = long long;
using u64 = unsigned long long;
using u32 = unsigned;

using u128 = unsigned __int128;
using i128 = __int128;
using ld = long double;

void solve() {
    int n;
    cin >> n;
    vector<array<int, 2>> a(n + 1);
    int sum = 0;
    for (int i = 1; i <= n; i++) {
        int x, y;
        cin >> x >> y;
        a[i] = {x, y};
        sum += y;
        sum += y - x;
    }
    sort(a.begin() + 1, a.end(),
         [&](auto &i, auto &j) { return i[0] + i[1] < j[0] + j[1]; });
    for (int i = 1; i <= n / 2; i++) {
        sum -= a[i][0] + a[i][1];
    }
    if (n % 2 == 0) {
        cout << sum << "\n";
        return;
    }
    int ans = -3e18;
    for (int i = n / 2 + 1; i <= n; i++) {
        ans = max(ans, sum - a[i][1]);
    }
    sum -= a[n / 2 + 1][0] + a[n / 2 + 1][1];
    for (int i = 1; i <= n / 2 + 1; i++) {
        ans = max(ans, sum + a[i][0]);
    }
    cout << ans << "\n";
}

signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int t;
    cin >> t;
    while (t--) {
        solve();
    }

    return 0;
}

CF 2140 E1

题意

$n$ 堆物品，每堆物品数在 $[1,m]$ 之间，给定 $k$ 个可操作的位置。Alice 和 Bob 轮流操作，Alice 先手。每轮操作选择一个位置，删去该堆物品，且该位置后面的位置前移。当只剩一堆的时候游戏结束，Alice 最大化最后剩的物品数量，Bob 最小化。求所有可能的初始物品中最终状态的物品数量的和。

$n\le 20, m\le 2$。

题解

Easy Version 中 $m = 2$，最终状态不是 1 就是 2。$n$ 的范围提示我们状压。我们设 $dp[l][0/1][s]$ 表示当前有 $l$ 堆物品，Alice / Bob 操作，物品状态为 $s$ 的最终状态。如果 $dp$ 值为 0 表示最后剩余 1，$dp$ 值为 1 表示最后剩余 2。

考虑状态转移，我们可以预处理每个状态删除一个位置后的下一个状态 $nxt[s][pos]$（也可以通过二进制操作 $O(1)$ 得到），那么 Alice 操作下，$dp$ 值取 1 当且仅当其后续状态有一个 $dp[l-1][1][nxt[s][i]]$ 能够取 1，对于 Bob，$dp$ 值取 0 当且仅当其后续状态有一个 $dp[l-1][0][nxt[s][i]]$ 取 0。

最后枚举所有状态即可，时间复杂度 $O(n^22^n)$

#include <bits/stdc++.h>

#define int long long
using namespace std;

using i64 = long long;
using u64 = unsigned long long;
using u32 = unsigned;

using u128 = unsigned __int128;
using i128 = __int128;
using ld = long double;

constexpr int MAXS = 1 << 20;
constexpr int N = 20;
int nxt[MAXS][20];
bool dp[N + 1][2][MAXS];

void solve() {
    int n, m, k;
    cin >> n >> m;
    cin >> k;
    vector<bool> vis(n);
    for (int i = 0; i < k; i++) {
        int x;
        cin >> x;
        x--;
        vis[x] = true;
    }
    if (m == 1) {
        cout << 1 << "\n";
        return;
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < 2; j++) {
            for (int s = 0; s < 1 << i; s++) {
                dp[i][j][s] = 0;
            }
        }
    }
    dp[1][0][1] = dp[1][1][1] = 1;
    for (int l = 2; l <= n; l++) {
        for (int s = 0; s < 1 << l; s++) {
            dp[l][0][s] = 0;
            for (int i = 0; i < l; i++) {
                if (vis[i]) {
                    dp[l][0][s] |= dp[l - 1][1][nxt[s][i]];
                }
            }
            dp[l][1][s] = 1;
            for (int i = 0; i < l; i++) {
                if (vis[i]) {
                    dp[l][1][s] &= dp[l - 1][0][nxt[s][i]];
                }
            }
        }
    }
    int ans = 0;
    for (int i = 0; i < 1 << n; i++) {
        ans += dp[n][0][i] + 1;
    }
    cout << ans << "\n";
}

signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    for (int s = 0; s < MAXS; s++) {
        int x = 0;
        for (int i = 0; i < N; i++) {
            int y = x;
            for (int j = i + 1; j < N; j++) {
                if (s >> j & 1) {
                    y |= 1 << (j - 1);
                }
            }
            nxt[s][i] = y;
            if (s >> i & 1) {
                x |= 1 << i;
            }
        }
    }

    int t;
    cin >> t;
    while (t--) {
        solve();
    }

    return 0;
}

CF 2140 E2

题意

$n\le 20, m\le 10^6$。

题解

在上一问的基础上，$m$ 的范围变成了 $10^6$。

我们考虑一个阈值 $k$，将第一问的状态改为：如果 $a_i < k$，二进制对应 0，否则二进制对应 1。

设 $cnt_r$ 为有多少个状态二进制下 1 的数量为 $r$ 且 $dp[n][0][s]$ 取到 1。那么对于这些状态，二进制为 1 的每一个数都可以取到 $[k, m]$，二进制为 0 的每一个数都可以取到 $[1,k - 1]$。

那么，我们的答案就是 $\sum_{k = 1}^m\sum_{r=0}^n(m-k+1)^r(k-1)^{r-n}cnt_r$。

时间复杂度 $O(nm\log n + n^22^n)$

#include <bits/stdc++.h>

#define int long long
using namespace std;

using i64 = long long;
using u64 = unsigned long long;
using u32 = unsigned;

using u128 = unsigned __int128;
using i128 = __int128;
using ld = long double;

template <class T>
constexpr T power(T a, i64 b) {
    T res = 1;
    for (; b; b /= 2, a *= a) {
        if (b % 2) {
            res *= a;
        }
    }
    return res;
}

constexpr i64 mul(i64 a, i64 b, i64 p) {
    i64 res = a * b - i64(1.L * a * b / p) * p;
    res %= p;
    if (res < 0) {
        res += p;
    }
    return res;
}
template <int P>
struct MInt {
    int x;
    constexpr MInt() : x{} {}
    constexpr MInt(i64 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 power(*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 std::istream &operator>>(std::istream &is, MInt &a) {
        i64 v;
        is >> v;
        a = MInt(v);
        return is;
    }
    friend constexpr std::ostream &operator<<(std::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();

constexpr int P = 1000000007;
using Z = MInt<P>;  // 静态模数，题目给定模数
using D = MInt<0>;  // 动态模数，可以 D::setMod(x) 改变

constexpr int MAXS = 1 << 20;
constexpr int N = 20;
int nxt[MAXS][20];
bool dp[N + 1][2][MAXS];

void solve() {
    int n, m, k;
    cin >> n >> m;
    cin >> k;
    vector<bool> vis(n);
    for (int i = 0; i < k; i++) {
        int x;
        cin >> x;
        x--;
        vis[x] = true;
    }
    if (m == 1) {
        cout << 1 << "\n";
        return;
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < 2; j++) {
            for (int s = 0; s < 1 << i; s++) {
                dp[i][j][s] = 0;
            }
        }
    }
    dp[1][0][1] = dp[1][1][1] = 1;
    for (int l = 2; l <= n; l++) {
        for (int s = 0; s < 1 << l; s++) {
            dp[l][0][s] = 0;
            for (int i = 0; i < l; i++) {
                if (vis[i]) {
                    dp[l][0][s] |= dp[l - 1][1][nxt[s][i]];
                }
            }
            dp[l][1][s] = 1;
            for (int i = 0; i < l; i++) {
                if (vis[i]) {
                    dp[l][1][s] &= dp[l - 1][0][nxt[s][i]];
                }
            }
        }
    }
    vector<int> cnt(n + 1);
    for (int i = 0; i < 1 << n; i++) {
        if (dp[n][0][i] == 0) {
            continue;
        }
        int x = 0;
        for (int j = 0; j < n; j++) {
            x += i >> j & 1;
        }
        cnt[x]++;
    }
    Z ans = 0;
    for (int k = 1; k <= m; k++) {
        for (int i = 0; i <= n; i++) {
            ans += power(Z(m - k + 1), i) * power(Z(k - 1), n - i) * cnt[i];
        }
    }
    cout << ans << "\n";
}

signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    for (int s = 0; s < MAXS; s++) {
        int x = 0;
        for (int i = 0; i < N; i++) {
            int y = x;
            for (int j = i + 1; j < N; j++) {
                if (s >> j & 1) {
                    y |= 1 << (j - 1);
                }
            }
            nxt[s][i] = y;
            if (s >> i & 1) {
                x |= 1 << i;
            }
        }
    }

    int t;
    cin >> t;
    while (t--) {
        solve();
    }

    return 0;
}

ABC 422 D

题意

构造一个长度为 $2^n$ 的序列，要求所有元素之和为 $k$。将这个序列进行 $n$ 次操作，每次操作将序列变成 $a_1+a_2,a_3+a_4,...,$，取 $X$ 为每个序列最大值减去最小值的最大值，求 $X$ 的最小值以及这个序列。

$n\le 20$

题解

重点是抓住不变量：数组的总和是一定的，我们尝试从 $k$ 开始反向构造回去，由于要让差值最小，我们将 $k$ 拆成 $\lfloor\dfrac{k}{2}\rfloor$ 和 $\lceil\dfrac{k}{2}\rceil$ 即可。模拟 $n$ 次就能得到原序列，且差值最大一定出现在原序列。

甚至还可以证明 $X$ 最大就是 1，因为拆成两个数后总是出现以下情况：

两个数相等，继续拆也相等
拆成一个奇数和一个偶数，继续拆的话奇数有一个数会跟偶数拆成的两个数相同，另一个数差 1。

时间复杂度：$O(2^n)$

#include <bits/stdc++.h>

#define int long long
using namespace std;

using i64 = long long;
using u64 = unsigned long long;
using u32 = unsigned;

using u128 = unsigned __int128;
using i128 = __int128;
using ld = long double;

signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n, k;
    cin >> n >> k;
    vector<int> ans{k};
    for (int i = 0; i < n; i++) {
        vector<int> nxt;
        for (auto a : ans) {
            nxt.push_back(a / 2);
            nxt.push_back(a - a / 2);
        }
        ans = nxt;
    }
    int mx = *max_element(ans.begin(), ans.end());
    int mn = *min_element(ans.begin(), ans.end());
    cout << mx - mn << "\n";
    for (int i = 0; i < ans.size(); i++) {
        cout << ans[i] << " \n"[i == ans.size() - 1];
    }

    return 0;
}

ABC 422 F

题意

一张连通无向图，每个点存在点权。初始重量为 0，沿着边行走，每走到一个点 $u$，重量就增加 $u$ 的点权，在此之前会消耗油，和其重量相等。求从 1 走到 $[1,n]$ 的最小油量。

$n,m\le 5000$

题解

考虑每条边的贡献，在一条路径中，点权乘上的系数成等差数列。问题可以抽象为一个人有 $k$ 张票，每走到一个点，如果它有 $x$ 张票，就消耗 $xa_u$ 的油，每经过一条边就丢掉一张票。那么对于一条路径来说，初始票刚好等于路径长度是最优的，且最多为 $n - 1$ 张。

考虑一个有向图，节点 $(v, x)$ 代表顶点 $v$，剩余车票可能数量为 $x$ ，对于原始图中每条边 $(u,v)$ 和 $1\le x\le n - 1$，都有一条从 $(u,x)$ 到 $(v, x- 1)$ 的边，只需要找出从 $(1,x)$ 到 $(i,0)$ 的最短路即可。

由于这张图是分层图，且是一个 DAG，可以进行 $n - 1$ 轮松弛。

时间复杂度：$O(nm)$

#include <bits/stdc++.h>

#define int long long
using namespace std;

using i64 = long long;
using u64 = unsigned long long;
using u32 = unsigned;

using u128 = unsigned __int128;
using i128 = __int128;
using ld = long double;

signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n, m;
    cin >> n >> m;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    vector<array<int, 2>> edges(m);
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        edges[i] = {u, v};
    }
    constexpr int inf = 3e18;
    vector<int> dp(n + 1, inf), ndp(n + 1, inf);
    dp[1] = 0;
    for (int i = n - 1; i >= 1; i--) {
        ndp = dp;
        for (int i = 1; i <= n; i++) {
            dp[i] = inf;
        }
        dp[1] = 0;
        for (auto [u, v] : edges) {
            dp[u] = min(dp[u], ndp[v] + i * a[v]);
            dp[v] = min(dp[v], ndp[u] + i * a[u]);
        }
    }
    for (int i = 1; i <= n; i++) {
        cout << dp[i] << "\n";
    }

    return 0;
}

ARC 205 B

题意

一张 $n$ 个节点的完全图，给定其中 $m$ 条边是黑色的，可以进行任意次操作，选择三个点，将这三个点两两连接的三条边的颜色翻转，求最大黑色边的数量。

题解

考虑不变量，操作之后每个节点所连接的黑色边的数量的奇偶性是不变的。那么我们根据奇偶性将每个点的黑边数量都取到最大值。

#include <bits/stdc++.h>

#define int long long
using namespace std;

using i64 = long long;
using u64 = unsigned long long;
using u32 = unsigned;

using u128 = unsigned __int128;
using i128 = __int128;
using ld = long double;

signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n, m;
    cin >> n >> m;
    vector<int> deg(n + 1);
    for (int i = 1; i <= m; i++) {
        int u, v;
        cin >> u >> v;
        deg[u]++, deg[v]++;
    }
    int ans = n * (n - 1);
    for (int i = 1; i <= n; i++) {
        ans -= (n - 1 - deg[i]) % 2;
    }
    cout << ans / 2 << "\n";

    return 0;
}

ARC 205 D

题意

给定一棵树，求最大匹配数量，一个节点与不是他祖先节点的节点可以算作一个匹配。

题解

匹配可以发生在一颗子树的不同子树之间，并且我们应该优先给深度较低的节点匹配，否则可能会出现有一条链无法匹配的情况。

那么我们可以维护每棵子树的大小，从根节点开始往下匹配，设 $sz_u,mx_u$ 分别代表以 $u$ 为根节点的子树大小和该子树最大的子树大小，我们同时维护 $u$ 节点的祖先有 $x$ 个节点还没有被匹配，如果 $sz_u + x - mx_u\ge mx_u$，说明当前子树可以完全匹配了，最多剩下一个节点找不到匹配。否则我们可以递归到 $mx_u$ 对应的子树继续。

#include <bits/stdc++.h>

#define int long long
using namespace std;

using i64 = long long;
using u64 = unsigned long long;
using u32 = unsigned;

using u128 = unsigned __int128;
using i128 = __int128;
using ld = long double;

void solve() {
    int n;
    cin >> n;
    vector<vector<int>> adj(n + 1);
    for (int i = 2; i <= n; i++) {
        int x;
        cin >> x;
        adj[x].push_back(i);
    }
    vector<int> sz(n + 1);
    auto dfs = [&](auto dfs, int x) -> void {
        sz[x] = 1;
        for (auto y : adj[x]) {
            dfs(dfs, y);
            sz[x] += sz[y];
        }
    };
    dfs(dfs, 1);
    auto dfs2 = [&](auto dfs2, int x, int r) -> int {
        int ans = 0;
        if (r) {
            r--, ans++;
        }
        int mx = 0, mxid = 0;
        for (auto y : adj[x]) {
            if (sz[y] > mx) {
                mx = sz[y];
                mxid = y;
            }
        }
        int v = sz[x] - 1 - mx;
        if (mx <= r + v) {
            return ans + (mx + r + v) / 2;
        }
        return ans + dfs2(dfs2, mxid, r + v);
    };
    cout << dfs2(dfs2, 1, 0) << "\n";
}

signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int t;
    cin >> t;
    while (t--) {
        solve();
    }

    return 0;
}

ARC 205 E

题意

给定一个序列 $a$，对于 $k\in [1,n]$，求在 $i\in[1,k]$ 中所有满足 $a_i\mid a_k = a_k$ 的 $a_i$ 的乘积，模 998244353。

$n\le 4\times 10^5,a_i< 2^{20}$

题解

根号分治。

有两种暴力，一种是直接遍历 $i\in [1,k]$ 中的 $a_i$，另一种是对于每个数，加入时维护对其他数产生的贡献。

加入一个数 $a_k$ 时，我们可以暴力遍历二进制的低 10 位，将满足与 $a_k$ 或运算后仍然等于 $a_k$ 的值直接加入高 10 位的贡献中。计算一个数的答案，我们遍历高 10 位，与自身低 10 位进行或运算后即可快速统计贡献。

时间复杂度：$O(n2^{10})$

#include <bits/stdc++.h>

#define int long long
using namespace std;

using i64 = long long;
using u64 = unsigned long long;
using u32 = unsigned;

using u128 = unsigned __int128;
using i128 = __int128;
using ld = long double;

template <class T>
constexpr T power(T a, i64 b) {
    T res = 1;
    for (; b; b /= 2, a *= a) {
        if (b % 2) {
            res *= a;
        }
    }
    return res;
}

constexpr i64 mul(i64 a, i64 b, i64 p) {
    i64 res = a * b - i64(1.L * a * b / p) * p;
    res %= p;
    if (res < 0) {
        res += p;
    }
    return res;
}
template <int P>
struct MInt {
    int x;
    constexpr MInt() : x{} {}
    constexpr MInt(i64 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 power(*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 std::istream &operator>>(std::istream &is, MInt &a) {
        i64 v;
        is >> v;
        a = MInt(v);
        return is;
    }
    friend constexpr std::ostream &operator<<(std::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();

constexpr int P = 998244353;
using Z = MInt<P>;  // 静态模数，题目给定模数
using D = MInt<0>;  // 动态模数，可以 D::setMod(x) 改变

signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n;
    cin >> n;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    constexpr int N = (1 << 20) - 1;
    constexpr int M = (1 << 10) - 1;
    vector<Z> b(N + 10, 1);
    for (int j = 1; j <= n; j++) {
        Z r = 1;
        int f = a[j] >> 10, g = a[j] & M;
        for (int i = 0; i <= M; i++) {
            if ((g | i) == i) {
                b[f << 10 | i] *= a[j];
            }
        }
        for (int i = 0; i <= M; i++) {
            if ((f | i) == f) {
                r *= b[i << 10 | g];
            }
        }
        cout << r << "\n";
    }

    return 0;
}

P3830 [SHOI2012] 随机树

题意

按照如下规则生成一棵二叉树：从单个节点的树开始，每次选择一个叶子节点，给他加上左右儿子。给定叶子节点数目 $n$，求：

叶子节点平均深度的数学期望。
树深度的数学期望。根节点深度为 0。

$n\le 100$

题解

概率相关要多想递推啊。先解决第一问，设 $f_x$ 为有 $x$ 个叶子节点的树的平均深度的期望，根据期望的线性性（和的期望等于期望的和），有 $f_x = \dfrac{f_{x-1}\times (x - 1) + f_{x - 1} + 2}{x} = f_{x-1} + \dfrac{2}{x}$，因为一次操作会增加一个新节点，同时增加一个叶子节点的深度。

对于第二问，需要用到正整数期望的一个性质，转变为概率之和。对于正整数随机变量 $x$，有 $E(x) = \sum_{i=1}^\infty\limits P\{x\ge i\}$。

证明：$E(x) = \sum_{i=1}^\infty\limits P\{x = i\}\cdot i = \sum_{i=1}^\infty\limits(P\{x\ge i\} - P\{x\ge i + 1\})\cdot i = \sum_{i=1}^\infty\limits P\{x\ge i\}\cdot i - \sum_{i=1}^\infty\limits P\{x\ge i\}(i - 1) = \sum_{i=1}^\infty\limits P\{x\ge i\}$。

注意到上面这个式子是只含概率的，我们设 $f_{i,j}$ 为有 $i$ 个叶子节点，树的深度大于等于 $j$ 的概率，那么答案就是 $\sum_{i=1}^n\limits f_{n,i}$。

考虑递推，设根节点的左子树叶子节点数目为 $k$，那么右子树叶子节点数目为 $n - k$，有 $f_{i,j} = \sum_{k=1}^{i-1}(f_{k,j} + f_{i-k, j} - f_{k,j}\times f_{i-k, j})\times P_{i,k}$。其中 $P_{i,k}$ 代表叶子节点数目为 $i$，左子树有 $k$ 个叶子节点的概率。

再考虑求 $P_{i,k}$，第一次操作一定会在根节点进行，在左右子树各生成一个节点，那么还有 $k - 1$ 次操作需要在左边进行，$i - k - 1$ 次操作在右边进行，而要将一棵子树构建成有 $i$ 个叶子节点的树，一共 $i$ 步，第 $i$ 步能在 $i$ 个节点里进行，那么方案数分别为 $(k-1)!$ 和 $(i - k - 1)!$，因此方案数为 $\dbinom{i-2}{k-1}\times (k-1)!\times (i - k - 1)! = (i - 2)!$。所以 $P_{i,k} = \dfrac{(i - 2)!}{(i - 1)!} = \dfrac{1}{i - 1}$，与 $k$ 是无关的。

那么设初值 $f_{i,0} = 1$ 就可以递推了。

#include <bits/stdc++.h>

#define int long long
using namespace std;

using i64 = long long;
using u64 = unsigned long long;
using u32 = unsigned;

using u128 = unsigned __int128;
using i128 = __int128;
using ld = long double;

signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int q, n;
    cin >> q >> n;
    if (q == 1) {
        ld ans = 0;
        for (int i = 2; i <= n; i++) {
            ans += 2.l / i;
        }
        cout << fixed << setprecision(6) << ans << "\n";
        return 0;
    }
    vector<vector<ld>> f(n + 1, vector<ld>(n));
    for (int i = 1; i <= n; i++) {
        f[i][0] = 1;
    }
    for (int i = 2; i <= n; i++) {
        for (int j = 1; j <= i - 1; j++) {
            for (int k = 1; k <= i - 1; k++) {
                f[i][j] += (f[k][j - 1] + f[i - k][j - 1] -
                            f[k][j - 1] * f[i - k][j - 1]) /
                           (i - 1);
            }
        }
    }
    ld ans = 0;
    for (int j = 1; j <= n - 1; j++) {
        ans += f[n][j];
    }
    cout << fixed << setprecision(6) << ans << "\n";

    return 0;
}

P4564 [CTSC2018] 假面

题意

$n$ 个怪，每只血量 $m_i$。$q$ 次操作，有两种操作：以 $\dfrac{u}{v}$ 的概率减少给定第 $i$ 只怪一点血量；给定 $k$ 只怪，等概率选择其中还没有死亡的怪，输出选择到每一只怪的概率。最后输出每一只怪剩余血量的期望。

$n\le 200,q\le 2\times 10^5,m_i\le 100$，操作 2 的数量 $C$ 不会超过 $1000$。

题解

对于操作一，由于数据很小，我们设 $f_{i,j}$ 代表第 $i$ 只怪剩余血量 $j$ 的概率，设 $p = \dfrac{u}{v}$ 那么转移有 $f_{i,j} = f_{i,j + 1}\times p + f_{i,j}\times (1-p)$，分别代表这次攻击成功或不成功，注意转移顺序应该是从大到小，不然会多次贡献，且 $j = 0$ 的转移是 $f_{i,0} = f_{i,1}\times p + f_{i,0}$。这一部分的时间复杂度是 $O(qm)$。

对于操作二，可以设 $h_{i,j}$ 是除了 $i$ 个人有 $j$ 个人活着的概率，那么答案就是 $alive_i\times \sum_{j=0}^{k-1}\limits \dfrac{h_{i,j}}{j + 1}$。考虑怎么求 $h_{i,j}$，可以想到递推：设 $dp_{i,j}$ 代表前 $i$ 个人中有 $j$ 个人存活的概率，有 $dp_{i,j} = dp_{i - 1,j }\times dead_{i} + dp_{i-1,j-1}\times alive_i$，其中 $dead_i,alive_i$ 分别代表 $i$ 死亡 / 未死亡的概率，且可以发现 $dead_i = f_{i,0},alive_i = 1 - f_{i,0}$。那么对于每一个人我们可以做这样的 dp，把要求的人放在最后一个，这样 $dp_{k-1}$ 就是 $h_i$，这样是 $O(Cn^3)$ 的，无法通过。

考虑优化，我们对每一个人都重复这样的 dp，考虑能不能递推求出答案：设 $g_i$ 代表有 $i$ 个人存活的概率，那么对于第 $i$ 个人，有 $g_i = g_{i-1}\times p_i + g_i\times (1 - p_i)$，初始 $g_0 = 1$。我们尝试找到 $g,h$ 之间的关系：应该有 $g_j = (1 - p_i)\times h_{i,j} + p_i\times h_{i,j-1}$，那么 $h_{i,j} = \dfrac{g_j - h_{i, j-1}\times p_i}{1 - p_i}(p_i\ne 1)$，若 $p_i = 1$，有 $h_{i,j} = g_{j + 1}$。那么我们先递推求出 $g$，再递推求出 $h$，这样的复杂度是 $O(Cn^2)$。

#include <bits/stdc++.h>

#define int long long
using namespace std;

using i64 = long long;
using u64 = unsigned long long;
using u32 = unsigned;

using u128 = unsigned __int128;
using i128 = __int128;
using ld = long double;

template <class T>
constexpr T power(T a, i64 b) {
    T res = 1;
    for (; b; b /= 2, a *= a) {
        if (b % 2) {
            res *= a;
        }
    }
    return res;
}

constexpr i64 mul(i64 a, i64 b, i64 p) {
    i64 res = a * b - i64(1.L * a * b / p) * p;
    res %= p;
    if (res < 0) {
        res += p;
    }
    return res;
}
template <int P>
struct MInt {
    int x;
    constexpr MInt() : x{} {}
    constexpr MInt(i64 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 power(*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 std::istream &operator>>(std::istream &is, MInt &a) {
        i64 v;
        is >> v;
        a = MInt(v);
        return is;
    }
    friend constexpr std::ostream &operator<<(std::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();

constexpr int P = 998244353;
using Z = MInt<P>;  // 静态模数，题目给定模数
using D = MInt<0>;  // 动态模数，可以 D::setMod(x) 改变

signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    vector<Z> Inv(201);
    Inv[1] = 1;
    for (int i = 2; i <= 200; i++) {
        Inv[i] = (P - P / i) * Inv[P % i];
    }

    int n;
    cin >> n;
    vector<int> m(n + 1);
    vector<vector<Z>> f(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> m[i];
        f[i].resize(m[i] + 2);
        f[i][m[i]] = 1;
    }
    int q;
    cin >> q;
    while (q--) {
        int op;
        cin >> op;
        if (op == 0) {
            int i, u, v;
            cin >> i >> u >> v;
            Z p = Z(u) / v;
            f[i][0] += f[i][1] * p;
            for (int j = 1; j <= m[i]; j++) {
                f[i][j] = f[i][j + 1] * p + f[i][j] * (P + 1 - p);
            }
        } else {
            int k;
            cin >> k;
            vector<Z> g(k + 2);
            vector<int> id(k + 1);
            vector<Z> inv(k + 1), p(k + 1);
            for (int i = 1; i <= k; i++) {
                cin >> id[i];
                p[i] = 0;
                for (int j = 1; j <= m[id[i]]; j++) {
                    p[i] += f[id[i]][j];
                }
                inv[i] = power(f[id[i]][0], P - 2);
            }
            g[0] = 1;
            for (int i = 1; i <= k; i++) {
                for (int j = k; j >= 1; j--) {
                    g[j] = g[j - 1] * p[i] + g[j] * f[id[i]][0];
                }
                g[0] *= f[id[i]][0];
            }
            vector<vector<Z>> h(k + 1, vector<Z>(k + 1));
            for (int i = 1; i <= k; i++) {
                h[i][0] = inv[i] * g[0];
                if (p[i] == 1) {
                    h[i][0] = g[1];
                }
                for (int j = 1; j <= k; j++) {
                    if (p[i] == 1) {
                        h[i][j] = g[j + 1];
                        continue;
                    }
                    h[i][j] = (g[j] - h[i][j - 1] * p[i]) * inv[i];
                }
                Z ans = 0;
                for (int j = 0; j < k; j++) {
                    ans += h[i][j] * Inv[j + 1];
                }
                ans *= p[i];
                cout << ans << " \n"[i == k];
            }
        }
    }
    for (int i = 1; i <= n; i++) {
        Z ans = 0;
        for (int j = 1; j <= m[i]; j++) {
            ans += j * f[i][j];
        }
        cout << ans << " \n"[i == n];
    }

    return 0;
}

P2473 [SCOI2008] 奖励关

题意

$k$ 次操作，每次等概率随机给你 $n$ 种物品的一种，你可以选择拿或不拿，拿的话获取它的价值（可能为负）。这些物品之间还存在一些依赖关系，只有当你之前拿去了某物品的所有依赖物品后，才能拿这件物品，求采取最优策略能拿取价值的期望。

$k\le 100,n\le 15$

题解

看数据识状压，如果直接设 $f_{i,S}$ 为第 $i$ 步，状态为 $S$ 下能拿的最大价值，有一个问题是可能无法到达状态 $S$。采取倒推，设 $f_{i,S}$ 为已经进行第 $i$ 步，前 $i$ 步拿取的物品集合为 $S$ 的最大期望，那么假设拿取第 $j$ 个物品，转移为 $f_{i,S} = \max(f_{i + 1,S}, f_{i+1, S\cap j + a_j})$，设 $b_j,a_j$ 分别代表 $j$ 的依赖，$j$ 的价值，且必须满足 $b_j\subseteq s$，含义是前面的步骤已经达成了集合 $S$，这一步不取；或这一步取 $j$ 才达成了 $S$ 状态。若不满足，只有 $f_{i,S} = f_{i + 1,S}$。那么答案就是 $f_{1,0}$。这样转移一定是正确的，因为只有从 0 出发能到达的状态，逆推才能转移到 0。

时间复杂度：$O(nk2^n)$

#include <bits/stdc++.h>

#define int long long
using namespace std;

using i64 = long long;
using u64 = unsigned long long;
using u32 = unsigned;

using u128 = unsigned __int128;
using i128 = __int128;
using ld = long double;

signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int k, n;
    cin >> k >> n;
    int S = (1 << n) - 1;
    vector<vector<ld>> f(k + 2, vector<ld>(S + 1));
    vector<int> a(n + 1), b(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        while (true) {
            int x;
            cin >> x;
            if (x == 0) {
                break;
            }
            b[i] |= 1ll << (x - 1);
        }
    }
    for (int i = k; i >= 1; i--) {
        for (int s = 0; s <= S; s++) {
            for (int j = 1; j <= n; j++) {
                if ((b[j] & s) != b[j]) {
                    f[i][s] += f[i + 1][s];
                } else {
                    f[i][s] +=
                        max(f[i + 1][s], f[i + 1][s | (1 << (j - 1))] + a[j]);
                }
            }
            f[i][s] /= n;
        }
    }
    cout << fixed << setprecision(6) << f[1][0] << "\n";

    return 0;
}

P2221 [HAOI2012] 高速公路

题意

直线上有 $n$ 个收费点，$n - 1$ 条路径。初始路径的费用都是 0。两种操作：1. 区间修改，给定收费站 $l,r$，它们之间每条路径的费用增加 $a$。2. 区间查询，给定 $l,r$，求在其中随机选择两个不同收费站，它们之间路径的期望花费。

$n,m\le 2\times 10^5$。

题解

很容易往线段树那里靠，考虑每一条路径的贡献，将边权挂在左端点上，给定的 $r$ 减去 1，答案就是 $\dfrac{ans}{\dbinom{r-l+2}{2}}$，重点是求 $ans$。

容易写出式子 $ans = \sum_{i=l}^r\limits v_i(i - l + 1)(r - i + 1) = (r - l + 1 - lr)\sum_{i=l}^r\limits v_i + (r + l)\sum_{i=l}^r\limits iv_i - \sum_{i=l}^r\limits i^2v_i$。

三棵线段树维护 $v_i,iv_i,i^2v_i$ 的区间修改，区间求和即可。

时间复杂度：$O((n + q)\log n)$

#include <bits/stdc++.h>

#define int long long
using namespace std;

using i64 = long long;
using u64 = unsigned long long;
using u32 = unsigned;

using u128 = unsigned __int128;
using i128 = __int128;
using ld = long double;

template <class Info, class Tag>
struct LazySegmentTree {
    int n;
    std::vector<Info> info;
    std::vector<Tag> tag;
    LazySegmentTree() : n(0) {}
    LazySegmentTree(int n_, Info v_ = Info()) { init(n_, v_); }
    template <class T>
    LazySegmentTree(std::vector<T> init_) {
        init(init_);
    }
    void init(int n_, Info v_ = Info()) { init(std::vector(n_ + 1, v_)); }
    template <class T>
    void init(std::vector<T> init_) {
        n = init_.size() - 1;
        info.assign(4 * (n + 1), Info());
        tag.assign(4 * (n + 1), Tag());
        std::function<void(int, int, int)> build = [&](int p, int l, int r) {
            if (l == r) {
                info[p] = Info(init_[l]);
                return;
            }
            int mid = (l + r) / 2;
            build(2 * p, l, mid);
            build(2 * p + 1, mid + 1, r);
            pull(p);
        };
        build(1, 1, n);
    }
    void pull(int p) { info[p] = info[2 * p] + info[2 * p + 1]; }
    void apply(int p, const Tag &v) {
        info[p].apply(v);
        tag[p].apply(v);
    }
    void push(int p) {
        apply(2 * p, tag[p]);
        apply(2 * p + 1, tag[p]);
        tag[p] = Tag();
    }
    void modify(int p, int l, int r, int x, const Info &v) {
        if (l == r) {
            info[p] = v;
            return;
        }
        int mid = (l + r) / 2;
        push(p);
        if (x <= mid) {
            modify(2 * p, l, mid, x, v);
        } else {
            modify(2 * p + 1, mid + 1, r, x, v);
        }
        pull(p);
    }
    void modify(int x, const Info &v) { modify(1, 1, n, x, v); }
    Info rangeQuery(int p, int l, int r, int x, int y) {
        if (l > y || r < x) {
            return Info();
        }
        if (x <= l && r <= y) {
            return info[p];
        }
        push(p);
        int mid = (l + r) / 2;
        return rangeQuery(2 * p, l, mid, x, y) +
               rangeQuery(2 * p + 1, mid + 1, r, x, y);
    }
    Info rangeQuery(int l, int r) { return rangeQuery(1, 1, n, l, r); }
    void rangeApply(int p, int l, int r, int x, int y, const Tag &v) {
        if (l > y || r < x) {
            return;
        }
        if (x <= l && r <= y) {
            apply(p, v);
            return;
        }
        int mid = (l + r) / 2;
        push(p);
        rangeApply(2 * p, l, mid, x, y, v);
        rangeApply(2 * p + 1, mid + 1, r, x, y, v);
        pull(p);
    }
    void rangeApply(int l, int r, const Tag &v) {
        rangeApply(1, 1, n, l, r, v);
    }
    template <class F>
    int findFirst(int p, int l, int r, int x, int y, F &&pred) {
        if (l >= y || r <= x) {
            return -1;
        }
        if (l >= x && r <= y && !pred(info[p])) {
            return -1;
        }
        if (r - l == 1) {
            return l;
        }
        int m = (l + r) / 2;
        push(p);
        int res = findFirst(2 * p, l, m, x, y, pred);
        if (res == -1) {
            res = findFirst(2 * p + 1, m, r, x, y, pred);
        }
        return res;
    }
    template <class F>
    int findFirst(int l, int r, F &&pred) {
        return findFirst(1, 0, n, l, r, pred);
    }
    template <class F>
    int findLast(int p, int l, int r, int x, int y, F &&pred) {
        if (l >= y || r <= x) {
            return -1;
        }
        if (l >= x && r <= y && !pred(info[p])) {
            return -1;
        }
        if (r - l == 1) {
            return l;
        }
        int m = (l + r) / 2;
        push(p);
        int res = findLast(2 * p + 1, m, r, x, y, pred);
        if (res == -1) {
            res = findLast(2 * p, l, m, x, y, pred);
        }
        return res;
    }
    template <class F>
    int findLast(int l, int r, F &&pred) {
        return findLast(1, 0, n, l, r, pred);
    }
};

struct Tag {
    int x = 0;
    Tag() {}
    Tag(int x) : x(x) {}
    void apply(const Tag &t) {
        if (t.x != 0) {
            x += t.x;
        }
    }
};

struct Info1 {
    int x = 0;
    int size = 1;
    Info1() {}
    Info1(int x) : x(x) {}
    void apply(const Tag &t) {
        if (t.x) {
            x += t.x * size;
        }
    }
};

Info1 operator+(const Info1 &a, const Info1 &b) {
    Info1 info;
    info.size = a.size + b.size;
    info.x = a.x + b.x;
    return info;
}

struct Info2 {
    int x = 0;
    int l = 0, r = 0;
    Info2() {}
    Info2(int x, int l, int r) : x(x), l(l), r(r) {}
    void apply(const Tag &t) {
        if (t.x) {
            x += t.x * (l + r) * (r - l + 1) / 2;
        }
    }
};

Info2 operator+(const Info2 &a, const Info2 &b) {
    Info2 info;
    info.l = a.l;
    info.r = b.r;
    info.x = a.x + b.x;
    return info;
}

int sum2(int r) { return r * (r + 1) * (2 * r + 1) / 6; }

struct Info3 {
    int x = 0;
    int l = 0, r = 0;
    Info3() {}
    Info3(int x, int l, int r) : x(x), l(l), r(r) {}
    void apply(const Tag &t) {
        if (t.x) {
            x += t.x * (sum2(r) - sum2(l - 1));
        }
    }
};

Info3 operator+(const Info3 &a, const Info3 &b) {
    Info3 info;
    info.l = a.l;
    info.r = b.r;
    info.x = a.x + b.x;
    return info;
}

signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n, m;
    cin >> n >> m;
    vector<Info2> init2(n + 1);
    vector<Info3> init3(n + 1);
    for (int i = 1; i <= n; i++) {
        init2[i] = Info2(0, i, i);
        init3[i] = Info3(0, i, i);
    }
    LazySegmentTree<Info1, Tag> seg1(n);
    LazySegmentTree<Info2, Tag> seg2(init2);
    LazySegmentTree<Info3, Tag> seg3(init3);
    while (m--) {
        char op;
        cin >> op;
        int l, r;
        cin >> l >> r;
        r--;
        if (op == 'C') {
            int v;
            cin >> v;
            seg1.rangeApply(l, r, Tag(v));
            seg2.rangeApply(l, r, Tag(v));
            seg3.rangeApply(l, r, Tag(v));
        } else {
            int ans = (r - l + 1 - l * r) * seg1.rangeQuery(l, r).x +
                      (r + l) * seg2.rangeQuery(l, r).x -
                      seg3.rangeQuery(l, r).x;
            int d = (r - l + 1) * (r - l + 2) / 2;
            int g = __gcd(ans, d);
            cout << ans / g << "/" << d / g << "\n";
        }
    }

    return 0;
}

P3239 [HNOI2015] 亚瑟王

题意

$n$ 张牌，每次有 $p_i$ 的概率打出。一共进行 $r$ 轮，每轮只能打出一张牌，且必须按顺序依次尝试打出，且打出过的牌不能再被打出。每张牌有伤害 $a_i$，求打出伤害的期望。

$T\le 444,n\le 220,r\le 132,a_i\le 1000$

题解

注意到答案只要能打出第 $i$ 张牌即可，并不需要强制在哪一轮打出。如果我们能求出 $r$ 轮中打出第 $i$ 张牌的概率 $g_i$，就能求出期望 $\sum g_ia_i$。对于第一张牌来说，它被打出的概率是 $1 - (1 - p_1)^{r}$。对于第二张牌来说，如果第一张牌被打出，当轮不能再尝试打出第二张牌，概率是 $1 - (1 - p_2)^{r - 1}$，否则概率同样是 $1 - (1 - p_2)^r$。可以发现，第 $i$ 张牌打出的概率只跟它前面有多少张牌被打出有关。

我们设 $f_{i,j}$ 表示前 $i$ 张牌恰好有 $j$ 张牌被打出，那么如果第 $i$ 张牌被打出，有 $f_{i,j} = f_{i-1,j-1}(1 - (1 - p)^{r-j+1})$，需满足 $j > 0$，如果不被打出，有 $f_{i,j} = f_{i-1,j}(1-p_i)^{r - j}$，需满足 $i\ne j$。

考虑如何计算 $g_i$，我们枚举前 $i - 1$ 张牌被打出了 $j$ 张，那么第 $i$ 张牌被打出的概率就是 $\sum_{j=0}^{i-1}\limits f_{i-1,j}(1 - (1 - p_i)^{r-j})$。

时间复杂度：$O(Tnr)$

#include <bits/stdc++.h>

#define int long long
using namespace std;

using i64 = long long;
using u64 = unsigned long long;
using u32 = unsigned;

using u128 = unsigned __int128;
using i128 = __int128;
using ld = long double;

template <class T>
T power(T a, int b) {
    T res = 1;
    while (b) {
        if (b & 1) {
            res = res * a;
        }
        a = a * a;
        b /= 2;
    }
    return res;
}

void solve() {
    int n, r;
    cin >> n >> r;
    vector<ld> p(n + 1), a(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> p[i] >> a[i];
    }
    if (r == 0) {
        cout << 0 << "\n";
        return;
    }
    vector<vector<ld>> pow(n + 1, vector<ld>(r + 1));
    for (int i = 1; i <= n; i++) {
        pow[i][0] = 1.;
        for (int j = 1; j <= r; j++) {
            pow[i][j] = pow[i][j - 1] * (1 - p[i]);
        }
    }
    vector<vector<ld>> f(n + 1, vector<ld>(n + 1));
    f[0][0] = 1;
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= min(i, r); j++) {
            if (j) {
                f[i][j] += f[i - 1][j - 1] * (1 - pow[i][r - j + 1]);
            }
            if (i != j) {
                f[i][j] += f[i - 1][j] * pow[i][r - j];
            }
        }
    }
    vector<ld> g(n + 1);
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= min(r, i - 1); j++) {
            g[i] += f[i - 1][j] * (1 - pow[i][r - j]);
        }
    }
    ld ans = 0;
    for (int i = 1; i <= n; i++) {
        ans += g[i] * a[i];
    }
    cout << fixed << setprecision(10) << ans << "\n";
}

signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int t;
    cin >> t;
    while (t--) {
        solve();
    }

    return 0;
}

ABC 423 F

题意

给定 $n$ 个数 $a_i$ 和 $m$，求在年份 $1$ 到 $y$ 之间有多少年份恰好是 $n$ 个数其中 $m$ 个的倍数。

$m \le n\le 20, y,a_i\le 10^{18}$

题解

二项式反演。

根据数据范围容易想到枚举每一个子集，如果子集大小为 $m$ 就求它们的 lcm，答案贡献 $\lfloor\dfrac{y}{lcm}\rfloor$，但是显然这样会算重，考虑容斥。

设 $f(S)$ 满足是集合 $S$ 中的元素的年份的数量，$g(S)$ 是恰好满足是集合 $S$ 中元素的年份数量，那么有 $f(S) = \sum_{S\subseteq T}\limits \dbinom{|T|}{|S|}g(T)$，即 $g(S) = \sum_{S\subseteq T}\limits(-1)^{|T|-|S|}\dbinom{|T|}{|S|}f(S)$。答案就是 $\sum_{|S| = m}\limits g(S) = \sum_{|S| = m}\limits\sum_{S\subseteq T}\limits(-1)^{|T|-|S|}\dbinom{|T|}{|S|}f(T) = \sum_{|T|\ge m}\limits(-1)^{|T| - m}\dbinom{|T|}{m}f(T)$。

注意会爆long long。

时间复杂度：$O(n2^n\log m)$

#include <bits/stdc++.h>

#define int long long
using namespace std;

using i64 = long long;
using u64 = unsigned long long;
using u32 = unsigned;

using u128 = unsigned __int128;
using i128 = __int128;
using ld = long double;

i128 gcd(i128 x, i128 y) { return y == 0 ? x : gcd(y, x % y); }

i128 lcm(i128 x, i128 y) {
    i128 g = gcd(x, y);
    return x / g * y;
}

signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n, m, y;
    cin >> n >> m >> y;

    vector<vector<int>> binom(n + 1, vector<int>(n + 1));
    for (int i = 1; i <= n; i++) {
        binom[i][0] = binom[i][i] = 1;
        for (int j = 1; j < i; j++) {
            binom[i][j] = binom[i - 1][j - 1] + binom[i - 1][j];
        }
    }

    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    const int S = (1 << n) - 1;
    i128 ans = 0;
    for (int i = 0; i <= S; i++) {
        int sz = __builtin_popcountll(i);
        if (sz < m) {
            continue;
        }
        i128 Lcm = 1;
        for (int j = 1; j <= n; j++) {
            if (i >> (j - 1) & 1) {
                Lcm = lcm(Lcm, (i128)a[j]);
                if (Lcm > y) {
                    Lcm = y + 1;
                    break;
                }
            }
        }
        ans += (i128)(y / Lcm) * (i128)((sz - m) & 1 ? -1 : 1) * binom[sz][m];
    }
    cout << (int)ans << "\n";

    return 0;
}

ABC 423 G

题意

给定两个数 $k$ 和 $s$，求一个最小的数，其子串包含 $s$ 且是 $k$ 的倍数。

$k\le 10^9,|s|\le 5\times 10^5$

题解

每隔 $k$ 个数，一定会有一个数是 $k$ 的倍数。设 $sz$ 为 $k$ 的位数，我们将 $s$ 前后共拓展 $sz$ 位，一定能找到满足条件的数。

考虑枚举前面拓展 $xx$ 位，后面拓展 $yy$ 位，前后分别添加数字 $x,y$。我们有两种暴力：

枚举 $x$，

P3750 [六省联考 2017] 分手是祝愿

题意

$n$ 个灯，开关编号为 $1$ 到 $n$，每按下一个开关，这个开关的所有因数编号都会改变灯的状态。给定初始状态，随机选择开关，直到所有灯都灭掉。如果当前局面可以通过小于等于 $k$ 次操作使得所有灯都灭掉，就不需要随机，使用最优方法。求操作次数的期望乘上 $n$ 的阶乘，模 100003。

$n\le 10^5$

题解

最优的策略一定是从大到小，如果有灯亮着就熄灭，可以 $O(n\log n)$ 预处理每个数的因数求出最优的操作次数。同时，我们注意到每个开关最多被操作一次，这样才是最优的。

如果我们设 $f_i$ 表示将 $i$ 盏灯熄灭的期望，是存在后效性的，因为选择一个开关可能导致很多灯都熄灭。考虑期望，设 $f_i$ 表示有 $i$ 个选择变为有 $i -1 $ 个正确选择的期望操作次数（也就是说，这 $i$ 个开关我们只要按了，就能到 $i - 1$ 的状态）。那么有 $f_i = \dfrac{i}{n} + \dfrac{n - i}{n}\times (1 + f_i + f_{i + 1})$，可以推出 $f_{i} = 1 + \dfrac{(n - i)(f_{i + 1}+1)}{i}$。初始状态 $f_n = 1$，代表有 $n$ 个选择的话，按哪一个都能到 $f_{n - 1}$。那么，设我们最优的策略需要 $cnt$ 步，如果 $cnt\le k$，答案就是 $k$。否则，答案就是 $f_{cnt} + f_{cnt - 1} + \cdots f_{k + 1} + k$。需要乘上阶乘。

时间复杂度：$O(n\log n)$

#include <bits/stdc++.h>

#define int long long
using namespace std;

using i64 = long long;
using u64 = unsigned long long;
using u32 = unsigned;

using u128 = unsigned __int128;
using i128 = __int128;
using ld = long double;

template <class T>
constexpr T power(T a, i64 b) {
    T res = 1;
    for (; b; b /= 2, a *= a) {
        if (b % 2) {
            res *= a;
        }
    }
    return res;
}

constexpr i64 mul(i64 a, i64 b, i64 p) {
    i64 res = a * b - i64(1.L * a * b / p) * p;
    res %= p;
    if (res < 0) {
        res += p;
    }
    return res;
}
template <int P>
struct MInt {
    int x;
    constexpr MInt() : x{} {}
    constexpr MInt(i64 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 power(*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 std::istream &operator>>(std::istream &is, MInt &a) {
        i64 v;
        is >> v;
        a = MInt(v);
        return is;
    }
    friend constexpr std::ostream &operator<<(std::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();

constexpr int P = 100003;
using Z = MInt<P>;  // 静态模数，题目给定模数
using D = MInt<0>;  // 动态模数，可以 D::setMod(x) 改变

signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n, k;
    cin >> n >> k;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    vector<vector<int>> factor(n + 1);
    for (int i = 1; i <= n; i++) {
        for (int j = i; j <= n; j += i) {
            factor[j].push_back(i);
        }
    }
    Z ans = 0;
    int cnt = 0;
    for (int i = n; i >= 1; i--) {
        if (a[i]) {
            cnt++;
            for (auto x : factor[i]) {
                a[x] ^= 1;
            }
        }
    }
    if (cnt <= k) {
        ans = cnt;
        for (int i = 1; i <= n; i++) {
            ans *= i;
        }
        cout << ans << "\n";
        return 0;
    }
    vector<Z> f(n + 1);
    f[n] = 1;
    for (int i = n - 1; i >= 1; i--) {
        f[i] = 1 + Z(n - i) / i * (f[i + 1] + 1);
    }
    for (int i = cnt; i > k; i--) {
        ans += f[i];
    }
    ans += k;
    for (int i = 1; i <= n; i++) {
        ans *= i;
    }
    cout << ans << "\n";

    return 0;
}

P4284 [SHOI2014] 概率充电器

题意

给定一棵树，每个节点都有 $q_i$ 的概率充电，每条边也有 $p_i$ 的概率导电。求充电的节点的数量的期望。

$n\le 5\times 10^5$

题解

第一眼看上去是树形 + 概率 dp，且期望就是每个点能充上电的概率之和。如果直接设 $f_i$ 是第 $i$ 个节点充上电的概率，这样的话每个节点都会跟它的儿子、父亲存在一个方程，高斯消元求解的话是 $O(n^3)$ 的，不能接受。

考虑正难则反。考虑到每个点会受到父亲和儿子的影响，我们想在 DFS 时只考虑一边的影响。不妨设 $f_i$ 是 $i$ 节点自身充不上电或因为儿子而充不上电的概率，那么有 $f_i = (1 - q_i)\prod_{v\in i}\limits(f_v + (1 - f_v)(1 - w_{i,v}))$。这样进行一次 DFS 就能求出所有 $f_i$。

再考虑父亲的影响，设 $g_i$ 是 $i$ 因为父亲充不上电的概率，那么 $g_{root} = 1$，且子树外包括两种情况：

在 $u$ 的父亲 $fa$ 之外的部分，贡献就是 $g_{fa}$
在 $fa$ 的子树除掉 $u$ 所在的子树的部分，贡献可以通过 $f_{fa}$ 除掉 $f_u$ 的贡献，即 $\dfrac{f_{fa}}{f_u + (1 - f_u)(1 - w_{u,fa})}$。

那么，设 $p = g_{fa}\times \dfrac{f_{fa}}{f_u + (1 - f_u)(1 - w_{u,fa})}$ 表示 $u$ 的父亲没电的概率，因此 $g_u =p + (1 -p)(1 - w_{u,fa}) $。

因此，答案就是 $\sum (1 - f_ig_i)$。

时间复杂度：$O(n)$

#include <bits/stdc++.h>

#define int long long
using namespace std;

using i64 = long long;
using u64 = unsigned long long;
using u32 = unsigned;

using u128 = unsigned __int128;
using i128 = __int128;
using ld = long double;

signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    constexpr ld eps = 1e-8;

    int n;
    cin >> n;
    vector<vector<array<int, 2>>> adj(n + 1);
    vector<int> q(n + 1);
    for (int i = 1; i < n; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
    }
    for (int i = 1; i <= n; i++) {
        cin >> q[i];
    }
    vector<ld> f(n + 1), g(n + 1);
    auto dfs1 = [&](this auto &&dfs1, int x, int fa) -> void {
        f[x] = 1.l - 1.l * q[x] / 100;
        for (auto [y, w] : adj[x]) {
            if (y == fa) {
                continue;
            }
            dfs1(y, x);
            f[x] *= f[y] + (1 - f[y]) * (1 - w / 100.l);
        }
    };
    dfs1(1, 0);
    g[1] = 1.l;
    auto dfs2 = [&](this auto &&dfs2, int x, int fa) -> void {
        for (auto [y, w] : adj[x]) {
            if (y == fa) {
                continue;
            }
            ld d = f[y] + (1 - f[y]) * (1 - w / 100.l);
            if (abs(d) <= eps) {
                g[y] = g[x];
            } else {
                ld P = f[x] / d * g[x];
                g[y] = P + (1 - P) * (1 - w / 100.l);
            }
            dfs2(y, x);
        }
    };
    dfs2(1, 0);
    ld ans = 0;
    for (int i = 1; i <= n; i++) {
        ans += 1 - f[i] * g[i];
    }
    cout << fixed << setprecision(6) << ans << "\n";

    return 0;
}

P5249 [LnOI2019] 加特林轮盘赌

题意

$n$ 个人轮流开枪，每个人射中自己的概率都是 $P_0$，求第 $k$ 个人获胜的概率。

$n\le 10^4$

题解

这 $n$ 个人是环形的，轮流开枪，设 $f_{i,j}$ 表示还剩 $i$ 个人，第一个人开枪，第 $j$ 个人存活下来的概率。

我们发现是可以递推的：$f_{i,j} = P_0f_{i-1,j-1} + (1 - P_0)f_{i,j-1}$ 第一个人开枪有 $P_0$ 的概率打中自己，此时每个人编号前移，变为 $f_{i-1,j-1}$，否则相当于第一个人去了最后，其余人编号前移，即 $f_{i,j-1}$，初始状态是 $f_{1,1} = 1$ 必胜，且满足 $\sum_{j=1}^if_{i,j} = 1$。直接高斯消元的话每一行 $f_i$ 都是 $O(n^3)$ 的，整体是 $O(n^4)$，需要优化。

注意到 $P_0f_{i-1,j-1}$ 是已经求出来的常数，且 $f_{i,j}$ 都可以按照公式递推到 $f_{i,1}$，不妨建立一个关于 $f_{i,1}$ 的方程，就能求出其余 $f_{i,j}$ 了。

设 $af_{i,1} + b = 1$，那么有 $\begin{cases}a=\sum_{j=0}^{i-1}\limits(1-p_0)^j\\b=p_0\sum_{j=1}^{i-1}\limits\sum_{k=0}^{i-j-1}\limits(1-p_0)^kf_{i-1,j}\end{cases}$。

预处理幂的前缀和，时间复杂度：$O(n^2)$。

#include <bits/stdc++.h>

#define int long long
using namespace std;

using i64 = long long;
using u64 = unsigned long long;
using u32 = unsigned;

using u128 = unsigned __int128;
using i128 = __int128;
using ld = double;

signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    ld p;
    int n, k;
    cin >> p >> n >> k;
    cout << fixed << setprecision(10);
    if (p == 0) {
        if (k == 1) {
            cout << 1.l << "\n";
            return 0;
        }
        cout << 0.l << "\n";
        return 0;
    }
    vector<vector<ld>> f(2, vector<ld>(n + 1));
    f[1][1] = 1.l;
    vector<ld> pow(n + 1), prepow(n + 1);
    pow[0] = prepow[0] = 1.l;
    for (int i = 1; i <= n; i++) {
        pow[i] = pow[i - 1] * (1 - p);
        prepow[i] = prepow[i - 1] + pow[i];
    }
    int now = 1, lst = 0;
    for (int i = 2; i <= n; i++) {
        lst = now;
        now ^= 1;
        ld a = prepow[i - 1];
        ld b = 0;
        for (int j = 1; j <= i - 1; j++) {
            b += prepow[i - j - 1] * f[lst][j];
        }
        b *= p;
        f[now][1] = (1.l - b) / a;
        for (int j = 2; j <= i; j++) {
            f[now][j] = p * f[lst][j - 1] + (1 - p) * f[now][j - 1];
        }
    }
    cout << f[now][k] << "\n";

    return 0;
}