menu zcmimi's blog

arrow_back 期望

f_i表示当数列中的数的\gcd=i时,还要再添加的数的期望个数

ans=1+\frac{\sum_{i=1}^n f_i}{n}

显然f_1=0

$f_i=1+\frac{\

zc
2020-01-19 22:14

可以先看一下LG P4868 Preprefix sum,很经典一道题,维护一下后缀和就可以了

这题的话就是把上面

zc
2020-01-18 22:40

```cpp

include<bits/stdc++.h>

namespace ZDY{

#pragma GCC optimize(3)
#define il __inline__ __attr
zc
2019-12-21 19:47

```cpp

include<bits/stdc++.h>

namespace ZDY{

#pragma GCC optimize(3)
#define il __inline__ __attr
zc
2019-12-21 19:47

Easy top: 0


Solution:   期望题总是贼有意思。

  本题期望comboo的期望连续长度的平方,所以我们设f_i表示到了第i位的总期望combo

zc
2019-12-21 19:47

```cpp

include<bits/stdc++.h>

namespace ZDY{

#pragma GCC optimize(3)
#define il __inline__ 
zc
2019-12-21 19:47

```cpp

include<bits/stdc++.h>

using namespace std;

define N 10011

int n; int main(){ double ans=0

zc
2019-12-21 19:47

E_xxn的期望时间

E_x = \sum_i E_i \times p_{xi}\prod_{j=1}^{i-1}(1-p_{xj})

我们可以用类似dij的思想来更新

zc
2019-12-21 19:47

当我们选中一个i

i,i^2,i^3...,i^k都会被去掉

我们设d_t为可以去掉t的数字的个数

ans = \sum_{i=1}^n \frac 1 {d_i}

那么

zc
2019-12-21 19:47

Favorite-Dice top: 0


我是没看题解和标签写出来的,完全不知道这是期望

假设你已经取了i个面,你取到没取过的一个面,概率是\frac {n-i}n

把所有概率加

zc
2019-12-21 19:47
1 / 2
Search
search