简单的期望

GitHub跳转原题关系图返回列表

把 v2(w) 的期望压成低 12 位精确、高位只留「连续相同位游程」的概率 DP;转移对游程长度仿射,于是每格只存概率与游程期望,O(n·2^B)。

OJ: roj

题目 ID: 1785

难度:提高+/省选-

标签:动态规划概率与期望位运算python

创建: 2026-10-08 03:20

更新: 2026-10-08 03:20

形式化题目

变量 xx 初值给定,依次做 nn 次操作,每次以 p%p\% 的概率令 x←2xx \leftarrow 2x, 以 (100−p)%(100-p)\% 的概率令 x←x+1x \leftarrow x+1。记最终值为 ww, d=v2(w)d = v_2(w)(ww 的质因数分解中 2 的指数,即二进制末尾连续 0 的个数),求 E[d]E[d]。 误差不超过 10−610^{-6} 即正确。范围:x≤109x \le 10^9,n≤200n \le 200,0≤p≤1000 \le p \le 100。

题面校正。 题面【题目描述】写的是 x←x/2x \leftarrow x/2,但三个官方样例只有 x←2xx \leftarrow 2x 能同时对上:

  • 1 1 50 → 1.00000000001.0000000000:读成 x/2x/2 时 1→01 \to 0,而 v2(0)v_2(0) 在数学上无定义, 且 d(0)d(0) 取任何约定都无法同时满足样例 1 与样例 3;
  • 5 3 0 → 3.00000000003.0000000000:p=0p=0 恒 +1+1,5→6→7→85 \to 6 \to 7 \to 8,v2(8)=3v_2(8)=3(两种读法都成立);
  • 5 3 25 → 1.9218750000=123/641.9218750000 = 123/64,把 x←2xx \leftarrow 2x 的 8 条路径全枚举正好凑出 123/64123/64:
路径 终值 ww v2(w)v_2(w) 概率 贡献
×××\times\times\times 40 3 1/641/64 3/643/64
××+\times\times+ 21 0 3/643/64 0
×+×\times+\times 22 1 3/643/64 3/643/64
×++\times++ 12 2 9/649/64 18/6418/64
+××+\times\times 24 3 3/643/64 9/649/64
+×++\times+ 13 0 9/649/64 0
++×++\times 14 1 9/649/64 9/649/64
++++++ 8 3 27/6427/64 81/6481/64

合计 123/64=1.921875123/64 = 1.921875。而读成 x/2x/2 时 n≤200n \le 200 的规模下 30 步后必为 0, n≤20/50/100n \le 20/50/100 的分层也失去意义。故题面的 “/” 是 “*” 的排版笔误,本解按 x←2xx \leftarrow 2x 实现。

正解

思路

朴素做法的瓶颈。 决策树有 2n2^n 个叶子,n=200n = 200 时不可行;而 w≤x⋅2n<2230w \le x \cdot 2^n < 2^{230}, 以「当前数值」为状态做 DP 会直接爆炸。所以必须找到「只保留与 v2v_2 有关的信息」的压缩状态。

观察一:v2v_2 只看低位。 记 s=w mod 2Bs = w \bmod 2^B(低 BB 位),tt 为 ww 的第 BB 位, kk 为从第 BB 位起连续等于 tt 的位数(游程)。则

