C. C. Blog

Security Research, Algorithm and Data Structure

51Nod 1765 谷歌的恐龙

Problem

把整个游戏简化为,每次生成一个[0,n)的随机数,如果这个随机数和给出的m个数字中的其中一个数字相等,那么就停止生成随机数,否则继续生成,求出所有生成的数的和的期望。

Solution

\[E = \sum_{i=0}^{n-1} p_i \times(i+[flag_i]\times E), p_i = \frac{1}{n}, 如果i不在m个数中, flag_i = 1, 否则为0。\]

化简为\[ E = \frac{n\times(n-1)}{2\times m} \]

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include<stdio.h>
#include<set>
#include<deque>
#include<iostream>
#include<stack>
#include<cstring>
#include<cmath>
#include<vector>
#include<algorithm>
typedef long long ll;
typedef long double ld;
typedef double db;
#define io_opt ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
using namespace std;
const int mod=998244353;
int mo(ll a,int p){
return a>=p?a%p:a;
}
inline int rd() {
int x = 0, f = 1;
char ch;
while (ch < '0' || ch > '9') {
if (ch == '-')f = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9') {
x = x * 10 + ch - '0';
ch = getchar();
}
return f * x;
}
ll n,m,x;
int main(){
//io_opt;
scanf("%lld%lld",&n,&m);

printf("%.6f\n",n*(n-1)/2.0/m);
return 0;
}
  • 本文作者: CCWUCMCTS
  • 本文链接: https://ccwucmcts.github.io/posts/31378/
  • 版权声明: 本博客所有文章除特别声明外,均采用 BY-NC-SA 许可协议。转载请注明出处!