HDU 5570：balls 期望。。。。。。。。。。。。。。。

balls

 

 Accepts: 19

 

 Submissions: 55

 Time Limit: 6000/3000 MS (Java/Others)

 

 Memory Limit: 65536/65536 K (Java/Others)

问题描述

有$n$个球，共有$m$种颜色，第$i$个球的颜色为$j$的概率为frac{a_{i,j}}{a_{i,1}+a_{i,2}+...+a_{i,m}}​a​i,1​​+a​i,2​​+...+a​i,m​​​​a​i,j​​​​。
对于第$i$种颜色，若有$x$个球，对答案的贡献为x^{2}x​2​​。
问答案的期望。

输入描述

若干组数据(大概$5$组)。
每组数据第一行两个整数$n(1\le n\le 1000),m(1\le m\le 1000)$。
接下来$n$行每行$m$个数表示a_i,j(1 leq a_i,j leq 100)a​i​​,j(1≤a​i​​,j≤100)

输出描述

对于每组数组，输出一行表示答案，保留两位小数。

输入样例

2 2
1 1
3 5
2 2
4 5
4 2
2 2
2 4
1 4

输出样例

3.00
2.96
3.20

val[i][j]表示第i个球颜色为j的概率。那么第i个球颜色为j的期望E[x[i][j]]=val[i][j]*1+(1-val[i][j])*0=val[i][j]

c[i]表示颜色为i的球的个数。题目要求的是 sum(E[c[i]^2]) i的值从1到m。

从最简单的来看 如果要求的是E[c[i]]，那么它等于E[(x[1][i]+x[2][i]...+x[n][i])]

现在要求的是E[c[i]^2]=E[(x[1][i]+x[2][i]...+x[n][i])^2]。

里面展开的话就是任意两个相乘,拿出其中一项来看 E[x[k1][i]*x[k2][i]] 

若k1==k2，那这个等式等于=val[k1][i]

若k1!=k2，那这个等式等于=val[k1][i]*val[k2][i]

求和即是结果了。

代码：

#pragma warning(disable:4996)  
#include <iostream>  
#include <algorithm>  
#include <cmath>  
#include <vector>  
#include <string>  
#include <cstring> 
#include <queue>
using namespace std;

const int maxn = 1005;

int n, m;
double val[maxn][maxn];

int main()
{
    //freopen("i.txt", "r", stdin);
    //freopen("o.txt", "w", stdout);
    

    while (scanf("%d%d", &n, &m) != EOF)
    {
        for (int i = 1; i <= n; i++)
        {
            double sum = 0;
            for (int j = 1; j <= m; j++)
            {
                scanf("%lf", &val[i][j]);
                sum += val[i][j];
            }
            for (int j = 1; j <= m; j++)
            {
                val[i][j] = val[i][j] / sum;
            }
        }
        double ans = 0;
        for (int i = 1; i <= m; i++)
        {
            double sum = 0;
            for (int j = 1; j <= n; j++)
            {
                sum += val[j][i];
                ans += val[j][i];
                ans -= val[j][i] * val[j][i];
            }
            ans += (sum*sum);
        }
        printf("%.2lf
", ans);
    }
    //system("pause");
    return 0;
}