【HDU5570 BestCoder Round 63 (div1)C】【期望DP 公式化简】balls n种求m种颜色，同颜色球数为x贡献为x方求期望

本文主要是介绍【HDU5570 BestCoder Round 63 (div1)C】【期望DP 公式化简】balls n种求m种颜色，同颜色球数为x贡献为x方求期望，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

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}}$ 。
对于第 $i$ 种颜色，若有 $x$ 个球，对答案的贡献为 $x^{2}$ 。
问答案的期望。

输入描述

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

输出描述

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

输入样例

输出样例

3.00
2.96
3.20

#include<stdio.h>
#include<string.h>
#include<ctype.h>
#include<math.h>
#include<iostream>
#include<string>
#include<set>
#include<map>
#include<vector>
#include<queue>
#include<bitset>
#include<algorithm>
#include<time.h>
using namespace std;
void fre(){freopen("c://test//input.in","r",stdin);freopen("c://test//output.out","w",stdout);}
#define MS(x,y) memset(x,y,sizeof(x))
#define MC(x,y) memcpy(x,y,sizeof(x))
#define MP(x,y) make_pair(x,y)
#define ls o<<1
#define rs o<<1|1
typedef long long LL;
typedef unsigned long long UL;
typedef unsigned int UI;
template <class T1,class T2>inline void gmax(T1 &a,T2 b){if(b>a)a=b;}
template <class T1,class T2>inline void gmin(T1 &a,T2 b){if(b<a)a=b;}
const int N=1005,M=0,Z=1e9+7,ms63=1061109567;
int casenum,casei;
double a[N][N];
int n,m;
int main()
{while(~scanf("%d%d",&n,&m)){for(int i=1;i<=n;++i){double sum=0;for(int j=1;j<=m;++j){scanf("%lf",&a[i][j]);sum+=a[i][j];}for(int j=1;j<=m;++j)a[i][j]/=sum;}double ans=0;for(int j=1;j<=m;++j){double sum=0;for(int i=1;i<=n;++i){sum+=a[i][j];ans+=a[i][j];ans-=a[i][j]*a[i][j];}ans+=sum*sum;}printf("%.2f\n",ans);}return 0;
}
/*
【题意】
有n（1000）个球，m（1000）种颜色。
给你一个n*m的矩阵，a[i][j]表示第i个球是颜色j的概率。
（a[i][j]其实并不是概率，其以整数给出，a[i][j]/(a[i][1]+a[i][2]+...+a[i][m])才是真正的"第i个球是颜色j"的概率）
然后，对于每一种颜色，如果该种颜色的数量为x个，那么对答案的贡献是x^2。让你输出——答案的期望是多少。【类型】
期望DP 公式化简【分析】
这道题比赛的时候完全不会做。
因为题目所要求的AC时间复杂度要低于O(nm)。即等阶于读入时间。我不会>_<问了叉老师之后才明白。叉姐说，这种题呀，只能按套路走！具体如下——用A[i][j]表示第i个球为颜色j的概率
用c[j]表示颜色为j的球的个数
用E[x]表示式子x的期望，显然有E[X[i][j]]=A[i][j]*1+(1-A[i][j])*0=A[i][j]
用P[x]表示事件x发生的概率
题目所要求的是E[c[1]^2 +c[2]^2 +c[3]^2+...+c[m]^2]
按照期望的线性相加特性，题目所求的就是∑(j=1~m)E[c[j]^2]=E[c[1]^2]+E[c[2]^2]+...+E[c[m]^2];一上来就研究概率，思路很难入手，难度会大一点。
于是我们不妨对于一个单独的状态（就是每个小球的颜色都确定）做研究——
用X[i][j]表示第i个球是否为第j种颜色，如果是，X[i][j]为1；否则，X[i][j]为0。
那么，c[j]=X[1][j]+X[2][j]+...+X[n][j].
回到∑(j=1~m)E[c[j]^2]，它便可以写成——
=∑(j=1~m)E[(X[1][j]+X[2][j]+...+X[n][j])^2]
对于元素个数的平方，如何考虑其叠加性质，从贡献上，通过加法来简化问题？
元素个数的平方，等于元素的pair数（pair自然也包括[自身，自身]这一个）。
于是，上式又可以化为——
=∑(for j=1~m--for p=1~n--for q=1~n)E[ X[p][j]*X[q][j] ]我们上面研究的某一个状态下的答案。然而我们还需要把其转化为概率来思考。
然而，在尝试化简的时候，我们注意点：E[X[p][j] * X[q][j]](p!=q)和 E[X[p][j]* X[p][j]] 是不一样的
因为对于E[X[p][j] * X[q][j]]来说，并结合上面确定的E[X[i][j]]=A[i][j]——
如果p!=q,那么这两个随机变量互相独立=E[X[p][j]] * E[X[q][j]] =A[p][j]*A[q][j]
如果p==q,那么E[ X[p][j]*X[p][j] ]=E[X[p][j]]=A[p][j]于是，对于这道题的答案，式子先变成了——
∑(for j=1~m)
{∑(for p=1~n){∑(for q=1~n&&q!=p){A[p][j]*A[q][j]}+A[p][j]}
}再化简一下，最后的式子就是——
∑(for j=1~m)
{( ∑(for i=1~n)A[i][j] )^2-∑(for i=1~n)A[i][j]^2 //这个是( ∑(for i=1~n)A[i][j] )^2中多算的量，减掉。+∑(for i=1~n)A[i][j] //这个是真正应该算入的量，加上去。
}
我们发现，这个复杂度确实只有O(nm)，这道题就做完啦~~再次感谢叉老师ORZ！【时间复杂度&&优化】
O(nm)*/

这篇关于【HDU5570 BestCoder Round 63 (div1)C】【期望DP 公式化简】balls n种求m种颜色，同颜色球数为x贡献为x方求期望的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！