推出数学公式:
#include<stdio.h>
#include<string.h>
__int64 C(int m,int n)
{
__int64 tmp=;
if(m>(n-m))m=n-m;
for(int i=; i<=m; i++)
{
tmp*=(n--);
tmp/=i;
}
return tmp;
}
int main()
{
int n,s;
int i,j,k;
//printf("#%I64d\n",C(10,50));
while(scanf("%d%d",&n,&s)!=EOF)
{
double sum=,tsum;
if(s>n)
{
printf("100.00000\n");
continue;
}
if(s==)
printf("0.00000\n");
else
{
for(i=; i<=s; i++)
{
sum+=(double)C(i,n)*((__int64)<<(n-i));
if(i==s-) tsum=sum;
}
printf("%.5lf\n",100.0*tsum/sum);
}
}
return ;
}
反面推出数学公式(超__int64):
#include<stdio.h>
#include<math.h> __int64 C(int m,int n)
{
__int64 tmp=;
if(m>(n-m))m=n-m;
for(int i=;i<=m;i++)
{
tmp*=(n--);
tmp/=i;
}
return tmp;
}
__int64 Sum(int n,int s)
{
__int64 tmp=,ret=;
for(int i=;i<n-s;i++)
{
tmp+=(C(i,n)*ret);
ret*=;
}
return tmp;
}
int main()
{
int n,s;
//printf("%d",C(25,50));
while(scanf("%d%d",&n,&s)!=EOF)
{
if(n<s)
{
printf("100.00000\n");
continue;
}
if(s==)printf("0.00000\n");
else
{
//printf("%lf\n",pow(3,n));
printf("%.5lf\n",-100.0*C(s,n)*pow(,n-s)/(pow(,n)-Sum(n,s)));
}
}
return ;
}
Dp解法:
转载:
//f(a,b)=2*f(a-1,b)+f(a-1,b-1)是公式
#include<stdio.h>
double p[][],o[][],k[][];
int main()
{
int a,b,c,d;
p[][]=;p[][]=;
for(a=;a<=;a++)
{
o[a][]=;
o[][a]=;
}
for(a=;a<=;a++)
{
p[a][]=*p[a-][];
p[][a]=;
}
for(a=;a<=;a++)
for(b=;b<=;b++)
{
p[a][b]=*p[a-][b]+p[a-][b-];
}
for(a=;a<=;a++)
for(b=;b<=;b++)
{
if(b>=a)
o[a][b]=*p[a-][b-]-;
else
o[a][b]=*o[a-][b]+o[a-][b-];
}
for(a=;a<=;a++)
for(b=;b<=;b++)
{
k[a][b]=o[a][b]/p[a][b]*;
}
while(scanf("%d%d",&a,&b)!=EOF)
{
if(b>a)
printf("100.00000\n");
else
printf("%.5lf\n",k[a][b]);
}
return ;
}
#include<stdio.h>
#include<string.h>
#define MM 1000000000000000.0
double dp[][];
int main()
{
int n,s,i,j;
while(scanf("%d%d",&n,&s)!=EOF)
{
memset(dp,,sizeof(dp));
if(s==)
{
printf("0.00000\n");
continue;
}
dp[][s] = ;
dp[][s-] = ;
for(i = ; i <= n ; i++)
for(j = ; j <= s ; j++)
{
dp[i][j] = dp[i-][j]*+dp[i-][j+];
}
double ss=;
for(i = ; i <= s ; i++)
{
ss+=dp[n][i]/MM;
}
dp[n][] = dp[n][]/MM;
double x = -1.0*dp[n][]/ss;
printf("%.5lf\n",x*);
}
return ;
}