游戏 - 题目列表

形式化题目

Alice 初始有 $n$ 颗宝石，Bob 有 $m$ 颗（ $n, m \leqslant 100$ ），宝石总数 $n+m$ 恒定。每回合抛一枚正面概率为 $p$ （不超过 6 位的有限小数）的硬币：

正面：Alice 给 Bob 一颗宝石（Alice 为 0 时状态不变）；
反面：Bob 给 Alice 一颗宝石（Bob 为 0 时状态不变）。

若某个回合结束时 Alice 恰有 $n$ 颗宝石，游戏结束。求游戏进行的期望回合数，相对误差 $\leqslant 10^{-6}$ 。

注意终止条件的含义：Alice 初始就恰有 $n$ 颗。若第 1 回合正面朝上，Alice 变成 $n-1$ 颗，游戏不结束；游戏只在 Alice 的宝石数经过波动后回到出发值 $n$ 的那个回合结束。所以本题求的是"从 $n$ 出发的首次回返时间"，而不是"首次到达 $n$ "。

以样例 $n = m = 1$ 、 $p = 0.5$ 画出来： Alice 的宝石数每回合在 $0,1,2$ 之间移动，两个端点 0（Alice 空手）与 2（Bob 空手）各有"不用给"的自环，起点 $s_0 = 1$ ，当 $s_t$ 再次等于 1 时游戏结束：

digraph G {
  rankdir = LR;
  node [shape = circle, style = filled, fillcolor = lightblue, fontsize = 12];
  s0 [label = "k=0\nAlice空手", fillcolor = lightyellow];
  s1 [label = "k=1\n起点=终点", fillcolor = lightgreen];
  s2 [label = "k=2\nBob空手", fillcolor = lightyellow];

  s0 -> s0 [label = "正面 p（不用给）", constraint = false];
  s0 -> s1 [label = "反面 1-p"];
  s1 -> s0 [label = "正面 p"];
  s1 -> s2 [label = "反面 1-p"];
  s2 -> s1 [label = "正面 p"];
  s2 -> s2 [label = "反面 1-p（不用给）", constraint = false];
}

观察这张状态图：只要第 1 回合没回到 1，游戏就进入了"从 $0$ 或 $2$ 重新走回 $1$ "的子问题——这正是"回返时间"的结构。这个状态图与 $n = m = 1$ 的样例输出 $3.0$ 一起，可作为后文公式推导的直观校验：几何级数 $\sum_{k=0}^{2} 1^{k-1} = 3$ 恰好给出样例答案。

正解

思路

第一步：把游戏建模成随机游走。

设 $s_t$ 为第 $t$ 回合结束时 Alice 的宝石数， $s_0 = n$ ，状态空间 $\{0, 1, \dots, n+m\}$ ：

内部状态 $0 < k < n+m$ ：以概率 $p$ 走到 $k-1$ ，以概率 $1-p$ 走到 $k+1$ ；
端点反射： $k = 0$ （Alice 空手）时正面"不用给"， $0 \to 0$ 概率 $p$ ； $k = n+m$ 时反面 $n+m \to n+m$ 概率 $1-p$ 。

游戏终止时刻 $T = \min\{t \geqslant 1 : s_t = n\}$ ，即从 $n$ 出发的首次回返时间。

第二步：朴素做法及其瓶颈。

设 $E_k$ 为"Alice 有 $k$ 颗宝石时，再过多少回合宝石数回到 $n$ "的期望，列方程组：

E_n = 1 + p\,E_{n-1} + (1-p)E_{n+1}, \qquad E_0 = 1 + pE_0 + (1-p)E_1, \qquad E_{n+m} = 1 + pE_{n+m-1} + (1-p)E_{n+m}.

这是 $n+m+1$ 个未知数的线性方程组：直接高斯消元是 $O(n^3)$ ；即使利用三对角结构消元做到 $O(n)$ ，也会在 $p$ 十分接近 $1/2$ 时遇到主元退化（测试数据 game7 ~ game9 的 $p$ 都在 $0.499$ 附近），需要谨慎处理精度。

第三步：用回返定理一步得到封闭形式。

