首页 > 其他分享 >CF1477F Nezzar and Chocolate Bars 题解

CF1477F Nezzar and Chocolate Bars 题解

时间:2023-05-01 23:22:07浏览次数:49  
标签:Nezzar lfloor Bars frac limits 题解 sum rfloor binom

题意: 有一根长为 \(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} \]

即为所求。

标签:Nezzar,lfloor,Bars,frac,limits,题解,sum,rfloor,binom
From: https://www.cnblogs.com/Charlie-Vinnie/p/17367067.html

相关文章

  • 4 月 30 日测试题解
    4月30日测试题解T1\({\color{green}{\text{100pts}}}\text{/100pts}\)题意一个无限长宽的棋盘,给出起点\(s\)和终点\(t\),行走方式是象棋中马的走法,问最少需要走多少步。对于\(100\%\)的数据,\(|x_s|,|y_s|,|x_t|,|y_t|\le10^7\)。思路\(\text{100pts}\)首先,坐......
  • 【题解】P3338 [ZJOI2014]力
    题目描述给出\(n\)个数\(q_1,q_2,\dotsq_n\),定义\[F_j~=~\sum_{i=1}^{j-1}\frac{q_i\timesq_j}{(i-j)^2}~-~\sum_{i=j+1}^{n}\frac{q_i\timesq_j}{(i-j)^2}\]\[E_i~=~\frac{F_i}{q_i}\]对\(1\leqi\leqn\),求\(E_i\)的值。\(1\le......
  • [P5785 [SDOI2012]任务安排] 题解
    P5785[SDOI2012]任务安排题目描述分析很明显是一个dp我们不妨设\(dp[i]\)表示枚举到\(i\)的最小费用\(t[i]\)表示加工完第\(i\)个任务所用的总时间,也就是\(T[i]\)的前缀和由于每一批任务前都要一个时间为\(s\)的开机工作我们不妨把每一个这样的\(s\)秒提出来,则这\(s\)秒都......
  • CF1624G 题解
    前言题目传送门!更好的阅读体验?比较好玩的二进制题目。思路答案最小,也就是说较高位要尽可能小。所以很容易想到从最高位开始枚举。第\(i\)位为\(0\),等价于选出的所有边的第\(i\)位都为\(0\)。同时,由于我们是贪心,如果之前枚举过的第\(j\)位可以是\(0\),那么这两个条件......
  • 洛谷 P7579 「RdOI R2」称重(weigh) 题解
    题意:题目一道交互题。有n个球,里面有两个假球,假球比普通球的要轻,每次可以询问任意两组球的轻重关系,第一组轻为<,第二组轻为>,一样重量为=。思路:先考虑在一个区间内找1个假球。我们可以将区间尽量平均分为3份,先询问相等的两组球的轻重关系,分3种情况:第一组轻......
  • 【题解】CF44G Shooting Gallery
    题目大意给定\(n\)个三维空间的平面,由高度\(z\)、\(x\)的范围\([xl,xr]\)和\(y\)的范围\([yl,yr]\)来表示。有\(m\)次射击,每次射击点\((x,y)\),摧毁包含此点的\(z\)值最小的平面,输出此平面编号,若摧毁不了任何平面,输出\(0\)。题解点查平面不好做,于是可以转化为平面查点,先将平面按......
  • Codeforces Round 869 (Div.1 & Div.2) 题解
    2A.Politics因为编号为\(1\)的人一定不会离开,那么最后留下的人一定要和编号为\(1\)的人的所有参数都一致,所以计数即可。#include<bits/stdc++.h>#include<ext/pb_ds/assoc_container.hpp>#include<ext/pb_ds/tree_policy.hpp>#include<ext/pb_ds/hash_policy.hpp>u......
  • CF51F Caterpillar题解
    题目传送门题意:定义毛毛虫为一种特殊的树,形如一条链上挂着若干个叶子。特殊地,在本题中的毛毛虫允许自环但不允许重边。给定一个无向图,每次操作可以合并两个点以及两个点的出边(两个点有相同出边则出现重边,两个点之间有边则出现自环)。求将其变为毛毛虫的最小操作次数。容易发现,......
  • Windows下安装Docker详细过程及问题解决
    官方手册供参考:https://docs.docker.com/desktop/windows/一:什么是Docker?Docker是一个开放源代码软件,是一个开放平台,用于开发应用、交付(shipping)应用、运行应用。Docker允许用户将基础设施(Infrastructure)中的应用单独分割出来,形成更小的颗粒(容器),从而提高交付软件的速度。Dock......
  • 义中常规赛430题解
    T1二分一个删除的数字个数然后考虑删除的数字肯定是从大到小来的,所以预处理一个降序的数组,这样能知道二分的数字个数所对应的数字。在原数组上跑最大子段和,如果碰到大于二分位置的数字就删了。最终成绩26分,因为对于二分的个数mid,原数组中a[mid]不止1个的话,无法判断哪些该删,哪......