hdu 5419(数学期望)
标签: hdu 5419(数学期望) 博客 51CTO博客
2023-05-29 18:24:14 45浏览
hdu 5419(数学期望),题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=5419题解:首先分母是C(m,3),考虑如何求出分子考虑数学期望的独立性,我们首先可以用线性的时间处理每个点被多少区间覆盖,如果第i个点被si个区间覆盖,则该点对结果的贡献度为wi*C(si,3),#include
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=5419
题解:
首先分母是C(m,3),考虑如何求出分子
考虑数学期望的独立性,我们首先可以用线性的时间处理每个点被多少区间覆盖,如果第i个点被si个区间覆盖,则该点对结果的贡献度为wi*C(si,3),注意这里si必须要大于等于3才能够对结果有贡献。
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
typedef long long LL;
const int maxn = 50005;
int n,m,w[maxn];
int bound[maxn];
LL gcd(LL a,LL b)
{
if(b) return gcd(b,a % b);
return a;
}
LL C(LL a)
{
return a * (a - 1) * (a - 2) / 6;
}
int main()
{
int t,l,r;
scanf("%d",&t);
while(t--)
{
memset(bound,0,sizeof(bound));
scanf("%d%d",&n,&m);
for(int i = 1; i <= n; i++)
scanf("%d",&w[i]);
for(int i = 1; i <= m; i++)
{
scanf("%d%d",&l,&r);
bound[l]++; bound[r+1]--;
}
int cnt = 0;
LL ans1 = 0;
for(int i = 1; i <= n; i++)
{
cnt += bound[i];
if(cnt >= 3)
ans1 += w[i] * C(cnt);
}
LL ans2 = C(m);
LL d = gcd(ans1,ans2);
if(d > 0)
{
ans1 /= d; ans2 /= d;
if(ans2 == 1) printf("%lld\n",ans1);
else printf("%lld/%lld\n",ans1,ans2);
}
else printf("0\n");
}
return 0;
}
好博客就要一起分享哦!分享海报
此处可发布评论
评论(0)展开评论
暂无评论,快来写一下吧
展开评论
您可能感兴趣的博客