hdu 2049 不容易系列之(4)——考新郎 (错排公式,注意精度)

hdu 2049 题目链接
题意:n个妹子和n个汉子对应。。然后让每个汉子取选一个妹子,不能重复,问恰好有m个汉子选错妹子的可能的方案数。

思路:从n个中选n-m个,然后做剩余m个错排即可。

答案就是c[n][n-m]*d[m]  c[]为组合数公式,d为错排公式。
然而wa到死。。。

因为我用了double….有毒。。。

double表示整数也是会丢失精度的!!!

double表示整数也是会丢失精度的!!!

double表示整数也是会丢失精度的!!!

double表示整数也是会丢失精度的!!!

double表示整数也是会丢失精度的!!!

Screenshot from 2016-07-27 19-49-40

我自杀去了,世界再见(x

 

 

 

 

hdu 2048 神、上帝以及老天爷 (错排公式)

hdu2048 题目链接

题意:n个人不放回的从一个有n个每个人对应id的卡片的盒子取一张卡片,取的正好和自己的对应就算中奖。求所有人都没有中奖的概率。

思路:错排。。。

复习了一下错排公式。。。d[n] = (n-1)*(d[n-1]+d[n-2])  (d[1]=0,d[2]=1)

然后求概率的时候。。惊讶得发现概率稳定在了36.79%(1/e)附近。。。

这是因为。。。错排还有一个公式:D(n) = n! [(-1)^2/2! + … + (-1)^(n-1)/(n-1)! + (-1)^n/n!].

求概率每次把n!除掉了。。剩下的。。其实就是e的泰勒展开,当x=-1时的值。

因为当n越大时。。这个概率越接近1/e

这道题里。。。在保留百分数的小数点两位的精度的条件下。。当n为7的时候。。答案就已经是36.79保持不变了。。。