前两个小时一题没过，然后忽然几分钟过五题，太演了……

补题：C

题意

现有一个容积为一升的空杯，给定实数\(x\)，要求多次往杯中灌水，每次灌入的水的升数\(t\)是一个在\([0,x]\)内均匀随机选择的实数，当把杯子灌满（或者溢出）时过程终止。问期望灌几次水？

\(T(T\le 10^4)\)组数据，\(0.05\le x\le 10^9\)。

解析

首先先来个经典转化，假设\(P(n)\)表示灌了\(n\)次水还没满的概率，那么答案就是：

\[ \sum_{n\ge 0}P(n) \]

下面我们来考虑怎么求\(P(n)\)。这里先用一个几何的视角看待问题：我们建立\(n\)个座标轴，每个座标轴表示第\(i\)次灌的水\(x_i\)；然后不考虑是否灌满的情况下，样本空间就相当于一个各边长为\(x\)的超立方体；符合要求的样本点就是在样本空间内且满足各座标和不超过\(1\)的点；\(P(n)\)就是这二者的超体积比。

至于求符合要求的点的总体积，这是个很经典的容斥问题：首先不考虑各座标要\(\le x\)的限制，这样只需要求一个锥形的体积，是\(\frac{1^n}{n!}\)；然后假设有一个座标超出了\(x\)，就从\(1\)里面减掉，然后是\(\frac{(1-x)^n}{n!}\)，把这个从答案里减掉；然后再把两个座标超出\(x\)的加回来……总之我们推出其体积为：

\[ \sum_{ix\le 1}\binom n i(-1)^i\cdot\frac{(1-ix)^n}{n!} \]

然后再除一下样本空间体积，得到：

\[ P(n)=\sum_{ix\le 1}\binom n i(-1)^i\cdot\frac{(\frac{1-ix}{x})^n}{n!} \]

最后我们把\(P(n)\)带回到答案的式子里：

\[ \begin{aligned} \sum_{n\ge 0}P(n)&=\sum_{n\ge 0}\sum_{ix\le 1}(-1)^i\cdot\frac{(\frac{1-ix}{x})^n}{i!(n-i)!}\\ &=\sum_{ix\le 1}\frac{(-1)^i}{i!}\sum_{n\ge i}\frac{(\frac{1-ix}{x})^n}{(n-i)!}\\ &=\sum_{ix\le 1}\frac{(-1)^i}{i!}(\frac{1-ix}{x})^i\sum_{n\ge i}\frac{(\frac{1-ix}{x})^{n-i}}{(n-i)!}\\ &=\sum_{ix\le 1}\frac{(-1)^i}{i!}(\frac{1-ix}{x})^i\sum_{n\ge 0}\frac{(\frac{1-ix}{x})^{n}}{n!}\\ &=\sum_{ix\le 1}\frac{(-1)^i}{i!}(\frac{1-ix}{x})^i e^{\frac{1-ix}{x}} \end{aligned} \]

注意到\(x\ge 0.05\)，因此需要枚举的\(i\)很少。

代码

#include <bits/stdc++.h>
typedef double real;
const real eps = 1e-6;

int main() {
  int T; scanf("%d", &T);
  while(T --) {
    double x; scanf("%lf", &x);
    double ans = 0, ifac = 1;
    for(int i = 0; x * i - 1 < eps; i ++) {
      double hi = (1.00 - x * i) / x;
      if(i > 0) ifac /= i;
      double th = ifac * exp(hi);
      if(i & 1) th *= -1;
      int j = i;
      while(j --) th *= hi;
      ans += th;
    }
    printf("%.10lf\n", ans);
  }
  return 0;
}