VP 2024 CCPC 郑州

比赛链接

Problems	Status	Notes
A. A + B = C Problem
B. Rolling Stones	○
C. Middle Point	⊕
D. Guessing Game
E. Permutation Routing
F. Infinite Loop	○
G. Same Sum	⊕	线段树、生成函数
H. The Witness
I. Best Friend, Worst Enemy
J. Balance in All Things
K. Brotato	⊕	概率、期望
L. Z-order Curve	○
M. Rejection Sampling	○

K

假设拥有「无限」道具，并且每次失败都立刻用道具（因此从不回到第 1 关）时，每一关都是独立的几何分布，期望尝试次数是

$$\frac{1}{1 - p}$$

每一关失败的期望次数是

$$\frac{1}{1 - p} - 1 = \frac{p}{1 - p}$$

因此总的失败次数（即总的道具消耗）期望是

$$
n \cdot \frac{p}{1-p} = \frac{np}{1-p}
$$

题目保证 $np\le20$，说明即使 $n$ 很大，$p$ 也足够小，使得 $\frac{np}{1-p}$ 上限约在 20～30 量级，不会无限发散。

当你的道具数 $k$ 远大于 $\frac{np}{1-p}$（例如 $k>165$），就几乎可以保证每次失败都能用道具。从而不回头，通关总尝试数的期望≈
$$
\frac{n}{1-p}
$$

因此，接下来我们只需要讨论 $k$ 较小的 case。

我们用 $f_{i,j}$ 表示：

当前已经成功通过第 $j$ 关，剩余道具数还有 $i$ 个，此时要通关剩下的 $n-j$ 关，额外需要的「期望尝试次数」。

假设我们处在第 $j$ 关（也就意味着下一个要挑战的是 $j+1$ 关）：

1. 选择立刻用道具（前提：$i>0$）
   • 本次挑战，如果失败，消耗 1 个道具，仍在第 $j+1$ 关重试；如果成功，就进入状态 $(i,j+1)$。
   • 成功／失败两种情况的贡献：
     $$
     1
     +p\cdot f_{i-1,j}
     +(1-p)\cdot f_{i,j+1}.
     $$
2. 选择不使用道具
   • 本次挑战，如果失败，则回到关卡 1（状态变为 $(i,0)$），如果成功，则进入 $(i,j+1)$。
   • 但是由于“单调性”说明，从现在开始直到第 $j+1$ 关都不再用道具，这一段就等价于：
     • 从第 1 关重新开始，一直打到第 $j+1$ 关成功。
     • 这一段无道具、全程失败必回头，期望尝试次数有一个封闭式：
       $$
       \biggl(\frac1{1-p}\biggr)^{j+1}
       $$
   • 再加上后面 $(i,j+1)$ 的期望，所以这一选项的期望是
     $$
     \bigl(\tfrac1{1-p})^{j+1} + f_{i,j+1}.
     $$

因此总的转移方程是

$$
f_{i,j}
= \min\lbrace 1 + pf_{i-1,j} + (1-p)f_{i,j+1}
,
(\frac{1}{1-p})^{j+1} + f_{i,j+1}\rbrace
$$

#include <bits/stdc++.h>
using i64 = long long;
#define int i64
#define pb push_back
#define ep emplace
#define eb emplace_back
using namespace std;
int read(int x = 0, int f = 0, char ch = getchar()) {
    while (ch < 48 or 57 < ch) f = ch == 45, ch = getchar();
    while(48 <= ch and ch <= 57) x = x * 10 + ch - 48, ch = getchar();
    return f ? -x : x;
}
template <class T1, class T2> ostream &operator<<(ostream &os, const std::pair<T1, T2> &a) { return os << "(" << a.first << ", " << a.second << ")"; };
template <class T> ostream &operator<<(ostream &os, const vector<T> &as) { const int sz = as.size(); os << "["; for (int i = 0; i < sz; ++i) { if (i >= 256) { os << ", ..."; break; } if (i > 0) { os << ", "; } os << as[i]; } return os << "]"; }
template <class T> void pv(T a, T b) { for (T i = a; i != b; ++i) cerr << *i << " "; cerr << '\n'; }
using pii = pair<int, int>;
const int inf = 1e18;

void solve() {
    int n = read();
    int k = read();
    double p; cin >> p;

    if (k > 165) {
        double ans = n / (1 - p);
        printf("%.12lf\n", ans);
        return;
    }

    vector<double> pw(n + 1);
    vector dp(k + 1, vector(n + 1, (double)(0.0)));

    pw[0] = 1;
    for (int i = 1; i <= n; i++) {
        pw[i] = pw[i - 1] / (1 - p);
    }
    for (int i = 0; i <= k; i++) {
        for (int j = n - 1; j >= 0; j--) {
            dp[i][j] = dp[i][j + 1] + pw[j + 1];
            if (i != 0) {
                dp[i][j] = min(dp[i][j], 1 + p * dp[i - 1][j] + (1 - p) * dp[i][j + 1]);
            }
        }
    }
    printf("%.12lf\n", dp[k][0]);
}

