小魔女帕琪的题解

记住只在没有思路时使用题解，不要从它复制粘贴代码。请尊重题目和题解的作者。
在解题之前提交题解的代码会导致封禁。

作者： admin

概述

本题要求计算在 $N$ ~N~ 个能量晶体的等概率随机消耗顺序中，连续 $7$ ~7~ 个魔法属性互不相同这一事件被触发的期望次数，答案保留三位小数。核心解法是用期望的线性性把总期望拆成 $N - 6$ ~N - 6~ 个长度为 $7$ ~7~ 的窗口各自的触发概率之和，再由随机排列的对称性把每个窗口的概率化成同一个乘积式，一次乘除即可算出答案。

分析

核心观察

每次施放都从当前剩余的晶体中等概率取走一个，因此整段施法序列是全部 $N$ ~N~ 个晶体的一个均匀随机排列：所有 $N!$ ~N!~ 种消耗顺序等概率出现。把触发总次数写成 $N - 6$ ~N - 6~ 个指示变量之和，其中第 $j$ ~j~ 个指示变量标记第 $j$ ~j~ 到第 $j + 6$ ~j + 6~ 个魔法是否属性互不相同，则由期望的线性性，总期望等于这 $N - 6$ ~N - 6~ 个事件的概率之和，事件之间的相关性完全不需要处理。又因为随机排列的对称性，任意一个长度 $7$ ~7~ 的窗口取到什么内容，分布都与最前面 $7$ ~7~ 个位置相同，于是所有窗口的概率是同一个值。

思路

设 $N = \sum_{i = 1}^{7} a_i$ ~N = \sum_{i = 1}^{7} a_i~，长度为 $7$ ~7~ 的窗口共有 $N - 6$ ~N - 6~ 个，其中每个窗口合法的概率都等于最前面 $7$ ~7~ 个位置恰好七种属性各出现一次的概率。

逐个位置计算这个概率。第 $1$ ~1~ 个位置取到属性 $i$ ~i~ 的概率是 $a_i / N$ ~a_i / N~；属性 $i$ ~i~ 的晶体被消耗一个之后，第 $2$ ~2~ 个位置取到属性 $j$ ~j~ 的概率是 $a_j / (N - 1)$ ~a_j / (N - 1)~；继续下去，第 $k$ ~k~ 个位置对应分母 $N - k + 1$ ~N - k + 1~，分子是该属性的剩余数量。七种属性各出现一次的相对顺序共有 $7!$ ~7!~ 种，每种顺序对应的概率都是同一个乘积，因此单个窗口合法的概率为

$\displaystyle p = \frac{7! \, \prod_{i = 1}^{7} a_i}{\prod_{k = 0}^{6} (N - k)}$

把它乘上窗口数 $N - 6$ ~N - 6~，恰好与分母中最后一项 $N - 6$ ~N - 6~ 约掉，得到

$\displaystyle E = (N - 6) \, p = \frac{7! \, \prod_{i = 1}^{7} a_i}{N (N - 1)(N - 2)(N - 3)(N - 4)(N - 5)}$

这就是最终答案，其中 $7! = 5040$ ~7! = 5040~。分母只有 $6$ ~6~ 个因子，含义是「窗口数已经乘进来了」；若写成先求单个窗口概率 $7! \times \frac{a_1}{N} \times \frac{a_2}{N - 1} \times \cdots \times \frac{a_7}{N - 6}$ 、再乘窗口数 $N - 6$ ~N - 6~ 的两步形式，化简后与上式完全相同。

枚举全部 $N!$ ~N!~ 种消耗顺序逐一统计的朴素做法在 $N$ ~N~ 可达 $10^9$ ~10^9~ 时完全不可行，而上式只需常数次乘除运算，与 $N$ ~N~ 的大小无关。

若某个 $a_i = 0$ ~a_i = 0~，则任何窗口都必然缺少第 $i$ ~i~ 种属性，答案恒为 $0$ ~0~。此时上式分子为 $0$ ~0~，直接输出 0.000 即可，同时也避免了 $N < 7$ ~N < 7~ 时分母出现因子 $0$ ~0~ 导致除零。

具体示例

样例 $a = (1, 1, 1, 1, 1, 1, 1)$ ~a = (1, 1, 1, 1, 1, 1, 1)~ 中 $N = 7$ ~N = 7~，窗口只有 $1$ ~1~ 个，每个窗口必然合法：

$\displaystyle E = \frac{5040 \times 1}{7 \times 6 \times 5 \times 4 \times 3 \times 2} = \frac{5040}{5040} = 1$

输出 1.000，与样例一致。

