出题人题解 | #Balls#

原题解链接：https://ac.nowcoder.com/discuss/150246

令$f[i][j]f[i][j]$表示次取球后盒子里有$jj$个白球的概率,则$f[0][1]=1f[0][1]\; =\; 1$。

对于每次取球,$jj$个白球只能由$jj$或$j-1j\; -\; 1$个白球得到。所以有

$f[i][j]=\frac{i+1-j}{i+1}f[i-1][j]+\frac{j-1}{i+1}f[i-1][j-1]f[i][j]=\backslash frac\{i+1-j\}\{i+1\}\; f[i-1][j]+\backslash frac\{j-1\}\{i+1\}\; f[i-1][j-1]$

但是这是 $O\left(n^2\right)O\backslash left(n^\{2\}\backslash right)$ 的。

打表后发现白球有多少个的概率都是一样的， 且等于$\frac{1}{n+1}\backslash frac\{1\}\{n+1\}$(可证,脑补一下吧)。所以就可以 $O(1)O(1)$得到答案了。

$UnexpectedSolutionUnexpected\; Solution$

实际上，黑白球没有区别,所以它们的期望次数都等于盒子里的$11$个加上$\frac{n}{2}\backslash frac\{n\}\{2\}$。

#include <cstdio>
#include <assert.h>
#include <algorithm>
typedef long long LL;
const int N=1e3+5;

double f[N][N];

int main()
{
//	freopen("ball.in","r",stdin);
//	freopen("ball.out","w",stdout);

	int n; scanf("%d",&n);
	assert(n<=1000000);
//	f[0][1]=1;
//	for(int i=1; i<=n; ++i)
//		for(int j=0; j<=i+1; ++j)
//			if(j) f[i][j]=1.0*(i+1-j)/(i+1)*f[i-1][j]+1.0*(j-1)/(i+1)*f[i-1][j-1];
//			else f[i][j]=1.0*(i+1-j)/(i+1)*f[i-1][j];
//	double ans=0;
//	for(int i=1; i<=n+1; ++i) ans+=f[n][i]*i;//, printf("%d:%.4lf\n",i,f[n][i]);
//	printf("%.7lf\n",ans);
	printf("%.7lf\n",1.0*(n+2)/2);

	return 0;
}