题解 | 练习赛 Round 149

A.调色题Ⅰ

假设我们将原始颜色编号 $a_1, a_2, \dots, a_n$ 从小到大排序，得到序列 $A = \{a'_1, a'_2, \dots, a'_n\}$ ，其中 $a'_i \le a'_{i+1}$ 。

设最终变换后的颜色序列为 $B = \{b_1, b_2, \dots, b_n\}$ 。为了使总代价 $S = \sum\limits_{i=1}^n (b_i - a'_i)$ 最小，且满足 $b_i$ 互不相同及 $b_i \ge a'_i$ 的约束，最优策略应保证 $b_i$ 的相对顺序与 $a'_i$ 一致，即 $b_1 < b_2 < \dots < b_n$ 。

对于序列中的每一个位置 $i$ ，其最终颜色 $b_i$ 必须满足两个限制条件：

$b_i \ge a'_i$ 。
对于 $i > 1$ ，必须满足 $b_i > b_{i-1}$ 。

综上，为了使 $b_i$ 尽可能小，我们可以得到递推关系：

b_i = \max(a'_i, b_{i-1} + 1)

最终的最小操作总次数即为： $\sum_{i=1}^n\limits (b_i - a'_i)$ 。

时间复杂度： $\mathcal{O}(n \log {n})$ 。

void solve() {
    int n;
    cin >> n;
    i64 ans = 0;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    sort(a.begin() + 1, a.end());
    for (int i = 1; i <= n; i++) {
        ans += max(a[i - 1] + 1 - a[i], 0);
        a[i] = max(a[i - 1] + 1, a[i]);
    }
    cout << ans << "\n";
    return;
}

B.调色题Ⅰ

定义打完一轮后的总能量净变化为：

W = \sum_{i=1}^n b_i - a_i

定义 $P_i$ 为在第一轮中，打出编号为 $i$ 的牌之前的能量值：

$P_1 = x$
对于 $2 \le i \le n$ ， $P_i = x + \sum\limits_{j=1}^{i-1} w_j$

首先判断 $\texttt{Infinity}$ 的情况，必须满足两个限制条件：
1. 能够成功打出前 $n$ 张牌，即对于所有 $1 \le i \le n$ ，均满足 $P_i \ge a_i$ 。
2. 一轮后的能量净变化 $W \ge 0$ 。
对于编号为 $i$ 的牌，其能够被成功打出的最大轮数 $k_i$ 满足：
$k \cdot (-W) \le P_i - a_i \implies k_i = \left\lfloor \frac{P_i - a_i}{-W} \right\rfloor$
这表示该编号的牌在最后一次可以被打出的是第 $k_i$ 轮，所以答案小于 $(k_i + 1) * n + i$ 。此时，它对总出牌数的贡献上限为 $(k_i + 1) \times n + i - 1$ ：

最终的答案即 $\min\limits_{1 \le i \le n} \{ (k_i + 1) \times n + i - 1 \}$ ：

时间复杂度： $\mathcal{O}(n)$ 。

void solve() {
    int n;
    i64 x;
    cin >> n >> x;
    i64 res = x;
    vector<int> a(n + 1), b(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    for (int i = 1; i <= n; i++) {
        cin >> b[i];
    }
    for (int i = 1; i <= n; i++) {
        res -= a[i];
        if (res >= 0) {
            res += b[i];
        } else {
            cout << i - 1 << "\n";
            return;
        }
    }
    i64 ch = x - res;
    if (ch <= 0) {
        cout << "Infinity\n";
        return;
    }
    i64 ans = 1e18;
    for (int i = 1; i <= n; i++) {
        i64 sum = (x - a[i]) / ch;
        ans = min(ans, (sum + 1) * n + i - 1);
        x += b[i] - a[i];
    }
    cout << ans << "\n";
    return;
}

C.调色题Ⅱ

考虑对问题进行建图求解。我们将每一个数值视作图中的一个节点。对于初始数组中的每一个 $a_i$ ，它可以经过一次调色操作变为 $a_i' = \gcd(a_i, b_j)$ ，这等价于在图上存在一条从节点 $a_i$ 连向节点 $a_i'$ 的有向边，且边权为 $1$ 。

题目要求所有方格最终的颜色编号完全相同，这等价于我们要寻找一个全局目标节点 $T$ ，使得所有的初始起点 $a_i$ 都能到达 $T$ ，且使得总代价 $\sum \limits_{i = 1}^n \text{dist}(a_i, T)$ 达到最小。

考虑到任何数通过 $\gcd$ 操作产生的状态必然是该数自身的约数，所以真正有用的节点仅限于所有初始颜色 $a_i$ 的约数集合。设值域上限为 $W$ ，单个数的最大约数个数记为 $d(W)$ ，则总的有效节点数最多为 $n \times d(W)$ 个。我们只需要在这些节点构成的空间上运行 BFS（广度优先搜索）求解最短路即可。

时间复杂度： $\mathcal{O}(n \cdot m \cdot d(W) \cdot \log{W})$ 。

constexpr int N = 5e5;
void solve() {
    int n, m;
    cin >> n >> m;
    vector<int> a(n + 1), b(m + 1);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    for (int i = 1; i <= m; i++) {
        cin >> b[i];
    }
    vector<int> dis(N + 1, 1e9);
    vector<int> sum(N + 1), cnt(N + 1);
    for (int i = 1; i <= n; i++) {
        vector<int> vec;
        queue<int> q;
        q.push(a[i]);
        dis[a[i]] = 0;
        cnt[a[i]]++;
        while (!q.empty()) {
            int x = q.front();
            q.pop();
            vec.push_back(x);
            for (int j = 1; j <= m; j++) {
                int gd = gcd(x, b[j]);
                if (dis[gd] == 1e9) {
                    dis[gd] = dis[x] + 1;
                    sum[gd] += dis[gd];
                    cnt[gd]++;
                    q.push(gd);
                }
            }
        }
        for (auto x : vec) {
            dis[x] = 1e9;
        }
    }
    int ans = 1e9;
    for (int i = 1; i <= N; i++) {
        if (cnt[i] == n) {
            ans = min(ans, sum[i]);
        }
    }
    cout << (ans == 1e9 ? -1 : ans) << "\n";
    return;
}

D.鼠鼠题

只要当前攻击力 $x$ 足以击败区间左侧或右侧的 Jerry，贪心地扩张区间显然是最优策略。

通过 ST 表结合二分查找，在每一轮中快速找到向左和向右满足 $\max \limits _{L \leq i \leq R} \{a_i\} \le x$ 的最远可达边界。

这种扩张过程最多只会持续 $\log W$ 轮， $W$ 为值域。若当前攻击力 $x$ 因为小于左侧或右侧某个位置的体力值 $a_{obst}$ 而停止扩张（即 $x < a_{obst}$ ），那么当新的攻击力 $x' \ge a_{obst}$ 时，新的攻击力 $x''$ 满足：

x'' = x' + a_{obst}

由于 $x' \ge a_{obst}$ ，且 $a_{obst} > x$ ，可以得出：

x'' > 2x

这意味着，每一次二分查找都会使攻击力至少翻倍，最多只会二分查找 $\log W$ 次。

时间复杂度： $\mathcal{O}(n \log{W} + q\log{n}\log{W})$ 。

void solve() {
    int n, q;
    cin >> n >> q;
    vector<int> a(n + 1);
    vector<i64> pre(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        pre[i] = pre[i - 1] + a[i];
    }
    ST<int> st(a);
    while (q--) {
        i64 pos, x;
        cin >> pos >> x;
        if (a[pos] > x) {
            cout << 0 << "\n";
            continue;
        }
        x += a[pos];
        int L = pos, R = pos;
        bool flag = 1;
        while (flag) {
            flag = 0;
            if (L != 1) {
                int l = 1, r = L - 1;
                while (l < r) {
                    int mid = l + r >> 1;
                    if (st.range(mid, L - 1) > x) {
                        l = mid + 1;
                    } else {
                        r = mid;
                    }
                }
                if (st.range(l, L - 1) <= x) {
                    x += pre[L - 1] - pre[l - 1];
                    L = l;
                    flag = 1;
                }
            }
            if (R != n) {
                int l = R + 1, r = n;
                while (l < r) {
                    int mid = l + r + 1 >> 1;
                    if (st.range(R + 1, mid) > x) {
                        r = mid - 1;
                    } else {
                        l = mid;
                    }
                }
                if (st.range(R + 1, l) <= x) {
                    x += pre[l] - pre[R];
                    R = l;
                    flag = 1;
                }
            }
        }
        cout << R - L + 1 << "\n";
    }
    return;
}

E.代码题

考虑转化成求期望 $E \times n!$ 。

设 $dp[i]$ 表示当前能触发更新的集合为 $[i,\cdots,n]$ 时，后续期望的更新次数。

枚举第一次更新的元素 $j \in [i, n]$ ，由于每个元素被选中的概率均为 $\frac{1}{n - i + 1}$ ，转移方程如下：

\begin{aligned} dp[i] &= \frac{1}{n - i + 1} \sum_{j=i}^n (1 + dp[k \cdot j + 1]) \\ &= 1 + \frac{1}{n - i + 1} \sum_{j=i}^n dp[k \cdot j + 1] \end{aligned}

注意到只有当 $k \cdot j + 1 \le n$ 时，状态才会有有效的后续转移。因此，我们只需要计算 $i$ 在 $1$ 到 $\lfloor \frac{n-1}{k} \rfloor$ 范围内的 $dp[i]$ 值。当 $i > \lfloor \frac{n-1}{k} \rfloor$ 时， $dp[i] = 1$ 。

对于转移方程的这部分求和 $F(i) = \sum\limits_{j=i}^n dp[k \cdot j + 1]$ ，有 $F(i) = F(i + 1) + dp[k \cdot i + 1]$ ，使用一个变量维护即可。

时间复杂度： $\mathcal{O}(n \log{n})$ 。

void solve() {
    int n;
    cin >> n;
    i64 ans = 1;
    for (int i = 1; i < n; i++) {
        int m = (n - 1) / i;
        vector<i64> dp(m + 2);
        i64 suf = 0;
        for (int j = m; j >= 1; j--) {
            if (i * j + 1 <= m) {
                suf = (suf + dp[i * j + 1]) % mod;
            } else if (i * j + 1 <= n) {
                suf = (suf + 1) % mod;
            }
            dp[j] = (1 + comb.inv(n - j + 1) * suf) % mod;
        }
        ans = (ans + dp[1]) % mod;
    }
    ans = ans * comb.fac(n) % mod;
    cout << ans << "\n";
    return;
}

F.数数题

可以观察到，每次操作后的结果只与当前操作数 $a_i$ 的奇偶性有关。记序列 $a$ 中奇数有 $x$ 个，偶数有 $y$ 个。

设 $G(a)$ 为某个特定序列 $a$ 操作后结果为奇数的操作序列数量， $F(a)$ 为操作后结果为偶数的操作序列数量。

定义 $\text{odd}(x, y)$ 为 $x$ 个奇数和 $y$ 个偶数的所有排列情况的 $G(a)$ 之和；

定义 $\text{even}(x, y)$ 为 $x$ 个奇数和 $y$ 个偶数的所有排列情况的 $F(a)$ 之和。

由于同奇偶性的数字之间可以任意互换位置，最终答案为 $\text{even}(x, y) \times x! \times y!$ 。

思路一

考虑先求出结果为奇数的方案数，再用总方案数进行容斥。

考虑最后一次操作和最后一个数 $a_n$ 的奇偶性：

如果最后一个数 $a_n$ 是奇数：无论前 $n-1$ 个数计算出的结果 $x_{n-1}$ 是奇是偶，我们总有且仅有一种操作（加法或乘法）能让最终结果变为奇数。因此，只要确定最后一个数是奇数，前面的排列和操作方式可以任意选择。这部分的方案数为 $2^{n - 2} \times \binom{n - 1}{y}$ 。
如果最后一个数 $a_n$ 是偶数：要让最终结果为奇数，最后一次操作必须使用加法，且前面的计算结果 $x_{n-1}$ 必须是奇数。这等价于在少了一个偶数的序列中求奇数结果的方案数，即 $\text{odd}(x, y - 1)$ 。

所以有递推式： $\text{odd}(x, y) = 2^{n - 2} \times \binom{n - 1}{y} + \text{odd}(x, y - 1)$ ，不断展开递推即可。

思路二

对于边界情况 $x = 0$ 或者 $y = 0$ 有：

\begin{aligned} \text{odd}(1, 0) = 1, \text{even}(1, 0) = 0\\ \text{odd}(x, 0) = 2^{x - 2}, \text{even}(x, 0) = 2^{x - 2} \\ \text{odd}(0, y) = 0, \text{even}(0, y) = 2^{y - 1} \end{aligned}

对于 $1 \leq x$ 且 $1 \leq y$ ，考虑状态转移，有如下递推：

\begin{aligned} \text{odd}(x, y) &= \text{odd}(x - 1, y) + \text{even}(x - 1, y) + \text{odd}(x, y - 1) \\ \text{even}(x, y) &= \text{odd}(x - 1, y) + \text{even}(x - 1, y) + \text{odd}(x, y - 1) + 2 \times \text{even}(x, y - 1) \end{aligned}

为了解出上述递推，设以下辅助变量：

\begin{aligned} \text{sum}(x, y) &= \text{odd}(x, y) + \text{even}(x, y)\\ &= 2^{x + y - 1} \times \binom{x + y}{x}\\ \text{diff}(x, y) &= \text{even}(x, y) - \text{odd}(x, y) \end{aligned}

将原递推式代入可得 $\text{diff}$ 的递推关系：

\begin{aligned} \text{diff}(x, y) &= \text{even}(x, y) - \text{odd}(x, y) \\ &= 2 \times \text{even}(x, y - 1) \end{aligned}

又因为和差关系：

\text{odd}(x, y) = \frac{\text{sum}(x, y) - \text{diff}(x, y)}{2}, \text{even}(x, y)= \frac{\text{sum}(x, y) + \text{diff}(x, y)}{2}

将 $\text{even}(x, y - 1)$ 展开代入 $\text{diff}(x, y)$ 中，可以推导出：

\begin{aligned} \text{diff}(x, y) &= \text{sum}(x, y - 1) + \text{diff}(x, y - 1)\\ &= \sum_{i = 0}^{y - 1} \text{sum}(x, i) + \text{diff}(x, 0)\\ &= \sum_{i = 0}^{y - 1} 2^{x + i - 1} \binom{x + i}{i} - [x == 1] \end{aligned}

对于 $1 \leq x$ 且 $1 \leq y$ ，进而解得 $\text{odd}(x, y)$ 和 $\text{even}(x, y)$ ：

\begin{aligned} \text{odd}(x, y) &= 2^{x + y - 2} \times \binom{x + y}{x} - \sum_{i = 0}^{y - 1} 2^{x + i - 2} \binom{x + i}{i} + \frac{[x == 1]}{2}\\ \text{even}(x, y) &= \sum_{i = 0}^{y} 2^{x + i - 2} \binom{x + i}{i} - \frac{[x == 1]}{2} \end{aligned}

时间复杂度： $\mathcal{O}(n)$ 。

void solve() {
    int n;
    cin >> n;
    int odd = 0, even = 0;
    for (int i = 1; i <= n; i++) {
        int x;
        cin >> x;
        if (x & 1) {
            odd++;
        } else {
            even++;
        }
    }
    if (odd == 0) {
        cout << qpow(2, even - 1) * comb.fac(even) % mod << "\n";
        return;
    }
    i64 ans = (odd == 1 ? mod - inv(2) : 0);
    for (int i = 0; i <= even; i++) {
        ans = (ans + qpow(2, odd + i - 2) * comb(odd + i, i)) % mod;
    }
    ans = ans * comb.fac(odd) % mod * comb.fac(even) % mod;
    cout << ans << "\n";
    return;
}

G.猜猜题

任意两个区间要么相离，要么存在包含关系，我们可以将每个区间 $u$ 挂载在其所包含的最小区间 $v$ 下，从而构建出森林，考虑进行树上dp。

设 $dp[u][\text{state}][i]$ 表示在以 $u$ 为根的子树中，共选择了 $i$ 个区间，且区间 $u$ 的确定状态为 $\text{state}$ ：

$dp[u][0][i]$ ：区间 $u$ 内所有变量均已知，选择 $i$ 个区间的方案数。
$dp[u][1][i]$ ：区间 $u$ 内恰好有一个变量未知，选择 $i$ 个区间的方案数。

对于节点 $u$ 的所有子节点 $v$ ，转移如下：

dp[u][0] = \prod_{v} dp[v][0]\\ dp[u][1] = \sum_{v} \left( dp[v][1] \prod_{w \neq v} dp[w][0] \right)

然后考虑是否选择节点 $u$ ：

若 $\sum \limits_v r_v -l _v + 1 = r_u - l_u + 1$ 此时选择 $u$ 不会提供额外信息，而不选 $u$ 仍能保持状态：

\begin{aligned}dp[u][0] &= dp[u][0] \cdot (x + 1) + dp[u][1] \cdot x\\ dp[u][1] &= dp[u][1]\end{aligned}

若 $\sum \limits_v r_v -l _v + 1 = r_u - l_u$ 此时必须选择 $u$ ：

\begin{aligned}dp[u][0] &= dp[u][0] \cdot x\\ dp[u][1] &= dp[u][0]\end{aligned}

设 $f(i) = dp[\text{root}][0][i]$ 为恰好在选择 $i$ 个区间时完全确定数组的方案数。由于每次抽取是等概率的，总的抽取方案数为 $\binom{m}{i}$ 。

记 $P(X \le i) = \frac{f(i)}{\binom{m}{i}}$ 为在 $i$ 次询问内完成确定的概率。则 Alice 恰好在第 $i$ 次询问后停止的概率为：

P(X = i) = P(X \le i) - P(X \le i-1)

最终期望为：

E(X) = \sum\limits_{i=1}^{m} i \cdot P(X=i)

注意判断无解的情况。

时间复杂度： $\mathcal{O}(n + m^2)$ 。

vector<i64> operator*(const vector<i64> &a, const vector<i64> &b) {
    vector<i64> c(a.size() + b.size() - 1, 0);
    for (int i = 0; i < a.size(); ++i) {
        for (int j = 0; j < b.size(); ++j) {
            c[i + j] = (c[i + j] + a[i] * b[j]) % mod;
        }
    }
    return c;
}
vector<i64> operator+(const vector<i64> &a, const vector<i64> &b) {
    vector<i64> c(max(a.size(), b.size()), 0);
    for (int i = 0; i < a.size(); ++i) {
        c[i] = (c[i] + a[i]) % mod;
    }
    for (int i = 0; i < b.size(); ++i) {
        c[i] = (c[i] + b[i]) % mod;
    }
    return c;
}
void solve() {
    int n, m;
    cin >> n >> m;
    vector<pair<int, int>> a(m);
    for (auto &[l, r] : a) {
        cin >> l >> r;
    }
    ranges::sort(a, [](auto x, auto y) {
        x.second = -x.second;
        y.second = -y.second;
        return x < y;
    });
    vector<vector<int>> tree(m);
    vector<int> vis(m);
    stack<int> stk;
    for (int i = 0; i < m; ++i) {
        while (!stk.empty() && a[stk.top()].second < a[i].first) {
            stk.pop();
        }
        if (!stk.empty()) {
            tree[stk.top()].push_back(i);
        }
        stk.push(i);
    }
    bool flag = 0;
    auto dfs = [&](auto dfs, int u) -> pair<vector<i64>, vector<i64>> {
        vis[u] = 1;
        auto [l, r] = a[u];
        int len = r - l + 1, sum = 0;
        for (auto v : tree[u]) {
            auto [l, r] = a[v];
            sum += r - l + 1;
        }
        vector<i64> f0{1}, f1{0};
        for (auto v : tree[u]) {
            auto [g0, g1] = dfs(dfs, v);
            f1 = f1 * g0 + f0 * g1;
            f0 = f0 * g0;
        }
        if (len == sum) {
            f0 = f0 * vector<i64>{1, 1} + f1 * vector<i64>{0, 1};
        } else if (len == sum + 1) {
            f1 = f0;
            f0 = f0 * vector<i64>{0, 1};
        } else {
            flag = 1;
        }
        return make_pair(f0, f1);
    };
    vector<i64> res{1};
    i64 sum = 0;
    for (int i = 0; i < m; i++) {
        if (vis[i]) {
            continue;
        }
        auto [l, r] = a[i];
        sum += r - l + 1;
        auto [f0, f1] = dfs(dfs, i);
        res = res * f0;
    }
    if (sum != n || flag) {
        cout << -1 << "\n";
        return;
    }
    i64 ans = 0;
    for (int i = m; i >= 1; i--) {
        res[i] = res[i] * inv(comb(m, i)) % mod;
    }
    for (int i = m; i >= 1; i--) {
        res[i] = (res[i] - res[i - 1] + mod) % mod;
    }
    for (int i = 0; i <= m; i++) {
        ans = (ans + i * res[i]) % mod;
    }
    cout << ans << "\n";
    return;
}

组合数

constexpr i64 mod = 998244353;

i64 qpow(i64 a, i64 b) {
    i64 res = 1;
    while (b) {
        if (b & 1) {
            res = res * a % mod;
        }
        a = a * a % mod;
        b >>= 1;
    }
    return res;
}
i64 inv(i64 a) { return qpow(a, mod - 2); }
struct Comb {
    vector<i64> _fac, _invfac;
    int n;
    Comb() : n(0), _fac(1, 1), _invfac(1, 1) {}
    Comb(int n) : Comb() { init(n); }
    void init(int m) {
        if (m <= n) return;
        _fac.resize(m + 1);
        _invfac.resize(m + 1);
        for (int i = n + 1; i <= m; i++) {
            _fac[i] = _fac[i - 1] * i % mod;
        }
        _invfac[m] = ::inv(_fac[m]);
        for (int i = m; i > n; i--) {
            _invfac[i - 1] = _invfac[i] * i % mod;
        }
        n = m;
    }
    i64 fac(int m) {
        if (m > n) init(2 * m);
        return _fac[m];
    }
    i64 invfac(int m) {
        if (m > n) init(2 * m);
        return _invfac[m];
    }
    i64 inv(int m) {
        return invfac(m) * fac(m - 1) % mod;
    }
    i64 operator()(int n, int m) {
        if (m < 0 || n < m) {
            return 0;
        }
        return fac(n) * invfac(m) % mod * invfac(n - m) % mod;
    }
    i64 Lucas(i64 n, i64 m) {
        if (m == 0) {
            return 1;
        }
        return (*this)(n % mod, m % mod) * Lucas(n / mod, m / mod) % mod;
    }
} comb;

ST表

template <typename T, typename Func = function<T(const T &, const T &)>>
struct ST {
    vector<vector<T>> st;
    Func func;

    ST() = default;
    ST(const vector<T> &v, Func func = [](const T &a, const T &b) {
        return max(a, b);
    }) : func(move(func)) {
        int k = bit_width<unsigned>(v.size());
        st.resize(k + 1, vector<T>(v.size()));
        st[0] = v;
        for (int i = 0; i < k; i++) {
            for (int j = 0; j + (1 << (i + 1)) - 1 < v.size(); ++j) {
                st[i + 1][j] = this->func(st[i][j], st[i][j + (1 << i)]);
            }
        }
    }
    T range(int l, int r) {
        int t = __lg(r - l + 1);
        return func(st[t][l], st[t][r + 1 - (1 << t)]);
    }
};