HDOJ 5645 DZY Loves Balls(確率)

DZY Loves Balls
Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 262144/262144 K (Java/Others) Total Submission(s): 621    Accepted Submission(s): 367
Problem Description
DZY loves playing balls.
He has 
n  balls in a big box. On each ball there is an integer written.
One day he decides to pick two balls from the box. First he randomly picks a ball from the box, and names it 
A . Next, without putting 
A  back into the box, he randomly picks another ball from the box, and names it 
B .
If the number written on 
A  is strictly greater than the number on 
B , he will feel happy.
Now you are given the numbers on each ball. Please calculate the probability that he feels happy.
 
Input
First line contains 
t  denoting the number of testcases.
t  testcases follow. In each testcase, first line contains 
n , second line contains 
n  space-separated positive integers 
ai , denoting the numbers on the balls.
(
1≤t≤300,2≤n≤300,1≤ai≤300 )
 
Output
For each testcase, output a real number with 6 decimal places. 
 
Sample Input

   
   
   
   

    
    
    
    2
3
1 2 3
3
100 100 100
   
   
   
   

 
Sample Output

   
   
   
   

    
    
    
    0.500000
0.000000
   
   
   
   
   
   
   
   


   
   
   
   
   
   
   
   

    
    
    
      ：n  ，     A，       B， P(A>B)
   
   
   
   
   
   
   
   


   
   
   
   
   
   
   
   

    
    
    
      ：        ，       
   
   
   
   
   
   
   
   


   
   
   
   
   
   
   
   

    
    
    
    ac  ：
   
   
   
   
   
   
   
   

    
    
    
    
#include<stdio.h>
#include<math.h>
#include<string.h>
#include<stack>
#include<set>
#include<queue>
#include<vector>
#include<iostream>
#include<algorithm>
#define MAXN 1010000
#define LL long long
#define ll __int64
#define INF 0xfffffff
#define mem(x) memset(x,0,sizeof(x))
#define PI acos(-1)
#define eps 1e-8
using namespace std;
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll lcm(ll a,ll b){return a/gcd(a,b)*b;}
ll powmod(ll a,ll b,ll MOD){ll ans=1;while(b){if(b%2)ans=ans*a%MOD;a=a*a%MOD;b/=2;}return ans;}
double dpow(double a,ll b){double ans=1.0;while(b){if(b%2)ans=ans*a;a=a*a;b/=2;}return ans;}
//head 
int num[333];
int main()
{
	int t,i;
	scanf("%d",&t);
	while(t--)
	{
		int n;
		scanf("%d",&n);
		mem(num);
		for(i=0;i<n;i++)
		{
			int a;
			scanf("%d",&a);
			num[a]++;
		}
		int k=0;
		double ans=0.0;
		for(i=1;i<=300;i++)
		{
			if(num[i])
			{
				double p=(num[i]*1.0)/n;
				double q=(k*1.0)/((n-1)*1.0);
				//printf("i= %d p=%lf,q=%lf
",i,p,q);
				ans+=p*q;
				k+=num[i];
			}
		}
		printf("%.6lf
",ans);
	}
	return 0;
}