【牛客练习赛137 C】题解

这场有点太超标了，后四题一个不会哈哈

慕容青峰

912人浏览 · 2025-04-20 14:24:47

慕容青峰 · 2025-04-20 14:24:47 发布

比赛链接

题目大意

一个长度为 $n$ 的非负数组 $a$ ，要求执行 $k$ 次操作，每次操作如下：

有 $\frac{1}{2}$ 的概率令 $a_i \leftarrow a_i + (a_i \otimes m) + x, \ \forall i \in [1, n]$ ；
另 $\frac{1}{2}$ 的概率保持 $\forall a_i$ 不变。

求 $\sum\limits_{i = 1}^{n}a_i$ 的期望，答案对 $998244353$ 取模。

其中 $\otimes$ 表示按位与，例如 $(10)_2 \otimes (11)_2 = (10)_2, \ (01)_2 \otimes (10)_2 = 0$ 。

数据范围

$\leq n \leq 10^6,$
$\leq m, k \leq 5 \cdot 10^3,$
$\leq x \leq 10^5,$
$\leq a_i \leq 10^9.$

Solution

我们观察 $a_i$ 的增量 $(a_i \otimes m) + x$ ，发现除了给定的 $x$ ， $(a_i \otimes m)$ 只与后 $\lfloor \log_2 m \rfloor$ 位有关，于是记 $2^{\lfloor \log_2 m \rfloor + 1},$

这样一来我们只需要知道 $a_i \otimes (M - 1)$ 就能知道 $a_i$ 的增量。

于是我们把每个 $a_i$ 划分为两部分，分别是 $\lfloor \frac{a_i}{M} \rfloor$ 和 $a_i \otimes (M - 1)$ ，我们称其为高位和低位。

接下来我们就分别求高位和低位的期望 $\rm{his}$ 和 $\rm{los}$ ，最终的答案就是 $\rm{his \times M + los}$ 。

对于低位来说，我们可以构造一个转换表 $\rm{suf}$ ，其中 $\rm{suf[v]} = (v + (v \otimes m) + x) \otimes (M - 1), \ v \in [0, M).$

这样就可以求出低位和的期望 $\rm{los}$ 。

假设有 $j$ 次操作让 $a_i$ 发生改变，现在已经求出 $j - 1$ 次改变时每个低位值的个数，记为 $cnt_{j - 1}[v]$ ，其中 $\in [0, M)$ ，那么只要对 $\forall v \in [0, M)$ 做一次 $\rm{suf}$ 变换就可以得到新的 $v^{'}$ 以及 $cnt_j[v']$ 了，具体来说就是 $\rm{cnt_j[suf[v]]} := cnt_j[suf[v]] + cnt_{j - 1}[v].$ 再对每个 $cnt_j[v'] \times v'$ 乘上 $j$ 次改变的概率 $\left(\frac{1}{2}\right)^k{k \choose j},$ 最后求和就是期望。
初始值 $cnt_0[v]$ 只要对 $\forall a_i$ 记录 $a_i \otimes (M - 1)$ 的数量即可。

高位就稍微复杂一些。

我们模仿低位，构造一个高位映射表 $\rm{pre}$ ，其中 $\rm{pre[v]} = \lfloor \frac{(v + (v \otimes m) + x)}{M} \rfloor, \ v \in [0, M).$

对于高位来说，我们不用期望的原始公式 $\sum\limits_{i = 1}^{N}p_i X_i,$ 而是选择一个基准 $B$ ，对其变形得到 $\sum\limits_{i = 1}^{N}p_i (X_i - B + B) = B + \sum\limits_{i = 1}^{N}p_i (X_i - B).$ 其中 $X_i - B)$ 是每个随机变量取值 $X_i$ 相对于 $B$ 的增量。

在高位上我们选择的基准 $\sum\limits_{i = 1}^{n}\lfloor \frac{(a_i + (a_i \otimes m) + x)}{M} \rfloor.$

接下来就是算高位增量的期望了。

我们先给出求和式。

$\sum\limits_{j = 0}^{k}\left( \frac{1}{2} \right)^k {k \choose j} \sum\limits_{i = 0}^{j - 1}\sum\limits_{v = 0}^{M - 1}cnt_i[v] \times pre[v],$

上式中 $\left( \frac{1}{2} \right)^k {k \choose j}$ 表示对数组 $a$ 做了 $j$ 次改变的概率，后面的两重循环是求从开始到改变 $j$ 次的增量和。

对于 $j$ ，之所以我们要遍历 $\in [0, j)$ ，是因为 $cnt_i[v]$ 是不断变化的；而低位不需要这样遍历则是因为它不用求增量，可以直接获得值。

但是这个三重循环的复杂度我们无法接受，所以考虑交换求和次序。

