CF1477F Nezzar and Chocolate Bars 题解

题意： 有一根长为 \(1\) 的巧克力，已经被切了 \(m-1\) 刀被分成 \(m\) 分，接下来每次在整根长度为 \(1\) 的巧克力上均匀随机一个点切一刀，求每一小段巧克力长度均小于一个给定值 \(K\) 需要的期望次数。

引理：Irwin-Hall 分布：对于 \(n\) 个在 \([0,1]\) 内均匀分布的实数随机变量，它们的和不超过一个实数 \(z\) 的概率为：

\[I_n(z)=\sum\limits_{k=0}^{\lfloor z\rfloor} (-1)^k\binom{n}{k}\frac{(z-k)^n}{n!}
\]

首先令 \(f_L(n)\) 表示将长度为 \(L\) 的巧克力切 \(n\) 刀已经合法的概率。

\[\begin{aligned}
f_L(n)&=n!\int\limits_{x_i\in[0,K],\sum_{i=1}^{n+1} x_i=L}\prod \mathrm{d}\frac{x_i}{L}\\
&=n!\int\limits_{x_i\in[0,K],\sum_{i=1}^{n} x_i\in[L-K,L]}\prod \mathrm{d}\frac{x_i}{L}\\
&=n!(\frac{K}{L})^n\int\limits_{x_i\in[0,1],\sum_{i=1}^{n} x_i\in[\frac{L-K}{K},\frac{L}{K}]}\prod \mathrm{d}x_i\\
&=n!(\frac{K}{L})^n(I_{n}(\frac{L}{K})-I_{n}(\frac{L}{K}-1))\\
&=n!w^n\Big(\sum\limits_{k=0}^{\lfloor \frac{1}{w}\rfloor} (-1)^k\binom{n}{k}\frac{(\frac{1}{w}-k)^n}{n!}-\sum\limits_{k=0}^{\lfloor \frac{1}{w}\rfloor-1} (-1)^k\binom{n}{k}\frac{(\frac{1}{w}-1-k)^n}{n!}\Big)\texttt{ (Let }w=\frac{K}{L}\texttt{)}\\
&=n!\Big(\sum\limits_{k=0}^{\lfloor \frac{1}{w}\rfloor} (-1)^k\binom{n}{k}\frac{(1-wk)^n}{n!}-\sum\limits_{k=0}^{\lfloor \frac{1}{w}\rfloor-1} (-1)^k\binom{n}{k}\frac{(1-w(k+1))^n}{n!}\Big)\\
&=\sum\limits_{k=1}^{{\lfloor \frac{1}{w}\rfloor}}(-1)^k(\binom{n}{k}+\binom{n}{k-1})(1-wk)^n\\
&=\sum\limits_{k=0}^{{\lfloor \frac{1}{w}\rfloor}}(-1)^k\binom{n+1}{k}(1-wk)^n\\
&=\sum\limits_{k=0}^{{\lfloor \frac{L}{K}\rfloor}}(-1)^k\binom{n+1}{k}(\frac{L-Kk}{L})^n\\
\end{aligned}
\]

卷起来，可以得到

设 \(f(n)\) 表示总共切 \(n\) 刀合法的概率，\(F(z)\) 为 \(f(n)\) 的 EGF；令 \(F_L(z)\) 为 \(f_L(n)\) 的 EGF，那么有 \(F(n)=\prod_{i=1}^m F_{L_i}(z)\)，且