这条随机游走每一步都至少挪动（或原地反射）一次，从任何状态出发都能以正概率回到 $n$ ，所以状态 $n$ 常返。对常返状态，Kac 回返定理给出：

E[T] = \frac{1}{\pi_n},

其中 $\pi_k$ 是这条链的平稳分布。由细致平衡方程 $\pi_k\,p = \pi_{k-1}(1-p)$ （两个端点的自环不影响转移的对称性，直接解平稳方程也得同一结果）：

\pi_k \propto \left(\frac{p}{1-p}\right)^k, \qquad \pi_k = \frac{(p/q)^k}{\sum_{j=0}^{n+m} (p/q)^j}, \quad q = 1-p.

于是期望回返时间

E[T] = \frac{1}{\pi_n} = \frac{\sum_{j=0}^{n+m} (p/q)^j}{(p/q)^n} = \frac{\sum_{j=0}^{n+m} \binom{n+m}{j} p^j q^{n+m-j}}{\binom{n+m}{n} p^n q^m} = \sum_{k=0}^{n+m} \left(\frac{1-p}{p}\right)^{k-n}.

它也可以从第二步的方程组硬解出来：特征方程 $p\lambda^2 - \lambda + q = 0$ 的根是 $\lambda = 1$ 与 $\lambda = q/p$ ，通项 $E_k = A + B\,r^k$ （ $r = q/p$ ）加上边界对称性 $E_0 = E_{n+m}$ ，解出的封闭形式与上式完全一致——这正是对回返定理结果的代数验证。

如果不想直接引用定理，也可以用平稳分布的含义论证：这条链长期运行时，每回返一次就"消耗"一个回返间隔，而长期处于各状态的比例就是 $\pi$ ，所以平均回返间隔必然是 $1/\pi_n$ 。

第四步：精确计算，绕开浮点溢出。

令 $r = (1-p)/p$ 。当 $p < 1/2$ 时 $r > 1$ ，级数中最大的项 $r^{m}$ 可达 $2^{100}$ ，用 double/long double 逐项累加会有溢出和精度风险（官方 C++ 题解靠"每项为正、乘除交替"侥幸避开，但 Python 里我们有更好的武器：精确整数）。

$p$ 是不超过 6 位的有限小数，把它按小数位数缩放成整数：设 $p = b/s$ （ $s = 10^{\text{小数位数}}$ ， $b$ 为整数）， $q = a/s$ （ $a = s - b$ ）。把通分到 $a^n b^m$ ：

E[T] = \sum_{k=0}^{n+m} \left(\frac{a}{b}\right)^{k-n} = \frac{\sum_{k=0}^{n+m} a^k\, b^{\,n+m-k}}{a^n\, b^m}.

$n + m \leqslant 200$ ，所以分子分母都是不超过 $200 \times 6 = 1200$ 位的整数，Python 大整数精确计算毫无压力；最后用 Decimal（40 位有效数字）做一次除法，误差远小于 $10^{-6}$ 。

整个算法只有 $O(n+m)$ 次大整数乘法。

代码

Python 版：

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38#!/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-02 18:00
# update_at: 2026-10-02 18:00

import sys
from decimal import Decimal, getcontext

PRECISION = 40  # 有效数字 40 位，远超题目 1e-6 的相对误差要求


def solve() -> None:
    getcontext().prec = PRECISION
    it = iter(sys.stdin.read().split())
    n, m = int(next(it)), int(next(it))
    p_text = next(it)
    whole, _, frac = p_text.partition('.')  # 有限小数按位数缩放成整数，全程只用整数运算
    scale = 10 ** len(frac)                 # 缩放系数：小数 6 位时 scale = 10^6
    p_scaled = int(whole or "0") * scale + int(frac or "0")

    # Alice 的宝石数在 [0, n+m] 上随机游走：正面 -1（0 处 Bob 空手，状态不动），
    # 反面 +1（n+m 处 Alice 空手，状态不动），两个端点等价于反射壁。
    # 游戏在 Alice 的宝石数"回到出发值 n"的那个回合结束，由回返定理 E = 1/π(n)，
    # 其中 π(k) ∝ (p/q)^k，于是 E = Σ_{k=0}^{n+m} ((1-p)/p)^{k-n}。
    # 整数化：令 a/b = (scale-p_scaled)/p_scaled，通分 a^n·b^m 后
    # 分子分母都是至多 1200 位的整数，避免浮点误差也避免大分数归约。
    a = scale - p_scaled  # q = 1-p 的缩放分子
    b = p_scaled          # p 的缩放分子
    total = n + m
    num = sum(a ** k * b ** (total - k) for k in range(total + 1))  # Σ a^k·b^{n+m-k}
    den = a ** n * b ** m
    print(f"{Decimal(num) / Decimal(den):.10f}")


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117/**
 * 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-04 23:00
 * update_at: 2026-10-04 23:00
 */
