Moe's CF Life

Appearance

D. Santa's Bot - 题解 ​

比赛与标签 ​

比赛: Educational Codeforces Round 79 (Rated for Div. 2) 标签: combinatorics, math, probabilities 难度: *1700

题目大意喵~ ​

各位Master好呀，喵~ 这道题是关于圣诞老人和他的小助手机器人的故事哦！

有 n 个小朋友，每个小朋友 i 都有一个愿望单，上面有 k_i 个他们想要的礼物。

圣诞老人的机器人助手出了点小问题，它会按下面的奇妙三步曲来决定送礼物：

  1. 等概率地在 n 个小朋友中选择一个小朋友 x。
  2. 等概率地在小朋友 x 的 k_x 个愿望中选择一个物品 y。
  3. 再等概率地在 n 个小朋友中选择一个小朋友 z，把礼物 y 送给他。

一个决策 (x, y, z) 被认为是“有效的”，当且仅当收到礼物的小朋友 z 的愿望单里，正好有物品 y。

我们的任务就是，计算这个机器人的一次决策是“有效的”概率是多少。因为答案可能是一个分数，题目要求我们对 998244353 取模输出结果呐。

解题思路呐~ ​

嘿嘿，这是一道概率题，看起来有点绕，但别怕，跟着我的思路一步步来，问题就会变得很清晰的喵~

首先，我们来分析一下机器人做出任何一个特定决策 (x, y, z) 的概率是多少。

  • 第一步，从 n 个小朋友中选出 x 的概率是 1/n。
  • 第二步，从 x 的 k_x 个愿望中选出 y 的概率是 1/k_x。
  • 第三步，从 n 个小朋友中选出 z 的概率是 1/n。

因为这三步是相互独立的，所以选出特定三元组 (x, y, z) 的总概率就是这三者相乘： P(x, y, z) = P(x) * P(y | x) * P(z) = (1/n) * (1/k_x) * (1/n) = 1 / (n^2 * k_x)

好啦，现在我们知道了选出任意一个组合的概率。那一个“有效”决策的总概率是多少呢？当然是把所有“有效”的 (x, y, z) 组合的概率加起来啦！

P(有效) = Σ_{所有有效的(x, y, z)} P(x, y, z)

一个组合 (x, y, z) 是有效的，条件是小朋友 z 的愿望单里包含物品 y。我们可以把这个求和公式写得更具体一点：

P(有效) = Σ_{x=1 to n} Σ_{y in W_x} Σ_{z=1 to n, 且 z 想要 y} (1 / (n^2 * k_x)) 其中 W_x 是小朋友 x 的愿望单。

这个三层求和看起来好可怕呀！(>ω<) 但是不要慌，我们来施展一个魔法——交换求和次序，让它变简单！

注意到 1 / (n^2 * k_x) 这一项只和 x 有关，我们可以把它提到内层求和的外面去：

P(有效) = Σ_{x=1 to n} (1 / (n^2 * k_x)) * [ Σ_{y in W_x} (Σ_{z=1 to n, 且 z 想要 y} 1) ]

再把只和 n 有关的 1/n^2 也提出来：

P(有效) = (1/n^2) * Σ_{x=1 to n} (1/k_x) * [ Σ_{y in W_x} (Σ_{z=1 to n, 且 z 想要 y} 1) ]

现在，我们来仔细看看最里面的那个求和 Σ_{z=1 to n, 且 z 想要 y} 1。这不就是“想要物品 y 的小朋友总人数”嘛！我们可以预处理一下，用一个数组 count[y] 来表示想要物品 y 的人数。

这样一来，公式就变成了：

P(有效) = (1/n^2) * Σ_{x=1 to n} [ (1/k_x) * Σ_{y in W_x} count[y] ]

哇！这个公式是不是清晰多啦？喵~ 它的计算步骤就是：

  1. 预处理：遍历所有小朋友的所有愿望，用一个 item_counts 数组统计出每个物品被多少个小朋友喜欢。
  2. 计算总和：
    • 遍历每一个小朋友 x (从 1 到 n)。
    • 对于每个小朋友 x，计算一个内部和 inner_sum。这个和就是遍历 x 的所有愿望 y，然后把 item_counts[y] 加起来。
    • 算完 inner_sum 后，乘以 1/k_x。
    • 把这个结果累加到一个总和 total_sum 上。
  3. 最终结果：最后，把 total_sum 乘以 1/n^2，就是我们的答案啦！

在计算过程中，因为有除法，并且要对 998244353 这个质数取模，所以我们需要用到乘法逆元。我们可以预处理出 1 到 10^6 所有整数的逆元，这样计算 1/n 和 1/k_x 的时候就非常快了。

代码实现喵！ ​

cpp
#include <iostream>
#include <vector>
#include <numeric>

// 加速一下I/O，让程序跑得飞快喵~
void setup_io() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
}

