2013长春网赛1004 hdu 4762 Cut the Cake

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=4762

题意:有个蛋糕,切成m块,将n个草莓放在上面,问所有的草莓放在同一块蛋糕上面的概率是多少。2 < M, N <= 20

分析:概率题,公式题。可惜我数学太差,想了好久都想不出来,看了题解还是不太明白怎么算的。

最后的概率公式为:n / (m^(n-1)),然后用高精度就可以了,最后的结果要约分,可以在计算的过程中求gcd(n,m),然后分子分母同除以该数就可以了。

这里有两个方法可以推出来。

方法1:以落在最左边的一颗来考虑,其余落在其右边的概率为1/m^(n-1),考虑每一个都可能在最左,实际上就是乘以c(1,n)

这样就可以推出公式为:n / (m^(n-1))

感觉这个方法不太严谨。。。。

方法2:(用积分求的)

枚举两个点位于两边,就是A(n,2)=n*(n-1),然后两个点形成的角度范围在0~1/m之间,

剩下的n-2个点放的概率就是x^(n-2),所以积分0~1/m,x^(n-2)对x进行积分。

积分结果乘上n*(n-1)就行了

用的是c++大数模板

AC代码:

 #include<stdio.h>
#include<string.h>
struct BigNum{
int num[];
int len;
};
int gcd(int a,int b)
{
if(b==)
return a;
return gcd(b,a%b);
}
BigNum mul(BigNum &a,int b)
{
BigNum c;
int i,len;
len=a.len;
memset(c.num,,sizeof(c.num));
if(b==)
{
c.len=;
return c;
}
for(i=;i<len;i++)
{
c.num[i]+=(a.num[i]*b);
if(c.num[i]>=)
{
c.num[i+]=c.num[i]/;
c.num[i]%=;
}
}
while(c.num[len]>)
{
c.num[len+]=c.num[len]/;
c.num[len++]%=;
}
c.len=len;
return c;
}
int main()
{
int t,m,n,i,a,b,c;
BigNum s;
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&m,&n);
s.num[]=;
s.len=;
a=n;
for(i=;i<n;i++)
{
b=m;
c=gcd(a,m);
a/=c;
b/=c;
s=mul(s,b);
}
printf("%d\/",a);
for(i=s.len-;i>=;i--)
printf("%d",s.num[i]);
printf("\n");
}
return ;
}
上一篇:题解-hdu2866 Special Prime


下一篇:Qt5_简易画板_详细注释