// main.cpp：roj 10021 游戏
// 把 Alice 的宝石数看成 [0, n+m] 上的反射随机游走，游戏结束时它恰好回到出发点 n。
// 由 Kac 回返定理，期望回返时间 E = 1/pi(n)，其中平稳分布 pi(k) 正比于 (q/p)^k，
// 约去公共因子后 E = sum_{k=0}^{n+m} ((1-p)/p)^(k-n)。
// 注意 (1-p)/p 最大约 1e6、指数最大 200，直接求幂会溢出到 1e600；
// 所以先定位最大项、把它提到外面，再用 log10 分离指数与尾数，手工拼出定点小数。
#include <cmath>
#include <cstdio>
#include <iostream>
#include <string>
using namespace std;

typedef long long ll;

ll n, m;      // Alice、Bob 的初始宝石数
ll scale;     // 概率 p 的小数位数对应的 10 的幂，例如 p = 0.125 时 scale = 1000
ll p_scaled;  // p 按 scale 缩放后的整数分子，p = p_scaled / scale
ll q_scaled;  // q = 1 - p 同分母下的整数分子，q_scaled = scale - p_scaled

// 读入 n、m 和有限小数 p。
// p 用字符串读入并按小数位数缩放成整数，避免直接读浮点带来的表示误差。
void read_input() {
    string p_text;
    cin >> n >> m;
    cin >> p_text;

    ll point = p_text.size();  // 小数点位置；没有小数点时保持在末尾
    for (ll i = 0; i < (ll)p_text.size(); i++) {
        if (p_text[i] == '.') point = i;
    }

    scale = 1;
    for (ll i = point + 1; i < (ll)p_text.size(); i++) scale *= 10;

    p_scaled = 0;
    for (ll i = 0; i < (ll)p_text.size(); i++) {
        if (p_text[i] == '.') continue;
        p_scaled = p_scaled * 10 + (p_text[i] - '0');
    }
    q_scaled = scale - p_scaled;
}

// 输出 value * 10^exponent 的定点小数（保留 8 位小数）。
// value 落在 [1, 10)，exponent >= 0，整数部分不足的位用 0 补齐；
// 超出浮点有效位数的低位补 0，相对误差仍可忽略。
void print_scaled(long double value, ll exponent) {
    char buffer[64];
    snprintf(buffer, sizeof(buffer), "%.17Lf", value);

    char digits[64];  // value 的有效数字，去掉小数点后按位存放
    ll len = 0;
    for (ll i = 0; buffer[i] != '\0' && len < 40; i++) {
        if (buffer[i] == '.') continue;
        digits[len] = buffer[i];
        len++;
    }

    string out;
    for (ll i = 0; i <= exponent; i++) out.push_back(i < len ? digits[i] : '0');
    out.push_back('.');
    for (ll i = 0; i < 8; i++) {
        ll pos = exponent + 1 + i;
        out.push_back(pos < len ? digits[pos] : '0');
    }
    printf("%s\n", out.c_str());
}

