钥匙与锁（困难版）

高占晔 @ 2026-5-8 18:21:05

C2. Key of Like (Hard Version) 详细题解

一、问题重述

有 $n$ 个人轮流尝试 $(l + k)$ 把钥匙与 $l$ 把锁的匹配。其中 $l$ 把是真钥匙（与锁一一对应）， $k$ 把是假钥匙。每个人在回合中会选择当前成功概率最大的钥匙‑锁组合。如果有多组最优组合，等概率随机选择。求每个人期望成功匹配的次数，对 $10^9+7$ 取模。

二、策略分析

2.1 初始状态

一开始没有任何信息。第一个人随机选择一把钥匙和一把锁：

概率 $p_{\text{succ}} = \frac{1}{l + k}$ （真钥匙恰好对应这把锁的概率）
概率 $1 - p_{\text{succ}}$ 失败

2.2 第一次失败后的策略

设第一个人选了钥匙 $A$ 和锁 $B$ 且失败。此时已知 $A$ 不是 $B$ 的钥匙，但 $A$ 可能是其他锁的钥匙， $B$ 也可能被其他钥匙打开。

第二个人面临三种选择：

类型	操作	成功概率	等可能组合数
1	同一把锁 $B$ ，不同钥匙	$\frac{1}{l + k - 1}$	$l + k - 1$
2	同一把钥匙 $A$ ，不同锁	$\frac{1}{l + k - 1}$	$l - 1$
3	不同钥匙、不同锁	可通过前两种推导	–

对于第 3 种，共有 $(l + k - 1)$ 种等可能的失败结果。其成功概率为：

$$p_3 = \frac{1 - \frac{1}{l + k - 1}}{l + k - 1} = \frac{l + k - 2}{(l + k - 1)^2} < \frac{1}{l + k - 1} $$

因此第 2 个人不会选择第 3 种，只会选择类型 1 或 2。两种类型的选择概率为：

选同一把锁（类型 1）：概率 $\frac{l + k - 1}{2l + k - 2}$
选同一把钥匙（类型 2）：概率 $\frac{l - 1}{2l + k - 2}$

2.3 后续回合

可以证明：一旦第二个人做出选择，后续所有人都会模仿这一策略——要么一直用同一把钥匙尝试不同锁，要么一直用同一把锁尝试不同钥匙，直到打开或全部试完。

三、动态规划状态与转移

3.1 状态定义

设 $p_{\text{now}}[j][i]$ 表示：在子问题还剩 $l$ 把锁、 $k$ 个假钥匙未识别的情况下，还有 $j$ 个假钥匙未被剔除，当前轮到第 $i$ 个人开始尝试的概率（使用差分存储）。

实际代码中 $p[0]$ 表示当前层， $p[1]$ 表示下一层。

3.2 转移类型

对于当前状态 $(l, k, j)$ ，总剩余钥匙数 $totk = l + k - j$ 。

转移 1 – 第一个人直接成功
概率 $prob = \frac{p[i]}{totk}$

贡献给答案 $e_i$ ： $e[i] += prob$
转移到下一轮 $(l-1, k, j)$ 的第 $(i+1) \bmod n$ 个人。

转移 2 – 第二个人在类型 1/2 中成功
通过系数 $prob$ 和尝试次数计算，并利用 Update 函数批量处理循环区间赋值。

转移 3 – 连续失败
第一个人失败且第二个人失败后，进入“同钥匙”或“同锁”的连续尝试。
利用均匀分布结论：在 $m$ 次尝试中，成功发生在第 $t$ 次尝试的概率均为 $\frac{1}{m}$ 。
据此可 $O(n)$ 计算出每个成员在此阶段获得的期望贡献，并更新到 $e$ 数组。

3.3 差分优化与区间更新

由于 $n$ 个人循环尝试，对 $e$ 和 $p$ 的更新往往落在至多 3 个连续区间（循环意义下）。
使用差分技巧：

