「AGC 032F」One Third 题解

题目

分析

考虑转化,可以转化为在 $\left[0,\frac{1}{3}\right]$ 上等概率随机分成 $n$ 份,并从 $1,2,3$ 中等概率随机赋上一种颜色,$0$ 初始颜色已为 $1$,$\frac{1}{3}$ 初始颜色已为 $2$,求最短的两端点颜色不同的线段的期望长度

先从没有限制的长度为 $1$ 的线段开始考虑,不妨设其互补累积分布函数 $F_{L_1}(x)=P(L>x)=(1-nx)^{n-1}$ 可得其期望:

$$\begin{aligned}\operatorname{E}[L_1] & =\int_0^\frac{1}{n}x\times\left[-(F_{L_1}(x))^\prime\right]dx\\
& =\int_0^\frac{1}{n}F_{L_1}(x)dx \text{ (分部积分) } \\
& =\int_0^\frac{1}{n}(1-nx)^{n-1}dx \\
& =\frac{1}{n}\int_0^1\left(\frac{n-nx}{n}\right)^{n-1}dx \\
& =\frac{1}{n}\int_0^1\left(1-x\right)^{n-1}dx \\
& =\frac{1}{n}\int_0^1x^{n-1}dx \text{ (换元) } \\
& =\frac{1}{n^2}\end{aligned}$$

考虑次小值,削除 $n$ 段最小值后的最小值再加上最小值:$\operatorname{E}[L_2]=\frac{1-n\operatorname{E}[L_1]}{(n-1)^2}+\operatorname{E}[L_1]$
变形得 $\operatorname{E}[L_2]-\operatorname{E}[L_1]=\frac{1}{n(n-1)}$,归纳得 $\operatorname{E}[L_{k+1}]-\operatorname{E}[L_k]=\frac{1}{n(n-k)}$
考虑乘上至少前 $i$ 条线段都不满足条件的概率 $\frac{1}{3^i}$ 答案即为 $\frac{1}{n}\sum\limits_{i=1}^n\frac{1}{3^i(n-i+1)}$

代码

constexpr int N = 1000005;
constexpr int Mod = 1000000007;

int pow(int a, int b, int m);

int inv[N];
int n;

int main() {
  read(n);
  inv[1] = 1;
  for (int i = 2; i <= n; ++i) {
    inv[i] = (Mod - Mod / i) * 1ll * inv[Mod % i] % Mod;
  }
  int ans = 0;
  int iv3 = pow(3, Mod - 2, Mod);
  for (int i = 1, p3 = inv[n]; i <= n; ++i) {
    p3 = p3 * 1ll * iv3 % Mod;
    ans = (ans + p3 * 1ll * inv[n - i + 1] % Mod) % Mod;
  }
  write(ans), EL;
  return 0;
}

int pow(int a, int b, int m) {
  int ans = 1, now = a;
  while (b) {
    if (b & 1) {
      ans = ans * 1ll * now % m;
    }
    now = now * 1ll * now % m;
    b >>= 1;
  }
  return ans;
}

本博客采用知识共享署名-相同方式共享 4.0 国际许可协议进行许可
本文链接:https://blog.seniorious.cc/2020/AGC-032F/