3236958_ac_47ms_304k.cc

北大大牛代码 1240道题的原代码 超级权威

#include <stdio.h>
#include <string.h>

double c[21][21];
double p;
double cc[21];

double power(double q,int n)
{
	if(n==0)
		return 1.00;
	if(n%2==0)
		return power(q*q,n/2);
	else
		return q*power(q,n-1);
}

double calc(int n)
{
	int i;

	if(cc[n]!=0)
		return cc[n];
	double t = 0;
	for(i = 0; i < n-1; i++)
	{
		t += c[n-1][i]*calc(i+1)*power(1-p,(i+1)*(n-i-1));
	}
	return cc[n]=1-t;
}

int n;

void init()
{
	int i, j;

	for(i = 0; i <= n; i++)
	{
		c[i][0] = 1;
	}
	for(i = 1; i <= n; i++)
	{
		for(j = 1; j < n; j++)
		{
			c[i][j] = c[i-1][j]+c[i-1][j-1];
		}
		c[i][j] = 1;
	}
}

int main()
{
	scanf("%d%lf",&n,&p);
	init();
	memset(cc,0,sizeof(cc));
	cc[1] = 1;cc[2] = p;
	printf("%lf\n",calc(n));
	return 0;
}