Project Euler 307

发表于 更新于 分类于 阅读次数： 本文字数： 956 阅读时长 ≈ 1 分钟

Project Euler 307

题目

Chip Defects

$k$ defects are randomly distributed amongst $n$ integrated-circuit chips produced by a factory (any number of defects may be found on a chip and each defect is independent of the other defects).

Let $p(k,n)$ represent the probability that there is a chip with at least $3$ defects.

For instance $p(3,7) \approx 0.0204081633$.

Find $p(20 000, 1 000 000)$ and give your answer rounded to $10$ decimal places in the form 0.abcdefghij.

解决方案

不难想到先考虑事件：全部零件最多只有$2$个缺陷。计算出这个事件的概率后，那么这个事件的补就是题目所求的至少一个零件有$3$个缺陷。

令$K=20000,N=100000$。

枚举$i$，有$i$个零件具有两个瑕疵，那么$K-2i$个零件具有一个瑕疵，$N-K+i$个零件是没有瑕疵的。那么不难算出，这种方式一共有$\dbinom{N}{i}\cdot \dbinom{N-i}{K-2i}=\dfrac{N!}{i!(K-2i)!(N-K+i)!}$种取法。

对于瑕疵而言，相当于将$K$个瑕疵放进$i$个容量为$2$的不同篮子，将$K-2i$个瑕疵放进$K-2i$个容量为$1$的不同篮子的情况数。假设容量为$2$的篮子都放在容量为$1$的篮子后面，那么根据全排列数公式，可以写出$\dfrac{K!}{(2!)^i\cdot(1!)^{K-2i}}$

最终可以得到：

注意到无论分子还是分母，数都比较大。因此考虑将它们转化成对数进行计算，在对数上计算完成后再通过幂运算转换成真正的结果。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
# include <bits/stdc++.h>
typedef long double ld;
using namespace std;
const int K=20000,N=1000000;
ld fac[N+K+2];
int main(){
    for(int i=1;i<=N+K;i++)
        fac[i]=fac[i-1]+log(i);
    ld ans=0;
    for(int i=0;i<=K/2&&i<=N;i++){
        if(K-2*i>N-i) continue;
        ld val=fac[N]+fac[K]-fac[i]-fac[K-2*i]-fac[N-K+i]-log(N)*K-log(2)*i;
        ans+=exp(val);
    }
    ans=(ld)1-ans;
    printf("%.10Lf\n",ans);
}