v2(w)={v2(s),s≠0B,s=0, t=1B+k,s=0, t=0v_2(w) = \begin{cases} v_2(s), & s \ne 0 \\ B, & s = 0,\ t = 1 \\ B + k, & s = 0,\ t = 0 \end{cases}

因为 s≠0s \ne 0 时末尾 0 必落在低 BB 位内;s=0s = 0 时高位从第 BB 位起先是 kk 个 tt: t=1t = 1 说明第 BB 位就是 1(恰好 BB 个末尾 0),t=0t = 0 说明第 B+kB+k 位是 1(恰好 B+kB+k 个)。

观察二:两种操作对状态的影响都很局部。

  • w←2ww \leftarrow 2w:低 BB 位整体左移,旧的 bit (B−1)(B-1) 被推进第 BB 位。 该位等于 tt 则游程延续(k→k+1k \to k+1),否则游程重置(k→1k \to 1,新的 tt 就是该位)。
  • w←w+1w \leftarrow w+1:s<2B−1s < 2^B - 1 时低 BB 位加一、(t,k)(t,k) 不变; s=2B−1s = 2^B - 1 时低 BB 位归零、进位进入第 BB 位: t=1t = 1 时进位穿过整段 kk 个 1、停在第 B+kB+k 位(那是 0),游程变成 kk 个 0,kk 不变; t=0t = 0 时第 BB 位由 0 变 1、进位到此为止,游程重置为 1。

观察三:转移对 kk 是仿射的。 上面三条转移里 k′k' 只会是 kk、k+1k+1 或常数 11, 于是不必为每个 kk 单独存状态:对每个 (s,t)(s,t) 只维护两个量

P[s][t]=∑kPr⁡[s][t][k],Q[s][t]=∑kk⋅Pr⁡[s][t][k].P[s][t] = \sum_k \Pr[s][t][k], \qquad Q[s][t] = \sum_k k \cdot \Pr[s][t][k].
  • k′=kk' = k:P+=pP \mathrel{+}= p,Q+=qQ \mathrel{+}= q;
  • k′=k+1k' = k+1:P+=pP \mathrel{+}= p,Q+=q+pQ \mathrel{+}= q + p;
  • k′=1k' = 1:P+=pP \mathrel{+}= p,Q+=pQ \mathrel{+}= p。

答案也只需这两个量:s=0s = 0 且 t=0t = 0 时的贡献是 B+kB + k, 聚合后就是 B⋅P[0][0]+Q[0][0]B \cdot P[0][0] + Q[0][0]。状态数从 O(2B⋅n)O(2^B \cdot n) 降到 O(2B)O(2^B)。

操作 条件 落点 (s′,t′)(s',t') PP 增量 QQ 增量
+1+1 s<2B−1s < 2^B-1 (s+1, t)(s+1,\ t) p⋅ap \cdot a q⋅aq \cdot a
+1+1 s=2B−1, t=1s = 2^B-1,\ t=1 (0, 0)(0,\ 0) p⋅ap \cdot a q⋅aq \cdot a
+1+1 s=2B−1, t=0s = 2^B-1,\ t=0 (0, 1)(0,\ 1) p⋅ap \cdot a p⋅ap \cdot a
×2\times 2 任意 ( (2s) mod 2B, b )(\,(2s) \bmod 2^B,\ b\,),b = $ 旧 bit $(B-1) p⋅cp \cdot c (q+p)c(q + p) c,若 b=tb = t 否则 p⋅cp \cdot c

其中 a=(100−p)/100a = (100-p)/100、c=p/100c = p/100。

摘要为何够用。 摘要唯一丢掉的信息是「第 B+kB+k 位之上」的位。只有一种转移会用到它: w←w+1w \leftarrow w+1 且 t=1t = 1 时,进位穿过整段 1 游程,若第 B+kB+k 位实际是 1 就会继续进位, 而摘要以为它停了。会让摘要出错(把「实际是 1」记成 0)的转移只有 s=2B−1s = 2^B-1、t=0t = 0、k=1k = 1 的 那次进位;要把它暴露出来,必须再来一次 t=1t = 1 的进位,也就是要再从 s=0s = 0 走到 s=2B−1s = 2^B-1。 这段路上不能用 ×2\times 2——s=0s = 0 时 bit (B−1)(B-1) 是 0,一乘就重置游程、摘要自动修正—— 只能靠 +1+1 爬,需要 2B−12^B - 1 步。合计 2B+12^B + 1 步才可能污染答案, 取 B=12B = 12(40974097 步)对 n≤200n \le 200 有 20 倍余量,故与精确解一致。

代码

Python 短解法:

python
#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-08 03:20
# update_at: 2026-10-08 03:35

import sys

# 题面【题目描述】的 "x = x/2" 是排版笔误:三个官方样例只有 x = x*2 能同时对上
# (1 1 50 -> 1.0;5 3 0 -> 3.0;5 3 25 -> 1.921875 = 123/64),本解按 x = x*2 实现。
B = 10            # 低 B 位精确记录;n <= 200 时 B >= 8 就够,取 10 兼顾余量与速度
SZ = 1 << B       # 低 B 位的取值个数
MASK = SZ - 1     # 低 B 位全 1,用于判断"低 B 位是否全是 1"

type Prob = list[float]                # 某个 t 下按 s 索引的概率数组
type Bucket = list[tuple[Prob, Prob]]  # bucket[t] = (概率数组 P, 游程期望贡献数组 Q)


def step_state(s: int, t: int, pr: float, qk: float, dst: Bucket, add1: float, mul2: float) -> None:
    """把状态 (s,t) 的概率 pr 与游程期望贡献 qk 按两种操作推到本轮的新数组上。"""
    if add1:  # w += 1
        if s != MASK:
            dp, dq = dst[t]
            dp[s + 1] += pr * add1
            dq[s + 1] += qk * add1
        else:  # 低 B 位归零、进位进入第 B 位,该位取反
            dp, dq = dst[t ^ 1]
            dp[0] += pr * add1
            # t=1 时进位穿过整段 1,游程原样变成 k 个 0(k 不变);t=0 时重置为 1
            dq[0] += (qk if t else pr) * add1
    if mul2:  # w *= 2
        bit = s >> (B - 1)  # 左移后进入第 B 位的那一位,它就是新的 t
        dp, dq = dst[bit]
        ns = (s << 1) & MASK
        gain = qk + pr if bit == t else pr  # 该位等于 t 则游程 k+1,否则重置为 1
        dp[ns] += pr * mul2
        dq[ns] += gain * mul2


def expectation(x: int, n: int, p: int) -> float:
    """算 n 次操作后 v2(w) 的期望(v2 即二进制末尾 0 的个数)。

    状态 = (s, t, k):s = w mod 2^B 精确记录,t = w 的第 B 位,
    k = 从第 B 位起连续等于 t 的位数。于是 v2(w) 可读出:s != 0 时是 v2(s),
    s = 0 且 t = 1 时是 B,s = 0 且 t = 0 时是 B + k。
    三种转移对 k 都是仿射的(k' = k、k+1 或常数 1),所以每个 (s,t) 只存两个量:
    P = Σ_k Pr[s][t][k] 与 Q = Σ_k k·Pr[s][t][k],答案里 B + k 那一支聚合后就是 B·P + Q。
    """
    add1 = 1.0 - p / 100.0  # w += 1 的概率
    mul2 = p / 100.0        # w *= 2 的概率

    p0, q0 = [0.0] * SZ, [0.0] * SZ  # t = 0:第 B 位是 0
    p1, q1 = [0.0] * SZ, [0.0] * SZ  # t = 1:第 B 位是 1

    # 初值:低 B 位取 x;t0 是 x 的第 B 位;k0 是 x >> B 从最低位起连续等于 t0 的位数
    s0 = x & MASK
    hi = x >> B
    t0 = hi & 1
    k0 = 0
    while hi >> k0 and (hi >> k0 & 1) == t0:
        k0 += 1
    k0 = max(k0, 1)  # x < 2^B 时高位全是 0,按"第 B 位起是 1 个 0"记
    (p1 if t0 else p0)[s0] = 1.0
    (q1 if t0 else q0)[s0] = k0

    for _ in range(n):
        np0, nq0 = [0.0] * SZ, [0.0] * SZ
        np1, nq1 = [0.0] * SZ, [0.0] * SZ
        dst: Bucket = [(np0, nq0), (np1, nq1)]
        for s in range(SZ):
            if p0[s]:
                step_state(s, 0, p0[s], q0[s], dst, add1, mul2)
            if p1[s]:
                step_state(s, 1, p1[s], q1[s], dst, add1, mul2)
        p0, q0, p1, q1 = np0, nq0, np1, nq1

    # (s & -s).bit_length() - 1 就是 v2(s)(s >= 1);s = 0 的两支是 B 与 B + k
    ans = sum(((s & -s).bit_length() - 1) * (p0[s] + p1[s]) for s in range(1, SZ))
    return ans + B * (p0[0] + p1[0]) + q0[0]


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    x, n, p = next(data), next(data), next(data)
    print(f"{expectation(x, n, p):.10f}")


if __name__ == "__main__":
    solve()

C++ 正式解:

cpp
/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-08 03:20
 * update_at: 2026-10-08 03:20
 */
// main.cpp:简单的期望(roj 1785)。
// 题意校正:题面【题目描述】写的 "x = x/2" 是排版笔误,三个官方样例只有 x = x*2 能同时对上
//   (1 1 50 -> 1.0;5 3 0 -> 3.0;5 3 25 -> 1.921875 = 123/64),本题按 x = x*2 实现。
// 目标:最终值 w 的 v2(w)(质因数分解中 2 的指数,即二进制末尾 0 的个数)的期望。
//
// 状态设计(低位精确 + 高位游程摘要):
//   取 s = w mod 2^B(低 B 位精确),t = w 的第 B 位,k = 从第 B 位起连续等于 t 的位数。
//   * w != 0 时 v2(w) 由状态直接读出:s != 0 -> v2(s);s = 0 且 t = 1 -> B;s = 0 且 t = 0 -> B + k。
//   * w += 1:s < 2^B - 1 时 (t,k) 不变;s = 2^B - 1 时 s 归零、进位进入第 B 位:
//       t = 1(第 B 位起是 k 个 1,第 B+k 位是 0)-> 进位穿过这 k 个 1,游程变成 k 个 0,k 不变;
//       t = 0 -> 第 B 位由 0 变 1,游程重置为 1。
//   * w *= 2:s 左移一位、旧的 bit(B-1) 进入第 B 位;该位等于 t 则游程延续 k+1,否则重置为 1。
//
// 关键压缩:三种转移对 k 都是仿射的(k' = k、k + 1 或常数 1),所以对每个 (s,t) 只需维护
//   p = Σ_k Pr[s][t][k],q = Σ_k k·Pr[s][t][k],
// 状态数从 O(2^B · n) 降到 O(2^B),答案照样能还原(s = 0 且 t = 0 时贡献 B·p + q)。
//
// 摘要为何够用:摘要丢掉的只是"第 B+k 位之上"的信息,只有 w += 1 的进位穿过整段 1 游程、
//   且第 B+k 位实际是 1 时才会用到它。这种"假信息"要再从 s = 0 走到 s = 2^B - 1(途中不能用
//   w *= 2,否则游程立即重置、摘要自动修正)需要 2^B - 1 步,B = 12 时是 4095 步,
//   n <= 200 留有 20 倍余量,故本实现与精确解一致。
// 复杂度:O(n · 2^B) 时间,O(2^B) 空间;B = 12、n = 200 时约 1.6e6 次转移。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int B = 12;          // 低 B 位精确记录,高位只留 (t,k) 摘要
const int SZ = 1 << B;     // 低 B 位的取值个数
const int MASK = SZ - 1;   // 低 B 位全 1,用于判断进位

// 每个 (s,t) 上聚合两个量:p = 该状态的概率总和,q = Σ_k k·Pr[s][t][k]
struct Agg {
    double p;
    double q;
};
Agg cur[2][SZ];  // cur[t][s]
Agg nxt[2][SZ];  // 本步转移的落点

// v2(v) = v 的二进制末尾 0 的个数(v >= 1)
int v2(ll v) {
    int z = 0;
    for (; (v & 1) == 0; v >>= 1) z++;
    return z;
}

int main() {
    ll x = 0;
    int n = 0, p = 0;
    if (scanf("%lld %d %d", &x, &n, &p) != 3) return 0;

    // 初始状态:低 B 位取 x,第 B 位是 t0,游程是 hi = x >> B 从最低位起连续等于 t0 的位数
    int s0 = x & MASK;
    ll hi = x >> B;
    int t0 = hi & 1;
    int k0 = 0;
    for (ll h = hi; h > 0 && (h & 1) == t0; h >>= 1) k0++;
    if (k0 == 0) k0 = 1;  // x < 2^B 时高位全是 0,按"第 B 位起是 1 个 0"记

    cur[t0][s0].p = 1.0;
    cur[t0][s0].q = k0;

    double mul2 = p / 100.0;      // w *= 2 的概率
    double add1 = 1.0 - mul2;     // w += 1 的概率

    for (int step = 0; step < n; step++) {
        for (int t = 0; t < 2; t++)
            for (int s = 0; s < SZ; s++) {
                nxt[t][s].p = 0.0;
                nxt[t][s].q = 0.0;
            }

        for (int t = 0; t < 2; t++) {
            for (int s = 0; s < SZ; s++) {
                double pr = cur[t][s].p;
                if (pr == 0.0) continue;  // 概率为 0 的分支(p = 0 或 100)直接跳过
                double qk = cur[t][s].q;

                if (add1 > 0.0) {  // 操作一:w += 1
                    double w1 = pr * add1;
                    if (s != MASK) {
                        nxt[t][s + 1].p += w1;
                        nxt[t][s + 1].q += qk * add1;
                    } else {
                        int nt = t ^ 1;  // 进位进入第 B 位,该位取反
                        nxt[nt][0].p += w1;
                        // t=1 时游程原样变 0(k 不变),t=0 时第 B 位由 0 变 1(k 重置为 1)
                        nxt[nt][0].q += (t == 1) ? qk * add1 : w1;
                    }
                }

                if (mul2 > 0.0) {  // 操作二:w *= 2
                    double w2 = pr * mul2;
                    int bit = (s >> (B - 1)) & 1;  // 左移后进入第 B 位的那一位
                    int ns = (s << 1) & MASK;
                    if (bit == t) {  // 与第 B 位相同,游程延续:k' = k + 1
                        nxt[t][ns].p += w2;
                        nxt[t][ns].q += qk * mul2 + w2;
                    } else {  // 不同,游程重置:k' = 1
                        nxt[bit][ns].p += w2;
                        nxt[bit][ns].q += w2;
                    }
                }
            }
        }

        for (int t = 0; t < 2; t++)
            for (int s = 0; s < SZ; s++) cur[t][s] = nxt[t][s];
    }

    // 统计答案:s != 0 贡献 v2(s);s = 0 且 t = 1 贡献 B;s = 0 且 t = 0 贡献 B + k
    double ans = 0.0;
    for (int s = 1; s < SZ; s++)
        ans += v2(s) * (cur[0][s].p + cur[1][s].p);
    ans += B * (cur[0][0].p + cur[1][0].p) + cur[0][0].q;

    printf("%.10f\n", ans);
    return 0;
}

复杂度

  • 时间:每步枚举 2⋅2B2 \cdot 2^B 个状态、每状态 O(1)O(1) 转移,共 O(n⋅2B)O(n \cdot 2^B); B=12B = 12、n=200n = 200 时约 1.6×1061.6 \times 10^6 次转移,实测 13 ms(限时 1000 ms)。 Python 短解法取 B=10B = 10(同样的复杂度,常数更小),实测 0.10 s。
  • 空间:只滚动当前与下一层各 2⋅2B2 \cdot 2^B 个二元组,O(2B)O(2^B)。

总结

  • 期望类问题先问「答案由哪些位决定」:v2v_2 只吃低位,于是把状态压成 「低 BB 位精确 + 高位游程摘要」。
  • 高位用游程 (t,k)(t,k) 而不是原值,是因为 +1+1 的进位与 ×2\times 2 的移位都只看 「从第 BB 位起有多少位相同」;再把对 kk 的仿射依赖聚合成 P,QP,Q 两个量,状态数就与 nn 无关。
  • BB 不是随便取的:摘要出错要 2B+12^B + 1 步才可能影响到答案, 取 BB 使 2B2^B 明显大于 nn 上限即可(本题 B=12B = 12)。
  • 本题还提醒一件事:题面的公式可能印错,先用样例把题意钉死再动手。