思路：组合数学+贡献法计数

我们可以先去计算所有方案的总和，然后除以方案数$c$，即为最终的期望，其中$c=C(n,2)=\frac{n\times (n-1)}{2}$

我们可以考虑每一个元素对答案的贡献

对于元素$x$，记其在$n$组卡片出现的个数为$k$

• $k=1$，即只有一组卡片出现过，那么对答案的贡献为$n-1$

• $k\ge 2$，那么有两种情况

情况1：选择的两组卡片，都含有元素$x$

情况2：选择的两组卡片，只有一组含有元素$x$

我们可以先考虑选择的两组卡片，至少有一组含有元素$x$，对应的方案数为$k\times (n-1)$，但是上述计算会把情况1多算一次，因此还需要把情况1对答案的贡献去除，情况1对应的贡献为$\frac{k\times (k-1)}{2}$

时间复杂度

$O(n)$

代码

C++

#include <bits/stdc++.h> 
using namespace std;

int main() {
    unordered_map<int, int> mp;
    int n;
    cin >>n;
    for (int i=0; i<n; i++) {
        int m;
        cin>>m;
        while (m--) {
            int x;
            cin >> x;
            mp[x]++;
        }
    }
    long long sum = 0;
    for (auto p : mp) {
        int k = p.second;
        if(k==1){
            sum+=1ll*k*(n-1);
        }
        else{
            sum += k*(n-1) - k*(k-1)/2;
        }

    }
    long long c=1ll*n*(n-1)/2;
    printf ("%.7f", (double)sum /c);
}

python代码

n = int(input().strip())
mp = {}
for _ in range(n):
    w = list(map(int,input().split()))
    for i in range(1,len(w)):
        x = w[i]
        if x in mp:
            mp[x] += 1
        else:
            mp[x] = 1
sum = 0
for k in mp.values():
    if k == 1:
        sum += k * (n - 1)
    else:
        sum += k * (n - 1) - k * (k - 1) // 2
c = n * (n - 1) // 2
print("{:.7f}".format(sum / c))

Java代码

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < n; i++) {
            int m = scanner.nextInt();
            while (m-- > 0) {
                int x = scanner.nextInt();
                map.put(x, map.getOrDefault(x, 0) + 1);
            }
        }
        long sum = 0;
        for (int k : map.values()) {
            if (k == 1) {
                sum += (long) k * (n - 1);
            } else {
                sum += (long) k * (n - 1) - (long) k * (k - 1) / 2;
            }
        }
        long c = (long) n * (n - 1) / 2;
        System.out.printf("%.7f", (double) sum / c);
    }
}

题目描述

小美有很多组卡片，每个卡片上有一个值。现在他想随意取出两组卡片将他们混在一起，这时他会剔除值相同的卡片，将每个值相同的卡片只留下一张，现在他想知道他这个操作得到的新的一组卡片的个数的期望是多少。

输入描述

第一行一个整数$n$,表示有$n$组卡片($2 \leq n \leq 200000$)。

接下来$n$行，每行第一个整数$m$，表示这个卡组有$m$张卡片，接下来有$m$个整数$a_i$，表示每个卡片上的值($1 \leq n \leq 10^9$)。数据保证每个卡组中的卡片值互不相同，并且所有集合的长度之和不超过200000。

输出描述

输出一个浮点数，表示新卡组的个数的期望。如果你的答案和标准答案的相对误差不超过10^-7，则认为答案正确。

样例

输入

2
5 1 2 3 4 5
4 1 2 3 4

输出

5.00000000000

说明

只有两个卡组，则一定会取这两个数组，并集为1,2,3,4,5，则期望为5。