再取 $a = (2, 2, 2, 2, 2, 2, 2)$ ~a = (2, 2, 2, 2, 2, 2, 2)~，此时 $N = 14$ ~N = 14~，窗口数 $N - 6 = 8$ ~N - 6 = 8~：

$\displaystyle E = \frac{5040 \times 2^7}{14 \times 13 \times 12 \times 11 \times 10 \times 9} = \frac{645120}{2162160} \approx 0.298368$

输出 0.298；先算单窗口概率 $645120 / 17297280 \approx 0.037296$ ~645120 / 17297280 \approx 0.037296~ 再乘窗口数 $8$ ~8~，结果相同。

反向的极端情形是某个 $a_i = 0$ ~a_i = 0~，例如 $a = (0, 1, 1, 1, 1, 1, 1)$ ~a = (0, 1, 1, 1, 1, 1, 1)~，无论怎么消耗都凑不齐 $7$ ~7~ 种属性，期望为 $0$ ~0~，输出 0.000。

算法步骤

读入 $7$ ~7~ 个整数存入数组 a，同时累加得到晶体总数 n。
若 a 中存在 $0$ ~0~，说明无论如何都无法触发，输出 0.000 并结束。
令浮点变量 ans 为 $5040$ ~5040~，依次乘上 a 中的每一个元素，得到 $5040 \prod a_i$ ~5040 \prod a_i~。
令 ans 依次除以 n、n 减 $1$ ~1~、……、n 减 $5$ ~5~，共 $6$ ~6~ 次除法。
输出 ans，四舍五入保留三位小数。

复杂度分析

时间： $O(1)$ ~O(1)~。只有 $13$ ~13~ 次浮点乘除运算，与 $N$ ~N~ 和各个 $a_i$ ~a_i~ 的大小无关。
空间： $O(1)$ ~O(1)~。只需存 $7$ ~7~ 个整数与一个浮点累加变量。

实现注意事项

分子 $5040 \prod a_i$ ~5040 \prod a_i~ 最大可达 $6 \times 10^{60}$ ~6 \times 10^{60}~ 量级，远超 $64$ ~64~ 位整数范围，必须用浮点类型（double 或 long double）承载。
遇到 $a_i = 0$ ~a_i = 0~ 必须提前输出 0.000：此时 $N$ ~N~ 可能小于 $7$ ~7~，公式分母会退化为 $0$ ~0~，甚至出现 $0 / 0$ ~0 / 0~。
分母是 $N, N - 1, \ldots, N - 5$ ~N, N - 1, \ldots, N - 5~ 共 $6$ ~6~ 个因子，已经包含了窗口数 $N - 6$ ~N - 6~，不要再额外乘窗口数或再除以 $N - 6$ ~N - 6~。
精度没有风险：答案的整数部分最大约 $6 \times 10^{6}$ ~6 \times 10^{6}~，双精度相对误差约 $10^{-16}$ ~10^{-16}~，折算到小数点后第三位的绝对误差不到 $10^{-9}$ ~10^{-9}~；各测试点中期望值距离最近的舍入边界也还有约 $8 \times 10^{-5}$ ~8 \times 10^{-5}~ 的余量，因此先乘后除与先除后乘得到的输出完全相同，无需刻意安排运算顺序。
大数值下不要用整数运算中转：乘积在整数类型中会溢出。
输出必须严格是三位小数并在行末换行，C++ 用 %.3f（long double 时为 %.3Lf），Python 用 f"{ans:.3f}"。

源代码

#include <cstdio>

int main() {
    long long a[7];
    long long n = 0;
    for (int i = 0; i < 7; ++i) {
        if (std::scanf("%lld", &a[i]) != 1) return 0;
        n += a[i];
    }
    for (int i = 0; i < 7; ++i) {
        if (a[i] == 0) {          // 缺少任意一种晶体，永远无法凑齐 7 种属性
            std::printf("0.000\n");
            return 0;
        }
    }
    long double ans = 5040.0L;    // 7!
    for (int i = 0; i < 7; ++i) ans *= static_cast<long double>(a[i]);
    for (int k = 0; k < 6; ++k) ans /= static_cast<long double>(n - k);
    std::printf("%.3Lf\n", ans);
    return 0;
}

import sys


def main():
    data = sys.stdin.buffer.read().split()
    a = [int(x) for x in data[:7]]
    n = sum(a)
    if any(x == 0 for x in a):
        print("0.000")
        return
    ans = 5040.0  # 7!
    for x in a:
        ans *= x
    for k in range(6):
        ans /= n - k
    print(f"{ans:.3f}")


if __name__ == "__main__":
    main()

目前没有评论。