hdu 5570 balls（期望好题）

Problem Description

There are n balls with m colors. The possibility of that the color of the i-th ball is color j is ai,jai,1+ai,2+...+ai,m. If the number of balls with the j-th is x, then you should pay x2 as the cost. Please calculate the expectation of the cost.

Input

Several test cases(about 5)

For each cases, first come 2 integers, n,m(1≤n≤1000,1≤m≤1000)

Then follows n lines with m numbers ai,j(1≤ai≤100)

Output

For each cases, please output the answer with two decimal places.

Sample Input

Sample Output

3.00
2.96
3.20

Source

BestCoder Round #63 (div.2)

附上中文题目：

附上官方题解：

 1 #pragma comment(linker, "/STACK:1024000000,1024000000")
 2 #include<iostream>
 3 #include<cstdio>
 4 #include<cstring>
 5 #include<cmath>
 6 #include<math.h>
 7 #include<algorithm>
 8 #include<queue>
 9 #include<set>
10 #include<bitset>
11 #include<map>
12 #include<vector>
13 #include<stdlib.h>
14 #include <stack>
15 using namespace std;
16 #define PI acos(-1.0)
17 #define max(a,b) (a) > (b) ? (a) : (b)
18 #define min(a,b) (a) < (b) ? (a) : (b)
19 #define ll long long
20 #define eps 1e-10
21 #define MOD 1000000007
22 #define N 1006
23 #define inf 1e12
24 int n,m;
25 double a[N][N];
26 double p[N][N];
27 int main()
28 {
29    while(scanf("%d%d",&n,&m)==2){
30       for(int i=0;i<n;i++){
31          double sum=0;
32          for(int j=0;j<m;j++){
33             scanf("%lf",&a[i][j]);
34             sum+=a[i][j];
35          }
36          for(int j=0;j<m;j++){
37             p[i][j]=a[i][j]*1.0/sum;
38          }
39       }
40       double ans=0;
41       for(int j=0;j<m;j++){
42          double sum=0;
43          for(int i=0;i<n;i++){
44             ans+=p[i][j]*(1.0-p[i][j]);
45          }
46          for(int i=0;i<n;i++){
47             sum+=p[i][j];
48          }
49          ans+=sum*sum;
50       }
51       printf("%.2lf
",ans);
52    }
53     return 0;
54 }

View Code