湫湫系列故事——植樹節 Time Limit: 1000/500 MS (Java/Others) Memory Limit: 65535/32768 K (Java/Others) Total Submission(s): 1025 Accepted Submission(s): 604 Problem Description 今天是一年一度的植樹節，騰訊幼兒園要求每個老師在班裡選出幾個小朋友一起去野外種植小樹苗，根據學校的整體安排，湫湫老師的班裡要選出3個小朋友。 已知湫湫的班裡共有n個孩子，每個孩子有Bi個朋友(i從1到n)，且朋友關系是相互的，如果a小朋友和b小朋友是朋友，那麼b小朋友和a小朋友也一定是好朋友。為了選擇的公平性，湫湫老師會隨機抽取3個小朋友出來(每個人被抽到的概率相同)，但是她很希望這3個小朋友之間的關系完全相同，湫湫老師想請你幫她算算抽到的3個小朋友正好關系相同的概率是多少？ PS. 關系相同就是指要麼3個人互相是好朋友，要麼3個人互相都不是好朋友。 Input 輸入數據第一行是一個整數T(1<=T<=1000)，表示輸入數據的組數；每組數據的第一行是一正整數n表示孩子的總數(2<n<=1000)，第二行有n個數Bi (i從1到n)，分別代表每個小朋友的朋友的個數。 Output 對於每組數據，請輸出抽到的3個小朋友關系相同的概率，結果保留3位小數。 Sample Input 1 5 3 3 3 3 4 Sample Output 0.400
分析：
求正面不容易求，那麼就求反面。
由題易知，若不滿足題中條件，則3個人中必有兩個人是朋友，而另外一個人和其中一個或零個是朋友。就相當於3個點之間只能有兩條或一條直線。
每個人都有可能抽到，那麼如果抽到第i個人，另外兩個人只能在自己朋友中（Bi）抽一個和不是自己朋友中（n-Bi-1）抽一個才能不滿足題中條件，有朋友也許會問："如果抽到第i個人，另外兩個在第i個人的不是朋友中抽，也可能不滿足題中條件，比如當另外兩個人是朋友，而這兩個人都不是第i個人的朋友"。確實，有這種可能，但是我所說的包含你說的這種可能了，因為假設另外兩個人是j和k，那麼把i換成j或k，不就把這種情況包含進去了麼。 現在，又出了個新的問題：是否有重復事件？ 是的，確實有重復了，如前文，若在j處選了i和k，然後在k處選了i和j。那麼這就重復了，因此算出的反面事件除以2就是正確的反面事件的個數。而總事件為C(n，3), 設咱們求出反面事件的個數為sum，那麼答案ans=1-sum/C(n，3)；
代碼如下：
1 #include <stdio.h>
2 #include <string.h>
3 #include <algorithm>
4 #include <iostream>
5 using namespace std;
6
7 main()
8 {
9 int t, n, a[1005], i, j;
10 double ans, sum;
11 cin>>t;
12 while(t--)
13 {
14 scanf("%d",&n);
15 ans=0.0;
16 for(i=1;i<=n;i++)
17 {scanf("%d",&a[i]);
18 ans+=a[i]*(n-1-a[i]);
19 }
20 ans/=2.0;
21 sum=(n-1)*(n-2)*n/6;
22 ans=ans/sum;
23 printf("%.3lf\n",1-ans);
24 }
25 }
