题目分析

有 $M$ 个初始题目，每个对应一个独特想法。通过组合两个现有题目可以生成新题目，新题目的想法集合是这两个题目想法集合的并集。需要估计每个组合题目的想法集合大小。

由于 $N$ 可达 $10^6$，直接计算集合并集不可行，需要使用随机化方法进行近似估计。

解题思路

核心思想

使用最小值采样的概率计数方法：

• 为每个初始想法分配随机数
• 组合题目的随机值取子题目随机值的最小值
• 通过多次实验求平均值来估计集合大小

数学原理

对于均匀随机变量，集合最小值的期望与集合大小成反比：

算法步骤

1. 读入数据：题目数量和组合关系
2. 多次独立实验：进行200次随机实验
3. 随机值分配：为初始想法生成随机数
4. 传播最小值：按组合关系计算每个题目的随机值
5. 估计大小：根据累加结果估计集合大小

完整代码

#include <bits/stdc++.h>

#ifdef LOCAL
#include <debug.h>
#else
#define debug(...)
#define debug_arr(...)
#define debug_endl(...)
#endif

using u32 = unsigned int;

// 随机数生成器
std::mt19937 rng(std::chrono::steady_clock::now().time_since_epoch().count());

void solve() {
    int n, m;
    std::cin >> n >> m;

    // 存储组合关系：u[i]和v[i]组合成第i个题目
    std::vector<int> u(n), v(n);

    // 读入组合关系（题目编号从1开始，转换为从0开始）
    for (int i = m; i < n; i++) {
        std::cin >> u[i] >> v[i];
        u[i]--;  // 转换为0-based索引
        v[i]--;
    }

    // s[i] 存储第i个题目在多次实验中的随机值之和
    std::vector<unsigned long long> s(n, 0ull);

    // 进行200次独立实验
    for (int experiment = 0; experiment < 200; experiment++) {
        std::vector<u32> dp(n);  // 存储当前实验中各题目的随机值

        // 为初始想法分配随机值
        for (int j = 0; j < m; j++) {
            dp[j] = rng();  // 生成32位随机数
        }

        // 按组合关系传播随机值
        for (int j = m; j < n; j++) {
            // 组合题目的随机值取两个子题目随机值的最小值
            dp[j] = std::min(dp[u[j]], dp[v[j]]);
            // 累加到总和
            s[j] += dp[j];
        }
    }

    // 输出估计结果
    for (int i = m; i < n; i++) {
        // 使用经验公式估计集合大小
        // 858993459000 是根据随机数范围和实验次数调整的常数
        int estimated_size = static_cast<int>(1.0 * 858993459000 / s[i] - 0.5);
        std::cout << estimated_size << "\n";
    }
}

int main() {
    // 优化输入输出
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    // 设置输出精度（虽然本题输出整数，但保持一致性）
    std::cout.setf(std::ios::fixed);
    std::cout.precision(10);

    solve();

    return 0;
}

代码说明

关键数据结构

• u[i], v[i]：存储组合关系，题目 i 由题目 u[i] 和 v[i] 组合而成
• s[i]：存储题目 i 在多次实验中的随机值累加和
• dp[i]：单次实验中各题目的随机值

算法流程详解

1. 数据读入与预处理：

   for (int i = m; i < n; i++) {
       std::cin >> u[i] >> v[i];
       u[i]--; v[i]--;  // 转换为0-based索引
   }
   

2. 多次独立实验：

   for (int experiment = 0; experiment < 200; experiment++) {
       // 每次实验重新生成随机数
   }
   

3. 随机值传播：

   for (int j = m; j < n; j++) {
       dp[j] = std::min(dp[u[j]], dp[v[j]]);
       s[j] += dp[j];
   }
   

   • 组合题目的想法集合是子题目集合的并集
   • 取最小值操作模拟了集合并集的最小随机值特性

4. 大小估计：

   int estimated_size = static_cast<int>(1.0 * 858993459000 / s[i] - 0.5);
   

   • 基于数学原理：集合大小的倒数与最小随机值的期望成正比
   • 常数 858993459000 根据32位随机数范围和200次实验校准

数学背景

对于均匀分布在 $[0,1]$ 的随机变量，集合 $S$ 的最小值 $X_{\min}$ 满足：

在实际实现中，使用32位整数随机数，需要相应调整常数因子。

复杂度分析

• 时间复杂度：$O(K \cdot N)$

  • $K = 200$ 次实验
  • $N$ 个题目
  • 总操作数约 $2 \times 10^8$，在可接受范围内

• 空间复杂度：$O(N)$

  • 存储组合关系和累加结果