Luogu P3802 小魔女帕琪

link
 

题解

设 (n = sumlimits_{i=1}^{7} a_i) 。
(n) 这么大，貌似难以 (O(n)) 做。于是试图找规律。
设 (E(i) = E(i-1) + P(i)) 。 (P(i)) 表示第 (i) 位触发魔法的概率。问题在于如何求 (P(i)) 。
显然对于第 (7) 位， (P(7) = 7! imes prodlimits_{i=1}^{7} dfrac{a_i}{n-i+1}) 。
考虑对于第 (8) 位的所有情况。
第 (1) 位为魔法 (1) 时，概率为 (7! imes prodlimits_{i=1}^{7} dfrac{a_i}{n-i} imes dfrac{a_1-1}{n-7}) 。
第 (1) 位为魔法 (2) 时，概率为 (7! imes prodlimits_{i=1}^{7} dfrac{a_i}{n-i} imes dfrac{a_2-1}{n-7}) 。
按照此规律，可以发现 (P(8) = 7! imes prodlimits_{i=1}^{7} dfrac{a_i}{n-i} imes dfrac{sum_{i=1}^{7}(a_i-1)}{n-7} = 7! imes prodlimits_{i=1}^{7} dfrac{a_i}{n-i} = P(7)) 。
即 (forall x geq 7,P(x) = 7! imes prodlimits_{i=1}^{7} dfrac{a_i}{n-i+1}) 。
故 (E(n) = (n-6) imes 7! imes prodlimits_{i=1}^{7} dfrac{a_i}{n-i+1}) 。
这启示我们不会做时，不妨先大胆把式子推出来，从最初状态开始推，也许可以找到规律。

#include <cstdio>

double a[10];
int n;
double ans;

int main() {
	for (int i = 1; i <= 7; ++i) {
		scanf("%lf", &a[i]); 
		n += a[i];
	}
	if (n >= 7) {
		ans = n - 6;
		for (int i = 1; i <= 7; ++i)
			ans *= a[i] / (n - i + 1) * i;
	}
	printf("%.3lf", ans);
	return 0;
}