题目链接:http://poj.org/problem?id=1322
题意:
思路:
double C[N][N]; void init() { C[0][0]=1; int i,j; for(i=1;i<N;i++) { C[i][0]=C[i][i]=1; for(j=1;j<i;j++) C[i][j]=C[i-1][j-1]+C[i-1][j]; } } double Pow(double a,int b) { double ans=1; while(b) { if(b&1) ans*=a; a=a*a; b>>=1; } return ans; } int n,m,c; double cal() { double positive[N],negative[N],a[N],b[N]; double temp1,temp2; int i,j,k; for(i=0;i<=c;i++) positive[i]=negative[i]=a[i]=b[i]=0; temp1=Pow(0.5,m); for(i=0;i<=m;i++) { j=i-(m-i); if((m-i)&1) temp2=-temp1; else temp2=temp1; if(j>=0) a[j]+=temp2*C[m][i]; else b[-j]+=temp2*C[m][i]; } temp1=Pow(0.5,c-m); for(i=0;i<=c-m;i++) { temp2=temp1*C[c-m][i]; for(j=0;j<=m;j++) { k=j+i-(c-m-i); if(k>=0) positive[k]+=temp2*a[j]; else negative[-k]+=temp2*a[j]; } for(j=0;j<=m;j++) { k=-j+i-(c-m-i); if(k>=0) positive[k]+=temp2*b[j]; else negative[-k]+=temp2*b[j]; } } double ans=0; for(k=1;k<=c;k++) { if(n&1) negative[k]=-negative[k]; ans+=C[c][m]*Pow(1.0*k/c,n)*(positive[k]+negative[k]); } return ans; } int main() { init(); Rush(c) { if(!c) break; RD(n,m); if((n-m)%2||m>c||m>n) puts("0.000"); else if(n==0&&m==0) puts("1.000"); else PR(cal()); } }