$\begin{align*} &\sum\limits_{j = 0}^{k}\left( \frac{1}{2} \right)^k {k \choose j} \sum\limits_{i = 0}^{j - 1}\sum\limits_{v = 0}^{M - 1}cnt_i[v] \times pre[v] \\ &= \sum\limits_{i = 0}^{k}\sum\limits_{j = i + 1}^{k}\sum\limits_{v = 0}^{M - 1}\left( \frac{1}{2} \right)^k {k \choose j} \times cnt_i[v] \times pre[v] \\ &= \sum\limits_{i = 0}^{k}\sum\limits_{v = 0}^{M - 1}cnt_i[v] \times pre[v] \sum\limits_{j = i + 1}^{k}\left( \frac{1}{2} \right)^k {k \choose j} \\ &= \sum\limits_{i = 0}^{k}\sum\limits_{v = 0}^{M - 1}cnt_i[v] \times pre[v] \times s[j]. \end{align*}$

其中 $\sum\limits_{j = i + 1}^{k}\left( \frac{1}{2} \right)^k {k \choose j}.$

这样就把复杂度降到 $O (M k)$ 了。

时间复杂度 $O (mk)$

虽然说 $2^{\lfloor \log_2 m\rfloor} + 1$ ，但是量级上最多是 $2 m$ ， $2$ 可以看作常数。

C++ Code

#include <bits/stdc++.h>

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

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;
}
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>;

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) {
        m = std::min(m, Z::getMod() - 1);
        if (m <= n) return;
        _fac.resize(m + 1);
        _invfac.resize(m + 1);
        _inv.resize(m + 1);
        for (int i = n + 1; i <= m; i += 1) {
            _fac[i] = _fac[i - 1] * i;
        }
        _invfac[m] = _fac[m].inv();
        for (int i = m; i > n; i -= 1) {
            _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);
    }
    Z Lucas(i64 n, i64 m, int p) {
        if (n < p and m < p) {
            return binom(n, m);
        }
        return Lucas(n / p, m / p, p) * binom(n % p, m % p);
    }
    Z Lucas(i64 n, i64 m) {
        if (n < Z::getMod() and m < Z::getMod()) {
            return binom(n, m);
        }
        return Lucas(n / Z::getMod(), m / Z::getMod()) * binom(n % Z::getMod(), m % Z::getMod());   
    }
    Z perm(int n, int m) {
        if (n < m or m < 0) {
            return 0;
        }
        return fac(n) * invfac(n - m);
    }
} comb;

template<class T>
std::istream &operator>>(std::istream &is, std::vector<T> &v) {
    for (auto &x: v) {
        is >> x;
    }
    return is;
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int n, x, m, k;
    std::cin >> n >> x >> m >> k;

    std::vector<int> a(n);
    std::cin >> a;

    int lm = std::__lg(m) + 1;
    int M = 1 << lm;

    std::vector<int> pre(M);
    std::vector<int> suf(M);
    for (int i = 0; i < M; i++) {
        int v = i + (i & m) + x;
        pre[i] = v >> lm;
        suf[i] = v & (M - 1);
    }

    Z hi0 = 0;
    std::vector<int> cnt(M);
    for (int ai: a) {
        cnt[ai & (M - 1)]++;
        hi0 += ai >> lm;
    }

    std::vector<Z> binom(k + 1);
    for (int i = 0; i <= k; i++) {
        binom[i] = comb.binom(k, i) / power(Z(2), k);
    }
    std::vector<Z> s(k + 2);
    for (int i = k; i >= 0; i--) {
        s[i] = s[i + 1] + binom[i];
    }

    Z los = 0;
    Z his = hi0;
    for (int i = 0; i <= k; i++) {
        Z lo = 0;
        Z hi = 0;
        for (int j = 0; j < M; j++) {
            lo += Z(cnt[j]) * j;
            hi += Z(cnt[j]) * pre[j];
        }
        los += binom[i] * lo;
        his += s[i + 1] * hi;
        std::vector<int> ncnt(M);
        for (int j = 0; j < M; j++) {
            ncnt[suf[j]] += cnt[j];
        }
        cnt = std::move(ncnt);
    }

    Z ans = his * M + los;

    std::cout << ans << "\n";
    
    return 0;
}

2048 AI社区

有“AI”的1024 = 2048，欢迎大家加入2048 AI社区

更多推荐

UFW防火墙安全指南

UFW（Uncomplicated Firewall）是Ubuntu/Debian系统中简化防火墙管理的工具，通过直观命令帮助用户有效控制网络流量，提升系统安全性。文章详细介绍了UFW的基本命令，包括启停防火墙、添加规则、限制连接速率和日志配置等操作，并提供了安全最佳实践，如默认拒绝策略、IP地址限制和服务级规则管理。同时，还涵盖高级配置技巧，例如多网络接口设置、规则优先级调整、IPv6支持及与f