\[\begin{aligned}
F_L(z)&=\sum\limits_{n\ge 0} \frac{1}{n!}\sum\limits_{k=0}^{{\lfloor \frac{L}{K}\rfloor}}(-1)^k\binom{n+1}{k}(\frac{L-Kk}{L}z)^n\\
&=\sum\limits_{k=0}^{{\lfloor \frac{L}{K}\rfloor}}(-1)^k\sum\limits_{n\ge 0} \frac{1}{n!}\binom{n+1}{k}(\frac{L-Kk}{L}z)^n\\
&=\sum\limits_{k=0}^{{\lfloor \frac{L}{K}\rfloor}}(-1)^k\sum\limits_{n\ge 0} \frac{n+1}{k!(n+1-k)!}(\frac{L-Kk}{L}z)^n\\
&=\sum\limits_{k=0}^{{\lfloor \frac{L}{K}\rfloor}}(-1)^k\sum\limits_{n\ge 0} \frac{k+(n+1-k)}{k!(n+1-k)!}(\frac{L-Kk}{L}z)^n\\
&=\sum\limits_{k=0}^{{\lfloor \frac{L}{K}\rfloor}}(-1)^k\sum\limits_{n\ge 0} (\frac{1}{(k-1)!(n+1-k)!}+\frac{1}{k!(n-k)!})y_k^n\texttt{ (Let }y_k=\frac{L-Kk}{L}z\texttt{)}\\
&=\sum\limits_{k=0}^{{\lfloor \frac{L}{K}\rfloor}}(-1)^k(\frac{y_k^{k-1}}{(k-1)!}+\frac{y_k^{k}}{k!})\mathrm{e}^{y_k} \\
&=\sum\limits_{k=0}^{{\lfloor \frac{L}{K}\rfloor}}(-1)^k(\frac{1}{(k-1)!}(\frac{L-Kk}{L})^{k-1}z^{k-1}+\frac{1}{k!}(\frac{L-Kk}{L})^kz^k)\mathrm{e}^{\frac{L-Kk}{L}z} \\
&=\mathrm{e}^z\sum\limits_{k=0}^{\lfloor \frac{L}{K}\rfloor}\sum\limits_{r=0}^{1} a_{k,r}z^{k-r}\mathrm{e}^{\frac{K}{L}kz}
\end{aligned}
\]

其中 \(a_{k,0}=(-1)^k\frac{1}{k!}(\frac{L-Kk}{L})^k,a_{k,1}=(-1)^{k-1}\frac{1}{(k-1)!}(\frac{L-Kk}{L})^{k-1}\)。

于是将所有 \(F_{L_i}(z)\) 卷起来，可以得到

\[\begin{aligned}
F(z)&=\sum\limits_{k=0}^{\frac{L}{K}}\sum\limits_{r=0}^{n}a_{k,r}z^{k-r}\mathrm{e}^{(n+\frac{K}{L}k)z}\\
&=\sum\limits_{k}\sum\limits_{r}a_{k,r}z^{k-r}\sum\limits_{t\ge 0}\frac{(n+\frac{K}{L}k)^t}{t!}z^t\\
&=\sum\limits_{k}\sum\limits_{r}a_{k,r}\sum\limits_{t\ge 0}\frac{(n+\frac{K}{L}k)^t}{t!}z^{t+k-r}\\
\end{aligned}
\]

注意 \(F(z)\) 是 \(f(z)\) 的 EGF，我们想求的是 OGF，所以令

\[F^*(z)=\sum\limits_{k}\sum\limits_{r}a_{k,r}\sum\limits_{t\ge 0}\frac{(n+\frac{K}{L}k)^t}{t!}(t+k-r)!z^{t+k-r}
\]

则答案为

\[\begin{aligned}
F^*(1)&=\sum\limits_{k}\sum\limits_{r}a_{k,r}\sum\limits_{t\ge 0}\frac{(n+\frac{K}{L}k)^t}{t!}(t+k-r)!\\
&=\sum\limits_{k}\sum\limits_{r}a_{k,r}(k-r)!\sum\limits_{t\ge 0}\binom{t+k-r}{t}(n+\frac{K}{L}k)^t\\
&=\sum\limits_{k}\sum\limits_{r}\frac{a_{k,r}(k-r)!}{(1-n-\frac{K}{L}k)^{k-r+1}}
\end{aligned}
\]

即为所求。

CF1477F Nezzar and Chocolate Bars 题解的相关教程结束。