「雅礼day7」结合Conjugate - 找规律

题目大意

在不存在的 noip day3 里，小w 见到了一堆堆的谜题。
比如这题为什么会叫共轭？
他并不知道答案。
有 n 堆谜题，每堆有 ai 个，小 w 每次从剩下的谜题中选择一个，然后把所在的那一堆谜题全部丢掉。
小 w 期望多少次后丢掉第一堆？

---

题目分析

题目略毒。
先写出期望的计算式：

$$E=\frac{a_1}{sum}\times 1+\sum_{j=2}^n\frac{a_j}{sum}\times \frac{a_1}{sum-a_1}\times 2+\sum_{j=2}^n\frac{a_j}{sum}\times \sum_{k=2,k\neq j}^n\frac{a_k}{sum-a_j}\times\frac{a_1}{sum-a_j-a_k}\times 3+\cdots$$

然后可以用$O(n^3)$的暴力或$O(n^2)$的动规解决（似乎？）。

有没有更快的方法？
我们举个$n=3$的栗子。

$$E=\frac{a_1}{sum}+2(\frac{a_2}{sum}\times \frac{a_1}{sum-a_2}+\frac{a_3}{sum}\times \frac{a_1}{sum-a_3})+3(\frac{a_3}{sum}\times\frac{a_2}{sum-a_3}\times\frac{a_1}{sum-a_2-a_3}+\frac{a_2}{sum}\times\frac{a_3}{sum-a_2}\times\frac{a_1}{sum-a_2-a_3})$$

我们将$sum$使用$a_1+a_2+a_3$代替得到：

$$E=\frac{a_1}{a_1+a_2+a_3}+2(\frac{a_2}{a_1+a_2+a_3}\times \frac{a_1}{a_1+a_3}+\frac{a_3}{a_1+a_2+a_3}\times \frac{a_1}{a_1+a_2})+3(\frac{a_3}{a_1+a_2+a_3}\times \frac{a_2}{a_1+a_2}\times 1+\frac{a_2}{a_1+a_2+a_3}\times \frac{a_3}{a_1+a_3}\times 1)$$

然后使用mathematica暴力化简得到：

观察一下，发现第二个式子非常优美，可以通过$O(n)$得出答案，因此我们根据这个化简式大胆假设答案：

$$n-\frac{a_1}{a_1+a_2}-\frac{a_1}{a_1+a_3}-\cdots-\frac{a_1}{a_1+a_n}$$

验证一下发现好像是对的。

---

代码

#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;
inline const int Get_Int() {
	int num=0,bj=1;
	char x=getchar();
	while(x<'0'||x>'9') {
		if(x=='-')bj=-1;
		x=getchar();
	}
	while(x>='0'&&x<='9') {
		num=num*10+x-'0';
		x=getchar();
	}
	return num;
}
int n;
double a1;
int main() {
	n=Get_Int();
	a1=Get_Int();
	double ans=n;
	for(int i=2; i<=n; i++) {
		double x=Get_Int();
		ans=(ans-a1/(a1+x));
	}
	printf("%0.8lf\n",ans);
	return 0;
}