2016 年 ACM/ICPC 青岛区域赛 Problem C Pocky

昨晚乱入学弟的训练赛,想了一下这个题。推导的过程中,加深了对公理化的概率论的理解。$ ewcommand{d}{mathop{}!mathrm{d}}$


解法一

考虑 $ d < L$ 的情形。
egin{equation*}
P(X = 1) = frac{d}{L}
end{equation*}
egin{align*}
P(X = 2) &= int_0^{L - d} frac{d x}{L} frac{d}{L - x} \
&= frac{d}{L}lnfrac{L}{d}
end{align*}
egin{align*}
P(X = 3) &= int_{0}^{L-d}frac{d x}{L}int_{0}^{L-x-d}frac{d y}{L-x}frac{d}{L-x-y} \
&= int_{0}^{L-d} frac{d x}{L} frac{d}{L - x} ln frac{L - x}{d} \
&= frac{d}{L}frac{1}{2}ln^2frac{L}{d}
end{align*}
egin{align}
P(X = 4) &= int_0^{L - d}frac{d x}{L} int_0^{L - x - d} frac{d y}{L-x}int_0^{L-x-y-d}frac{d z}{L - x -y}frac{d}{L - x - y - z} otag\
&= int_0^{L - d}frac{d x}{L} int_0^{L - x - d} frac{d y}{L-x} frac{d}{L - x -y} ln frac{L - x -y}{d} otag\
&= int_0^{L - d}frac{d x}{L} frac{d}{L-x}frac{1}{2}ln^2frac{L-x}{d} label{Int:1}
end{align}
令 $u = frac{L-x}{d}$ ,则 $d x = -dd u$ ,有
egin{align*}
eqref{Int:1} &= int_1^frac Ldfrac dLfrac{d u}{u}frac 12ln^2u \
&= int_1^frac Ldfrac dLfrac 16dln^3u \
&= frac 16frac dLln^3frac Ld
end{align*}
不难推出
egin{equation*}
P(X = n) = frac dLfrac1{(n-1)!}ln^{n-1}frac Ld
end{equation*}
所以
egin{align*}
E(X) &= sum_{ n ge 1 } n P(X=n) \
&= frac dL sum_{n ge 1} frac n{(n-1)!}ln^{n-1}frac Ld \
&= frac dL sum_{n ge 0} frac{n+1}{n!} ln^nfrac Ld \
&= frac dL (lnfrac Ld + 1) mathrm{e}^{lnfrac Ld} \
&= lnfrac Ld + 1
end{align*}
上式中的求和用到了 $(x+1)mathrm{e}^x$ 的 Maclaurin 展开:
egin{equation*}
(x+1)mathrm{e}^x = sum_{nge 0} frac{n + 1}{n!} x^n
end{equation*}

解法二

用 $f(x)$ 表示绳长为 $x$ 时切割次数的期望,则有
$$
f(x) =
egin{cases}
0, && ext{if $xle d$;} \
1 + int_0^x frac{dy}{x}f(y), && ext{otherwise.}
end{cases}
$$
考虑 $x>d$ 的情形,此时有
egin{align}
f(x) &= 1 + int_0^x frac{d y}{x}f(y) otag\
&= 1 + int_0^d frac{d y}{x}f(y) + int_d^x frac{d y}{x}f(y) otag\
&= 1 + int_d^x frac{d y}{x}f(y) label{Int:2}
end{align}
对 eqref{Int:2} 式两边求导,得
egin{align*}
f'(x) &= frac{f(x)}x - frac1{x2}int_dxd yf(y) \
&= frac{f(x)}x - frac1x(f(x) -1) \
&= frac1x
end{align*}
又 $limlimits_{x o d^+} f(x) = 1 $,得 $$ f(x) = ln x + 1 - ln d $$


解法二来自 Huo Chen

原文地址:https://www.cnblogs.com/Patt/p/7712248.html