「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;
}