CF248E Piglet's Birthday

题面

题意翻译

给定$n$个货架，初始时每个上面有$a[i]$个蜜罐。

有$q$次操作，每次操作形如$u,v,k$，表示从货架$u$上任意选择$k$个蜜罐试吃（吃过的也还能吃），吃完后把这$k$个蜜罐放到$v$货架上去。

每次操作完之后回答所有蜜罐都被试吃过的货架数量的期望

题解

直接引用$\text{yyb}$的

代码

#include<cstdio>

#include<cstring>

#include<cctype>

#include<cmath>

#include<algorithm>

#define RG register

#define file(x) freopen(#x".in", "r", stdin);freopen(#x".out", "w", stdout);

#define clear(x, y) memset(x, y, sizeof(x))

inline int read()

{

	int data = 0, w = 1; char ch = getchar();

	while(ch != '-' && (!isdigit(ch))) ch = getchar();

	if(ch == '-') w = -1, ch = getchar();

	while(isdigit(ch)) data = data * 10 + (ch ^ 48), ch = getchar();

	return data * w;

}

const int maxn(100010);

double f[maxn][110], ans;

int n, q, a[maxn], b[maxn], ln[maxn];

inline double C(int n, int m)

{

	if(n < m) return 0; double ans = 1;

	for(RG int i = 1; i <= m; i++) ans *= 1. * (n - i + 1) / i;

	return ans;

}

int main()

{

	n = read();

	for(RG int i = 1; i <= n; i++) a[i] = b[i] = read();

	for(RG int i = 1; i <= n; i++) f[i][a[i]] = 1;

	for(RG int i = 1; i <= n; i++) ans += f[i][0];

	q = read();

	for(RG int i = 1; i <= q; i++)

	{

		int x = read(), y = read(), K = read(); ans -= f[x][0];

		for(RG int j = 0; j <= a[x]; j++)

		{

			double F = 0, c = C(b[x], K);

			for(RG int k = 0; k <= K; ++k)

				F += f[x][j + k] * C(j + k, k) * C(b[x] - j - k, K - k) / c;

			f[x][j] = F;

		}

		b[x] -= K, b[y] += K, ans += f[x][0];

		printf("%.10lf\n", ans);

	}

	return 0;

}