Hill：区间 $[l, r)$ 增加等差数列
Valley：区间 $[l, r)$ 减少等差数列
然后统一用前缀和恢复真实值。

四、标程（带详细注释）

#include <cstdio>
#include <cstring>
using namespace std;

#define MOD 1000000007
#define MAXN 108
#define MAXL 5004
#define MAXK 27

int e[MAXN];                     // 最终每个人期望值（差分存储）
int p[2][MAXK][MAXN];            // dp状态：0当前层，1下一层
int inv[2 * MAXL + MAXK];        // 预处理逆元

// 差分更新函数：在 a 数组的 [l, r) 区间（循环意义）加上等差数列
// base 是第一个位置的值，diff 是每次增加的量
inline void _update(int * const a, const int lbd, const int rbd, const int base, const int diff) {
    (a[0] += base) %= MOD;
    (a[lbd] += diff) %= MOD;
    (a[rbd] += MOD - diff) %= MOD;
    return;
}

// 根据区间方向选择 Hill 或 Valley
#define Hill(_a, _lbd, _rbd, _base, _diff) _update(_a, _lbd, _rbd, _base, _diff)
#define Valley(_a, _lbd, _rbd, _base, _diff) _update(_a, _rbd, _lbd, ((_base) + (_diff)) % MOD, MOD - (_diff))
#define Update(_a, _lbd, _rbd, _base, _diff) { if (_lbd < _rbd) Hill(_a, _lbd, _rbd, _base, _diff); else Valley(_a, _lbd, _rbd, _base, _diff); }

int like() {
    int n, l, k;
    scanf("%d %d %d", &n, &l, &k);

    // 特判 n=1 的情况：一个人开所有锁
    if (n == 1) {
        printf("%d\n", l);
        return 0;
    }

    // 预处理逆元（扩展到可能的最大分母 2*l+k）
    inv[1] = 1;
    int max_denom = 2 * l + k;
    for (int i = 2; i <= max_denom; ++i)
        inv[i] = 1ll * (MOD - MOD / i) * inv[MOD % i] % MOD;

    // 初始化 dp
    memset(p, 0, sizeof(p));
    memset(e, 0, sizeof(e));
    p[0][0][0] = 1;          // 初始状态：还有0个假钥匙暴露，从第0个人开始
    p[0][0][1] = MOD - 1;    // 差分标记，方便后面 accumulate

    int now = 0, nxt = 1;    // 滚动数组

    // 主循环：一层一层处理锁
    for (int i = 0; i < l; ++i) {
        for (int j = 0; j <= k; ++j) {
            // 前缀和还原真实概率
            for (int a = 1; a < n; ++a)
                (p[now][j][a] += p[now][j][a - 1]) %= MOD;

            int totk = l + k - i - j;      // 当前未尝试的钥匙总数

            for (int a = 0; a < n; ++a) {
                int prob = 1ll * p[now][j][a] * inv[totk] % MOD;

                // ---- 情况1：第一个人直接成功 ----
                (e[a] += prob) %= MOD;                       // 贡献给答案
                if (a != n - 1) (e[a + 1] += MOD - prob) %= MOD;   // 差分标记结束
                // 转移到下一层 (l-1, k, j) 的下一个人
                (p[nxt][j][(a + 1) % n] += prob) %= MOD;
                if (a != n - 2) (p[nxt][j][(a + 2) % n] += MOD - prob) %= MOD;

                // 再计算一个公共系数（第二个人成功以及后续批量更新要用）
                int prob2 = 1ll * prob * inv[totk + l - i - 2] % MOD;

                // ---- 情况2：第二个人成功，且是“同一锁”类型 ----
                {
                    int ntry = totk - 1;                       // 尝试次数
                    int pd = 1ll * prob2 * ntry % MOD;         // 每次尝试的基础概率
                    int pb = 1ll * (ntry / n) * pd % MOD;      // 完整轮次的基础
                    int dh = ntry % n;                         // 余数

                    if (dh) {
                        int lbd = (a + 1) % n;
                        int rbd = (a + dh) % n + 1;
                        Update(e, lbd, rbd, pb, pd);
                        (++lbd) %= n;
                        ++(rbd %= n);
                        Update(p[nxt][j], lbd, rbd, pb, pd);
                    } else {
                        (e[0] += pb) %= MOD;
                        (p[nxt][j][0] += pb) %= MOD;
                    }
                }

                // ---- 情况3：第二个人成功，且是“同一钥匙”类型（可识别一个假钥匙） ----
                {
                    int ntry = l - i - 1;                     // 尝试次数
                    int pd = 1ll * prob2 * ntry % MOD;
                    // 子情况：这一把钥匙被证明是假钥匙（概率与剩余假钥匙数成正比）
                    if (j < k) {
                        int pb = 1ll * pd * (k - j) % MOD;
                        int b = (a + l - i) % n;               // 下一个人位置
                        (p[now][j + 1][b] += pb) %= MOD;
                        if (b != n - 1) (p[now][j + 1][b + 1] += MOD - pb) %= MOD;
                    }
                    // 子情况：批量失败（同“同一锁”类型的结构）
                    int pb = 1ll * (ntry / n) * pd % MOD;
                    int dh = ntry % n;
                    if (dh) {
                        int lbd = (a + 1) % n;
                        int rbd = (a + dh) % n + 1;
                        Update(e, lbd, rbd, pb, pd);
                        (++lbd) %= n;
                        ++(rbd %= n);
                        Update(p[nxt][j], lbd, rbd, pb, pd);
                    } else {
                        (e[0] += pb) %= MOD;
                        (p[nxt][j][0] += pb) %= MOD;
                    }
                }
            }
        }

        // 交换当前层和下一层，并清空下一层
        now ^= 1;
        nxt ^= 1;
        memset(p[nxt], 0, sizeof(int) * MAXK * MAXN);
    }

    // 最后对 e 做前缀和，还原真实值（因为之前是差分存储）
    for (int i = 1; i < n; ++i)
        (e[i] += e[i - 1]) %= MOD;

    // 输出
    for (int i = 0; i < n; ++i)
        printf("%d%c", e[i], " \n"[i == n - 1]);
    return 0;
}

