CF453A Little Pony and Expected Maximum 期望dp

容易设出状态f[i][j]表示前i次最大值为j的概率。

转移很显然不过复杂度很高。

考虑优化。考虑直接求出最大值为j的概率对于1显然\((\frac{1}{m})^n\)

对于2 显然有\((\frac{2}{m})^n\)不过这其中有一部分是1的概率容斥掉即可。

对于更大的点数也是如此记一个前缀和sum就好了。

(不过这个前缀和是不必要的刚好等于上一次求出的概率

需要小数快速幂就没了。

const ll MAXN=300010,G=3;

ll n,m;

db f[MAXN],sum[MAXN],ans;//f[i]表示n次之中点数最大为i的概率.

inline db ksm(db b,ll p)

{

	db cnt=1;

	while(p)

	{

		if(p&1)cnt=cnt*b;

		b=b*b;

		p=p>>1;

	}

	return cnt;

}

signed main()

{

	freopen("1.in","r",stdin);

	get(m);get(n);

	rep(1,m,i)

	{

		f[i]=ksm((db)i/m,n)-sum[i-1];

		sum[i]=sum[i-1]+f[i];

		ans=ans+f[i]*i;

	}

	printf("%.9lf",ans);

	return 0;

}

巴特西

CF453A Little Pony and Expected Maximum 期望dp

最新文章

热门文章