题意: N个礼品箱, 每个礼品箱内的礼品只有第一个抽到的人能拿到. M个小孩每个人依次随机抽取一个, 求送出礼品数量的期望值. 1 ≤ N, M ≤ 100, 000
挺水的说..设f(x)表示前x个人都选择完成后礼品剩下数的期望值( f(0) = N ), 那么f(x) = f(x - 1) - f(x - 1) / N = f(x - 1) * (N - 1) / N (显然). 那么答案就是等于 N - N * [(N - 1) / N]^M. 后面部分可以用快速幂优化.时间复杂度O(log M). 数据这么小不用快速幂O(M)应该也能过...
#include using namespace std;double POW(double p, int a) {double ans = 1;for(; a; a >>= 1) {if(a & 1) ans = p;p = p;}return ans;}int main() {int N, M;scanf("%d%d", &N, &M);printf("%.9lfn", N - POW(1.0 * (N - 1) / N, M) * N);return 0;}
495. Kids and Prizes
Time limit per test: 0.25 second(s)
Memory limit: 262144 kilobytesinput: standard
output: standard
ICPC (International Cardboard Producing Company) is in the business of producing cardboard boxes. Recently the company organized a contest for kids for the best design of a cardboard box and selectedMwinners. There areNprizes for the winners, each one carefully packed in a cardboard box (made by the ICPC, of course). The awarding process will be as follows:
* All the boxes with prizes will be stored in a separate room.
* The winners will enter the room, one at a time.
* Each winner selects one of the boxes.
* The selected box is opened by a representative of the organizing committee.
* If the box contains a prize, the winner takes it.
* If the box is empty (because the same box has already been selected by one or more previous winners), the winner will instead get a certificate printed on a sheet of excellent cardboard (made by ICPC, of course).
* Whether there is a prize or not, the box is re-sealed and returned to the room.
The management of the company would like to know how many prizes will be given by the above process. It is assumed that each winner picks a box at random and that all boxes are equally likely to be picked. Compute the mathematical expectation of the number of prizes given (the certificates are not counted as prizes, of course).
InputThe first and only line of the input file contains the values ofNandM().
OutputThe first and only line of the output file should contain a single real number: the expected number of prizes given out. The answer is accepted as correct if either the absolute or the relative error is less than or equal to 10-9.
Example(s)
|
|
|
|
|
|
|
|
原文链接: https://www.cnblogs.com/JSZX11556/p/4719303.html
欢迎关注
微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍
原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/220429
非原创文章文中已经注明原地址,如有侵权,联系删除
关注公众号【高性能架构探索】,第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处!