int main() {
    read_input();

    ll total = n + m;                                              // 宝石总数，也是随机游走状态的上界
    long double r = (long double)q_scaled / (long double)p_scaled;  // 反向概率比 q/p

    // 找出答案 sum r^(k-n) 中绝对值最大的一项所在下标 dominant。
    // r >= 1 时最大项在 k = total（指数为 m），r < 1 时最大项在 k = 0（指数为 -n）。
    ll dominant = total;
    if (r < 1.0L) dominant = 0;

    // 提出最大项后 sum = r^(dominant-n) * s，其中 s = sum r^(k-dominant) 落在 [1, total+1]。
    // 从 dominant 向两侧扩展时每项都不超过 1，因此不会溢出。
    long double s = 1.0L;
    long double term = 1.0L;
    for (ll k = dominant - 1; k >= 0; k--) {
        term /= r;
        s += term;
    }
    term = 1.0L;
    for (ll k = dominant + 1; k <= total; k++) {
        term *= r;
        s += term;
    }

    // log10(答案) = (dominant - n) * log10(r) + log10(s)。
    long double log10_answer = (long double)(dominant - n) * log10l(r) + log10l(s);

    ll exponent = (ll)floorl(log10_answer);
    long double mantissa_part = log10_answer - (long double)exponent;  // 答案的小数尾数部分，落在 [0, 1)
    while (mantissa_part < 0.0L) {
        mantissa_part += 1.0L;
        exponent--;
    }
    while (mantissa_part >= 1.0L) {
        mantissa_part -= 1.0L;
        exponent++;
    }
    long double mantissa = powl(10.0L, mantissa_part);  // 尾数，落在 [1, 10)

    print_scaled(mantissa, exponent);
    return 0;
}

复杂度

设 $N = n + m \leqslant 200$ ， $s \leqslant 10^6$ 。

时间复杂度： $O(N)$ 次大整数乘法，参与运算的整数不超过 $N \log_{10} s \approx 1200$ 位，单次乘法 $O(1200^2)$ 以内，总体在毫秒级。
空间复杂度： $O(1)$ ，只保存当前的分子累加值与两个幂（不存储整张幂表）。
若用 C++ 实现，同样的公式用 long double 计算 $\sum_k r^{k-n}$ 即可（注意 $r^{k-n}$ 有正有负时改成乘除交替，避免 $r > 1$ 方向溢出）。

总结

关键观察 1：终止条件是"Alice 的宝石数回到初始值 $n$ "，游戏求的是回返时间而非首达时间——这一步想错了，后面全错。
关键观察 2：宝石数变化是一个带反射壁的随机游走，由 Kac 回返定理，期望回返时间等于平稳概率的倒数 $1/\pi_n$ ，其中 $\pi_k \propto (p/q)^k$ 。
关键化简： $1/\pi_n$ 约去二项系数与 $p^n q^m$ 后只剩几何级数 $\sum_{k=0}^{n+m} ((1-p)/p)^{k-n}$ ，不用任何方程组。
实现要点：小数按位数缩放成整数、通分 $a^n b^m$ ，用大整数 + Decimal 精确求值，彻底避开 $p \approx 1/2$ 与 $r$ 很大时的浮点问题。

图示解析

最后把整条推导路线串起来，从朴素方程组走到整数化求值：

digraph G {
  rankdir = TB;
  node [shape = box, style = rounded, fontsize = 11];

  a [label = "朴素：E_k 期望方程组\nn+m+1 个未知数", fillcolor = lightyellow, style = "rounded,filled"];
  b [label = "特征方程 pλ²-λ+q=0\n根 λ=1 与 λ=q/p", fillcolor = lightyellow, style = "rounded,filled"];
  c [label = "细致平衡 π_k ∝ (p/q)^k\nKac 定理 E[T] = 1/π_n", fillcolor = lightgreen, style = "rounded,filled"];
  d [label = "几何级数\nE = Σ ((1-p)/p)^(k-n)", fillcolor = lightgreen, style = "rounded,filled"];
  e [label = "p=b/s 整数化，通分 a^n·b^m\n大整数 + Decimal 精确求值", fillcolor = lightblue, style = "rounded,filled"];

  a -> b [label = "硬解方程组"];
  a -> c [label = "换视角：回返时间"];
  c -> d [label = "约去二项系数"];
  b -> d [label = "代数验证，结果一致"];
  d -> e [label = "绕开浮点溢出"];
}

从图里能看出两条殊途同归的路线：左路（朴素方程组 → 特征根）是纯代数推导，右路（细致平衡 → Kac 定理）是概率论证，两者最终都收敛到同一个几何级数。实现层再补最后一块：利用"有限小数"这个输入约束做整数化，让 Python 的精确运算成为可能。

EOF

游戏

目录

形式化题目

正解

思路

代码

复杂度

总结

图示解析