我们可以先去计算所有方案的总和,然后除以方案数c,即为最终的期望,其中c=C(n,2)=2n×(n−1)
我们可以考虑每一首歌曲对答案的贡献
对于歌曲编号x,记其在n个歌单中出现的次数为k
小蓝正在分析一个音乐平台的数据。平台上有 n 名用户,每名用户拥有一个私人歌单,歌单中包含若干首歌曲,同一歌单内歌曲编号互不相同。小蓝从这 n 名用户中随机等概率地选取两名不同的用户,将他们的歌单合并,并剔除重复的歌曲,形成一个联合歌单。他想知道这个联合歌单中歌曲数量的期望值。
歌单数量 n 满足 2≤n≤ 200000。所有歌单的歌曲总数不超过 200000。歌曲编号均为不超过 10^9 的正整数。
第一行包含一个整数 n,表示歌单的数量。 接下来 n 行,每行对应于一个歌单。每行首先是一个整数 mi,表示该歌单包含的歌曲数量,随后是 mi 个互不相同的正整数,表示歌曲编号。
By signing up a CodeFun2000 universal account, you can submit code and join discussions in all online judging services provided by us.