题解 AT4521 【[AGC032F] One Third】

· · 题解

Lemma

在[0,1)上随机取n-1个点，把线段分成了n段中所有段长度的最小值的期望是\frac{1}{n^2}

证明：设最短的一段长度为x，那么剩下的n-1段的长度都要大于等于x，考虑先将每条线段的长度减去x，于是就变成了在剩下的长度为1-nx的线段上随机取n-1个点，那么就有

P(L_{min}\geq x)=(1-nx)^{n-1}

于是

\begin{aligned} E(L_{min})&=\int_0^{\frac{1}{n}}P(L_{min}\geq x)dx\\ &=\int_0^{\frac{1}{n}}(1-nx)^{n-1}dx\\ &=-\frac{1}{n}\int_0^{\frac{1}{n}}(1-nx)^{n-1}d(1-nx)\\ &=-\frac{1}{n^2}(1-nx)^n\Big\lvert_0^{\frac{1}{n}}\\ &=\frac{1}{n^2} \end{aligned}

如果考虑次长段的期望，那么就是剩下的1-nx中最短的一段的期望，即

\frac{1-nE(L_{min})}{(n-1)^2}+E(L_{min})=\frac{1}{n}(\frac{1}{n}+\frac{1}{n-1})

于是可以归纳得出第k短的长度的期望为

E(L_k)=\frac{1}{n}(\frac{1}{n}+\frac{1}{n-1}+\cdots +\frac{1}{n-k+1})

Solution

首先可以转化一下题意，令其中某一条边为起点，顺时针每\frac{2}{3}\pi划分为一个区域，将三个区域中的线段分别染成红绿蓝三种颜色，然后把所有线段的夹角\mod \frac{2}{3}\pi之后都放到一个区间内，于是问题就变成了

在[0,\frac{2}{3}\pi)中随机取n-1个点，然后将每个点随机染成红绿蓝三种颜色中的一种，求两端颜色不同的线段长度的最小值的期望

考虑枚举答案是第k小的线段，那么要求前k-1小的线段必须同色，根据容斥可以得出这样的概率为\frac{1}{3^{k-1}}-\frac{1}{3^k}，然后根据上面的Lemma不难得出答案为

\begin{aligned} ans &= \frac{1}{3}\sum_{i=1}^n(\frac{1}{3^{i-1}}-\frac{1}{3^i})E(L_i)\\ &=\frac{1}{3n}\sum_{i=1}^n(\frac{1}{3^{i-1}}-\frac{1}{3^i})\sum_{j=1}^i\frac{1}{n-j+1}\\ &=\frac{1}{3n}\sum_{j=1}^n\frac{1}{n-j+1}\sum_{i=j}^n(\frac{1}{3^{i-1}}-\frac{1}{3^i})\\ &=\frac{1}{n}\sum_{j=1}^n\frac{1}{3^j(n-j+1)} \end{aligned}

Code


int n,ans;
int fac[MAXN],ifac[MAXN];

int main(){
    scanf("%d",&n);
    fac[0] = ifac[0] = 1;
    for(int i = 1;i <= n;i++)
        fac[i] = 1ll * fac[i - 1] * i % MOD;
    ifac[n] = Inv(fac[n]);
    for(int i = n - 1;i >= 1;i--)
        ifac[i] = 1ll * ifac[i + 1] * (i + 1) % MOD;
    int inv3 = Inv(3);
    for(int i = 1,tmp = inv3;i <= n;i++,tmp = 1ll * tmp * inv3 % MOD)
        addmod(ans,1ll * tmp * ifac[n - i + 1] % MOD * fac[n - i] % MOD);
    ans = 1ll * ans * ifac[n] % MOD * fac[n - 1] % MOD;
    printf("%d\n",ans);
    return 0;
}