int main() {
    int t;
    scanf("%d", &t);
    while (t--) {
        like();
    }
    return 0;
}

五、算法复杂度

状态数 $O(l \cdot k) \le 5000 \times 25 = 1.25 \times 10^5$
每个状态转移 $O(n) \le 100$ （得益于差分区间更新）
总时间复杂度 $O(n \cdot l \cdot k) \approx 1.25 \times 10^7$ ，在时限内可运行

六、关键技巧总结

策略化简：通过概率比较，证明第 2 个人之后的策略只有两种（同钥匙或同锁）
均匀概率：失败序列中成功位置的均匀分布，简化期望计算
差分优化：用差分数组处理区间批量更新，避免 $O(n^2)$
循环分配：利用 $n$ 个人循环，将连续尝试次数分段处理（最多 3 段）
模逆预处理：一次性计算所有分母的逆元，加速除法

七、示例验证

样例 1：3 1 4 输出 800000006 800000006 400000003
对应期望 $\frac{2}{5}, \frac{2}{5}, \frac{1}{5}$ ✅

样例 2：3 2 0 输出 500000004 1 500000004
对应期望 $\frac12, 1, \frac12$ ✅

八、结语

本题巧妙地将概率游戏转化为动态规划问题，通过策略分析和数学优化，在 $O(nlk)$ 时间内求解。代码实现的难点在于利用差分和循环分段更新，确保效率满足 $l$ 总和不超过 $5000$ 的约束。

ID

7022

时间

1000ms

内存

256MiB

难度

标签

递交数

已通过

上传者

高占晔

1 条题解