Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

DP过了 生成函数为什么过不了呢,求数据。。。程序见内

Posted by CydorniaKnight at 2009-09-25 11:28:15 on Problem 1322
#include<iostream>
#include<cmath>
using namespace std;

int c,n,m,k;
double comb[101][101]={0};
double odd[300],even[300],ek[300];
double ans,tmp,kc,sum;

void setlist()
{
	int i,j;
	for(i=0;i<=100;++i)
		comb[i][0]=1;
	for(i=1;i<=100;++i)
		for(j=1;j<=i;++j)
			comb[i][j]=comb[i-1][j]+comb[i-1][j-1];
}

int main()
{
	int i,j,ind,c_m;
	setlist();
	while(scanf("%d",&c)&&c){
		scanf("%d%d",&n,&m);
		if(m<=c&&m<=n&&m%2==n%2){
			for(i=0;i<300;++i)
				ek[i]=odd[i]=even[i]=0;
			ans=comb[c][m]/pow(2.0,(double)c);
			for(i=0;i<=m;++i)
			{
				ind=m-i*2+150;
				if(i%2) odd[ind]=-comb[m][i];
				else odd[ind]=comb[m][i];
			}
			c_m=c-m;
			for(i=0;i<=c_m;++i)
			{
				ind=c_m-i*2+150;
				even[ind]=comb[c_m][i];
			}
			for(i=0;i<=m;++i)
			{
				for(j=0;j<=c_m;++j)
				{
					ek[c-(i+j)*2+150]+=odd[m-i*2+150]*even[c_m-j*2+150];
				}
			}
			sum=0;
			if(n%2) sum=ek[c+150]-ek[150-c];
			else sum=ek[c+150]+ek[150-c];
			if(n<=5000){
				for(k=1;k<c;++k)
				{
					kc=pow((double)k/(double)c,(double)n);
					if(n%2) tmp=ek[k+150]-ek[150-k];
					else tmp=ek[k+150]+ek[150-k];
					sum+=tmp*kc;
				}
			}
			ans*=sum;
			printf("%.3lf\n",ans);
		}else printf("0.000\n");
	}
	return 0;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator