P6944

P6944

正题

题目链接:

题目大意

有 n n n颗不同颜色的宝石，每次随机选择一颗复制，重复 d d d次，求最后宝石数前 r r r的颜色的宝石数之和的期望值。

1 ≤ r ≤ n , d ≤ 300 1leq rleq n,dleq 300 1≤r≤n,d≤300

解题思路

考虑一种最终状态 S S S的概率，设第 i i i种宝石个数为 a i + 1 a_i+1 ai​+1，那么我们考虑在若干次分裂中分裂到这几个的概率，这里先考虑分子作为权重（因为分母一样）。
首先分裂天数分配到每一种宝石的方案就是可重排列的公式： d ! ∏ i = 1 n a i ! frac{d!}{prod_{i=1}^na_i!} ∏i=1n​ai​!d!​
然后对于第 i i i次分裂一种宝石时，有 i i i的概率，所以这一部分的方案就是 ∏ i = 1 n a i ! prod_{i=1}^na_i! ∏i=1n​ai​!
那么总共的权重
d ! ∏ i = 1 n a i ! × ∏ i = 1 n a i ! = d ! frac{d!}{prod_{i=1}^na_i!}times prod_{i=1}^na_i!=d! ∏i=1n​ai​!d!​×i=1∏n​ai​!=d!

所以所有方案的概率都是相等的。

之后考虑怎么求所有方案的，我们可以考虑 d p dp dp。

d p dp dp求前 r r r大的和话我们有个很常见的技巧，就是我们可以每次让一个前缀 + 1 +1 +1，然后不断缩短前缀，这样我们还可以在缩短前缀的过程中顺便统计重排的方案。

设 f i , j f_{i,j} fi,j​表示目前分裂了 i i i次，前缀长度为 j j j时的方案数， g g g则表示所有方案的答案，然后转移即可。

时间复杂度： O ( n 3 ) O(n^3) O(n3)

code

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=510;
int n,d,r;
double C[N][N],f[N][N],g[N][N];
int main()
{scanf("%d%d%d",&n,&d,&r);C[0][0]=f[0][n]=1;for(int i=1;i<=n;i++)for(int j=0;j<=i;j++)C[i][j]=C[i-1][j]+(j?C[i-1][j-1]:0);for(int i=0;i<d;i++)for(int j=1;j<=n;j++)for(int k=1;k<=j;k++){if(i+k>d)break;f[i+k][k]+=f[i][j]*C[j][k];g[i+k][k]+=(g[i][j]+min(r,k)*f[i][j])*C[j][k];}double F=0,G=0;for(int i=1;i<=n;i++)F+=f[d][i],G+=g[d][i];printf("%.12lfn",G/F+r);return 0;
}