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(){ scanf("%lld%lld",&n,&m); printf("%.6f\n",n*(n-1)/2.0/m); return 0; }
|