signed main() {
    // for (int T = read(); T--; solve());
    solve();
    return 0;
}

G

题目描述
给定一个非负整数序列 $A=\left[a_1, a_2, \ldots, a_n\right]$ ，设计一个数据结构维护以下更新操作以及回答询问。

• 区间加 $w$ ；
• 区间查询：是否能将区间内的数两两配对，使得和相等。

数据范围：$n, q, w \leq 2 \cdot 10^5$ ；
出题人：Tianxing Ding（skyline）and Jiachen Tang（oscar）

解法

• 考虑维护一下区间信息：
• 矩母函数 $M_{+}(x)=\sum_{i \in[L, R]} x^{a_i}, M_{-}(x)=\sum_{i \in[L, R]} x^{-a_i}$ ；
• 区间平均值 $m$ 。
• 满足条件当且仅当 $M_{+}(x)=x^{2 m} M_{-}(x)$ 。
• 考虑随机 $x$ 作为哈希值进行判定即可。
• 时间复杂度：$O(n \log n)$ 。
• 标准程序使用 $10^{18}$ 量级的模数以及两个随机 $x$ 作为hash值，可以保证正确率不低于 $1-10^{-12}$ 。

特别注意：维护前 $k=\Theta(\log n)$ 阶矩 $\sum_{i \in[L, R]} a_i^k$ 是错误解答。事实上，可以构造出前 $\Theta(\log n)$ 阶矩一致，但本质不同的两个序列。

很有启发性的思路，将配对问题转化为多项式的判定

进一步地，多项式哈希不止能检验配对，还能 检查两个子串、多段区间的“相同多重集合”，或是 验证某些子集和／子序列和的分布性质。

