把 v2(w) 的期望压成低 12 位精确、高位只留「连续相同位游程」的概率 DP;转移对游程长度仿射,于是每格只存概率与游程期望,O(n·2^B)。
OJ: roj
题目 ID: 1785
难度:提高+/省选-
标签:动态规划概率与期望位运算python
创建: 2026-10-08 03:20
更新: 2026-10-08 03:20
形式化题目
变量
题面校正。 题面【题目描述】写的是
1 1 50→:读成 时 ,而 在数学上无定义, 且 取任何约定都无法同时满足样例 1 与样例 3; 5 3 0→: 恒 , , (两种读法都成立); 5 3 25→,把 的 8 条路径全枚举正好凑出 :
| 路径 | 终值 |
概率 | 贡献 | |
|---|---|---|---|---|
| 40 | 3 | |||
| 21 | 0 | 0 | ||
| 22 | 1 | |||
| 12 | 2 | |||
| 24 | 3 | |||
| 13 | 0 | 0 | ||
| 14 | 1 | |||
| 8 | 3 |
合计
正解
思路
朴素做法的瓶颈。 决策树有
观察一:
因为
观察二:两种操作对状态的影响都很局部。
:低 位整体左移,旧的 bit 被推进第 位。 该位等于 则游程延续( ),否则游程重置( ,新的 就是该位)。 : 时低 位加一、 不变; 时低 位归零、进位进入第 位: 时进位穿过整段 个 1、停在第 位(那是 0),游程变成 个 0, 不变; 时第 位由 0 变 1、进位到此为止,游程重置为 1。
观察三:转移对
: , ; : , ; : , 。
答案也只需这两个量:
| 操作 | 条件 | 落点 |
||
|---|---|---|---|---|
| 任意 |
其中
摘要为何够用。 摘要唯一丢掉的信息是「第
代码
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++ 正式解:
/**
* 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;
}复杂度
- 时间:每步枚举
个状态、每状态 转移,共 ; 、 时约 次转移,实测 13 ms(限时 1000 ms)。 Python 短解法取 (同样的复杂度,常数更小),实测 0.10 s。 - 空间:只滚动当前与下一层各
个二元组, 。
总结
- 期望类问题先问「答案由哪些位决定」:
只吃低位,于是把状态压成 「低 位精确 + 高位游程摘要」。 - 高位用游程
而不是原值,是因为 的进位与 的移位都只看 「从第 位起有多少位相同」;再把对 的仿射依赖聚合成 两个量,状态数就与 无关。 不是随便取的:摘要出错要 步才可能影响到答案, 取 使 明显大于 上限即可(本题 )。 - 本题还提醒一件事:题面的公式可能印错,先用样例把题意钉死再动手。