JZOJ5949. 【NOIP2018模拟11.04】人生赢家

JZOJ5949. 【NOIP2018模拟11.04】人生赢家

Description

众所周知，DH是一位人生赢家，他不仅能虐暴全场，而且还正在走向人生巅峰；
在巅峰之路上，他碰到了这一题：
每次生成一个[0,n)的随机整数，如果这个随机数和给出的m个数字中的其中一个数字相等，那么就停止生成随机数，否则继续生成，求出所有生成的数的和的期望。

题解

其实答案与m个数是什么没有任何关系。
设在第i次的时候选到了m个数中的一个，
那么答案就是 ∑ i = 1 ( ( n − m ) / n ) i − 1 / n ∗ ( ∑ j = 1 n j ) sum _{i=1}((n-m)/n)^{i-1}/n*(sum_{j=1}^n j) ∑i=1​((n−m)/n)i−1/n∗(∑j=1n​j)
化简一下就可以得到答案：n*(n-1)/2/m
注意精度就可以了。

code

#include<cstdio>
#include<algorithm>
using namespace std;
long long n,m;
long double V;
int main()
{freopen("winner.in","r",stdin);freopen("winner.out","w",stdout);scanf("%lld%lld",&n,&m);V=1.0;V=V*n/m*(n-1)/2;printf("%.6lf",(double)V);
}