Good Trip
算法本质
思维、概论
题目大意
有n个孩子，其中有m对朋友，每对朋友有一个初始的友情值。
初始分数为0，接下来会进行k轮游戏，每轮游戏会随机选择2个孩子，如果这2个孩子是朋友：
- 这对朋友的友情值+1
- 获得这对朋友友情值的分数
如果不是朋友，则无事发生
输出最后分数的期望值。（mod 1e9+7）
n,m <= 1e5
k <= 2e5思路推演
分数的增加首先需要发生在朋友上，所以我们可以将$\frac{n*(n-1)}{2}$种情况为了m种朋友情况和其他。
我们将分数的获取分成两类，初始值友情分数和后续增加的友情分数，即这2个子问题：
- 如果规则中，友情值不会改变
- 如果规则中，友情值都默认为0
第一个问题易于解决，简单的平均值可以搞定。
对于第二个问题，这是一个比较经典情景，我们以单对朋友的视角来看，如果抽中他们x次，则收益是$\frac{x*(x-1)}{2}$，每次抽中的概论$p=\frac{2}{n(n-1)}$，一共抽k轮，则期望收益就是：
- $\sum_{i=0}^k\C_k^ip^i(1-p)^{k-i}\frac{i*(i-1)}{2}$
这是单对朋友的期望收益，我们乘以m就可以得到所有朋友的增加友情分数的期望收益了。
思路推演 - 进阶
实际上这道题仍然有发挥空间：$\sum_{i=0}^k\C_k^ip^i(1-p)^{k-i}\frac{i*(i-1)}{2} * 2= \sum_{i=0}^k\C_k^ip^i(1-p)^{k-i}i^2 - \sum_{i=0}^k\C_k^ip^i(1-p)^{k-i}i$
$\sum_{i=0}^k\C_k^ip^i(1-p)^{k-i}i$是二项式分布的期望$E(x)$，我们可以使用kp来O(1)计算。
$\sum_{i=0}^k\C_k^ip^i(1-p)^{k-i}i^2$也可以看作是其的一种简单变形$E(x^2)$，根据概率论中的知识，使用$E(x^2) = D(x)+E(x)^2 = kp(1-p)+k^2p^2$来O(1)计算。
所以实际上可以做到O(t)的复杂度（因为有多组数据），虽然在这道题上没有意义。
ac核心代码
头文件、宏定义、快读模板、常见变量、常见变量等略。
title
算法本质
题目大意
思路推演
ac核心代码
头文件、宏定义、快读模板、常见变量、常见变量等略。
title
算法本质
题目大意
思路推演
ac核心代码
头文件、宏定义、快读模板、常见变量、常见变量等略。
title
算法本质
题目大意
思路推演
ac核心代码
头文件、宏定义、快读模板、常见变量、常见变量等略。
title
算法本质
题目大意
思路推演
ac核心代码
头文件、宏定义、快读模板、常见变量、常见变量等略。
title
算法本质
题目大意
思路推演
ac核心代码
头文件、宏定义、快读模板、常见变量、常见变量等略。
评论 (0)