#include <bits/stdc++.h>
using i64 = long long;
#define int i64
#define pb push_back
#define ep emplace
#define eb emplace_back
using namespace std;
int read(int x = 0, int f = 0, char ch = getchar()) {
    while (ch < 48 or 57 < ch) f = ch == 45, ch = getchar();
    while(48 <= ch and ch <= 57) x = x * 10 + ch - 48, ch = getchar();
    return f ? -x : x;
}
template <class T1, class T2> ostream &operator<<(ostream &os, const std::pair<T1, T2> &a) { return os << "(" << a.first << ", " << a.second << ")"; };
template <class T> ostream &operator<<(ostream &os, const vector<T> &as) { const int sz = as.size(); os << "["; for (int i = 0; i < sz; ++i) { if (i >= 256) { os << ", ..."; break; } if (i > 0) { os << ", "; } os << as[i]; } return os << "]"; }
template <class T> void pv(T a, T b) { for (T i = a; i != b; ++i) cerr << *i << " "; cerr << '\n'; }
using pii = pair<int, int>;
const int inf = 1e18;

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_, v_));
    }
    template<class T>
    void init(std::vector<T> init_) {
        n = init_.size();
        info.assign(4 << std::__lg(n), Info());
        tag.assign(4 << std::__lg(n), Tag());
        std::function<void(int, int, int)> build = [&](int p, int l, int r) {
            if (r - l == 1) {
                info[p] = init_[l];
                return;
            }
            int m = (l + r) / 2;
            build(2 * p, l, m);
            build(2 * p + 1, m, r);
            pull(p);
        };
        build(1, 0, 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 (r - l == 1) {
            info[p] = v;
            return;
        }
        int m = (l + r) / 2;
        push(p);
        if (x < m) {
            modify(2 * p, l, m, x, v);
        } else {
            modify(2 * p + 1, m, r, x, v);
        }
        pull(p);
    }
    void modify(int p, const Info &v) {
        modify(1, 0, n, p, v);
    }
    Info rangeQuery(int p, int l, int r, int x, int y) {
        if (l >= y || r <= x) {
            return Info();
        }
        if (l >= x && r <= y) {
            return info[p];
        }
        int m = (l + r) / 2;
        push(p);
        return rangeQuery(2 * p, l, m, x, y) + rangeQuery(2 * p + 1, m, r, x, y);
    }
    Info rangeQuery(int l, int r) {
        return rangeQuery(1, 0, 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 (l >= x && r <= y) {
            apply(p, v);
            return;
        }
        int m = (l + r) / 2;
        push(p);
        rangeApply(2 * p, l, m, x, y, v);
        rangeApply(2 * p + 1, m, r, x, y, v);
        pull(p);
    }
    void rangeApply(int l, int r, const Tag &v) {
        return rangeApply(1, 0, n, l, r, v);
    }
    void half(int p, int l, int r) {
        if (info[p].act == 0) {
            return;
        }
        if ((info[p].min + 1) / 2 == (info[p].max + 1) / 2) {
            apply(p, {-(info[p].min + 1) / 2});
            return;
        }
        int m = (l + r) / 2;
        push(p);
        half(2 * p, l, m);
        half(2 * p + 1, m, r);
        pull(p);
    }
    void half() {
        half(1, 0, n);
    }
    
    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);
    }
    
    void maintainL(int p, int l, int r, int pre) {
        if (info[p].difl > 0 && info[p].maxlowl < pre) {
            return;
        }
        if (r - l == 1) {
            info[p].max = info[p].maxlowl;
            info[p].maxl = info[p].maxr = l;
            info[p].maxlowl = info[p].maxlowr = -inf;
            return;
        }
        int m = (l + r) / 2;
        push(p);
        maintainL(2 * p, l, m, pre);
        pre = std::max(pre, info[2 * p].max);
        maintainL(2 * p + 1, m, r, pre);
        pull(p);
    }
    void maintainL() {
        maintainL(1, 0, n, -1);
    }
    void maintainR(int p, int l, int r, int suf) {
        if (info[p].difr > 0 && info[p].maxlowr < suf) {
            return;
        }
        if (r - l == 1) {
            info[p].max = info[p].maxlowl;
            info[p].maxl = info[p].maxr = l;
            info[p].maxlowl = info[p].maxlowr = -inf;
            return;
        }
        int m = (l + r) / 2;
        push(p);
        maintainR(2 * p + 1, m, r, suf);
        suf = std::max(suf, info[2 * p + 1].max);
        maintainR(2 * p, l, m, suf);
        pull(p);
    }
    void maintainR() {
        maintainR(1, 0, n, -1);
    }
};

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 <i64 P>
struct MInt {
    i64 x;
    constexpr MInt() : x {0} {}
    constexpr MInt(i64 x) : x {norm(x % getMod())} {}
    static i64 Mod;
    constexpr static i64 getMod() { return P > 0 ? P : Mod; }
    constexpr static void setMod(i64 Mod_) { Mod = Mod_; }
    constexpr i64 norm(i64 x) const { if (x < 0) x += getMod(); if (x >= getMod()) x -= getMod(); return x; }
    constexpr i64 val() const { return x; }
    constexpr MInt operator-() const { MInt res; res.x = norm(getMod() - x); return res; }
    constexpr MInt inv() const { return power(*this, getMod() - 2); }
    constexpr MInt &operator*=(MInt rhs) & { if (getMod() < (1ULL << 31)) x = x * rhs.x % int(getMod()); else x = mul(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(); }
    friend constexpr bool operator<(MInt lhs, MInt rhs) { return lhs.val() < rhs.val(); }
};
template <>
i64 MInt<0>::Mod = 998244353;
constexpr int P = 998244353;
using Z = MInt<P>;

Z X;
struct Tag {
    int add {0};
     
    void apply(const Tag &t) & {
        add += t.add;
    }
};
struct Info {
    Z x1 = 0;
    Z x2 = 0;
    int sum = 0;
    int cnt = 0;
    void apply(const Tag &t) & {
        Z tmp = power(X, t.add);
        x1 *= tmp;
        x2 /= tmp;
        sum += t.add * cnt;
    }
};

Info operator+(const Info &a, const Info &b) {
    return {
        a.x1 + b.x1, 
        a.x2 + b.x2, 
        a.sum + b.sum,
        a.cnt + b.cnt
    };
}

void solve() {
    srand(time(0));
    X = rand();
    // X = 2;
    // cerr << X << '\n';

    int n = read();
    int q = read();

    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) a[i] = read();
    // cerr << a << '\n';

    LazySegmentTree<Info, Tag> seg(n + 1);

    // cout << seg.rangeQuery(1, 8).x << '\n';
    
    for (int i = 1; i <= n; i++) {
        Z t = power(X, a[i]);
        seg.modify(i, {
            t,
            t.inv(),
            a[i],
            1
        });
        // cerr << seg.rangeQuery(i, i + 1).sum << '\n';
    }

    while (q--) {
        int opt = read();
        int l = read(), r = read();
        if (opt == 1) {
            int v = read();
            seg.rangeApply(l, r + 1, {v});

        } else {
            auto [x1, x2, sum, cnt] = seg.rangeQuery(l, r + 1);
            if (x1 == x2 * power(X, 2 * sum / cnt)) {
                cout << "YES\n";
            } else {
                cout << "NO\n";
            }
        }
    }
}

signed main() {
    // for (int T = read(); T--; solve());
    solve();
    return 0;
}