// 定义一些常量
const int MOD = 998244353;
const int MAX_SIZE = 1000001; // n, k_i, 物品ID的最大值

// 使用全局数组来避免栈溢出，也更高效哦
// 预计算的模逆元数组
long long inv[MAX_SIZE];
// 统计每个物品被多少小朋友喜欢的频率数组
long long item_counts[MAX_SIZE] = {0};
// 存储每个小朋友的愿望单
std::vector<int> wishes[MAX_SIZE];
// 存储每个小朋友的愿望数量 k_i
int k_values[MAX_SIZE];

// 线性时间预处理模逆元，是个很有用的技巧呢！
void precompute_inverses() {
    inv[1] = 1;
    for (int i = 2; i < MAX_SIZE; ++i) {
        // 使用递推公式 inv[i] = -(MOD / i) * inv[MOD % i] (mod MOD)
        // 加上 MOD 是为了保证结果是正数，喵~
        inv[i] = MOD - (MOD / i) * inv[MOD % i] % MOD;
    }
}

int main() {
    setup_io();
    precompute_inverses();

    int n;
    std::cin >> n;

    // 读取输入，同时填充我们的数据结构
    for (int i = 0; i < n; ++i) {
        std::cin >> k_values[i];
        wishes[i].resize(k_values[i]);
        for (int j = 0; j < k_values[i]; ++j) {
            std::cin >> wishes[i][j];
            // 每读到一个物品，就给它的计数器加一
            item_counts[wishes[i][j]]++;
        }
    }

    // 这就是我们推导出的核心公式啦！
    // P = (1/n^2) * sum_{x=1 to n} [ (1/k_x) * sum_{y in W_x} count(y) ]
    // 我们先计算 Σ [ (1/k_x) * Σ count[y] ] 这部分
    long long total_sum_over_x = 0;
    
    // 遍历每个小朋友 x (这里用索引 i 表示)
    for (int i = 0; i < n; ++i) {
        // 计算内部的和，即 sum_{y in W_x} count(y)
        long long inner_sum = 0;
        for (int item : wishes[i]) {
            inner_sum = (inner_sum + item_counts[item]) % MOD;
        }
        
        // 乘以 1/k_x (也就是 k_x 的逆元)
        long long inv_k = inv[k_values[i]];
        long long term = (inner_sum * inv_k) % MOD;
        
        // 把当前小朋友的贡献加到总和里
        total_sum_over_x = (total_sum_over_x + term) % MOD;
    }

    // 最后，再乘上 (1/n) * (1/n) 就大功告成！
    long long inv_n = inv[n];
    long long inv_n_sq = (inv_n * inv_n) % MOD;

    long long final_prob = (total_sum_over_x * inv_n_sq) % MOD;
    
    std::cout << final_prob << std::endl;

    return 0;
}

复杂度分析的说 ​

  • 时间复杂度: O(N + Σkᵢ + MAX_ID) 的说。

    • 我们需要 O(MAX_ID) 的时间来预处理逆元，其中 MAX_ID 是物品ID和n的最大可能值（10^6）。
    • 读取输入并统计 item_counts 的时间是 O(Σkᵢ)。
    • 主循环计算总和的时间也是 O(Σkᵢ)。
    • 因为题目保证了 Σkᵢ ≤ 10^6，所以总的时间复杂度非常优秀，完全可以通过！

  • 空间复杂度: O(N + Σkᵢ + MAX_ID) 的说。

    • 我们需要 O(MAX_ID) 的空间来存储 inv 数组和 item_counts 数组。
    • 存储所有小朋友的愿望单需要 O(Σkᵢ) 的空间。
    • 这在题目给的256MB内存限制下是绰绰有余的。

知识点与总结~ ​

这道题真是一次愉快的数学与编程结合之旅呢，喵~！

  1. 概率论基础与期望: 核心思想是利用概率的加法法则和乘法法则。最关键的一步是将问题形式化为一个求和公式，然后通过交换求和顺序来简化计算。这种思想在组合数学和期望问题中非常常见，Master们要好好掌握哦！

  2. 模运算与乘法逆元: 只要是在质数模意义下进行计算，一看到除法，就要立刻想到它的好朋友——乘法逆元！使用 inv[i] = -(MOD / i) * inv[MOD % i] % MOD 这个递推式来线性预处理逆元，是一个必须学会的快速技巧呐。

  3. 预处理思想: “空间换时间”的经典应用！我们没有在每次需要 count[y] 的时候都去重新计算，而是提前遍历一遍，把所有 count[y] 都存起来。同样，逆元也是预处理好的。这让我们的主逻辑变得既清晰又高效。

希望这篇题解能帮助到你！只要把复杂的问题拆解成一个个小部分，再用正确的数学工具去分析，难题也会变得可爱的说！大家继续加油哦，喵~ (ฅ'ω'ฅ)

Released under the MIT License.

Copyright © 2024-present Moe