CF Round#698 Div1. Nezzar and Chocolate Bars
CF Round#698 Div1. Nezzar and Chocolate Bars
前言
这就是大道至简吗。。
为什么和某ZJOI开关一样，到最后就是个背包。。
题目大意：
给定 \(n,K\) 和一些棍子长度为 \(l_i(i\in [1,n])\) （实数！）
每次随机选择一根棍子，概率与 \(l_i\) 成正比，然后随机分裂成两段（实数！）
一直分裂，直到每根棍子 \(l_i\leq K\) ，求期望分裂次数
\[ \ \]
根据题意容易归纳一个更直观的模型：
把这些 \(l_i\) 排在数轴上，初始时，点集为 \(0,l_1,l_1+l_2,\ldots\)
每次随机在数轴上撒一个点，直到点集中相邻两点距离 \(\leq K\) 为止
考虑从简单情况入手
\[ \ \]
n=1
单棍情况，设长度为 \(L\) ，考虑期望的简单等价变换
\(\displaystyle E(\text{条件第一次成立操作数})=\sum_{i=0}^{\infty} P(i次操作条件未成立)\)
设 \(P_n\) 为操作 \(n\) 次成立（不是恰好）的概率
(变量名重了不要介意)
设 \(n\) 次操作后的点集排列之后为 \(X_i\) ，其中 \(X_0=0,X_{n+1}=L\)
我们要求 \(\forall i\in[1,n+1],Z_i=X_i-X_{i-1}\leq K\) ，考虑用一个二项式反演来解决这个计算
设 \(W=\lfloor \frac{L}{K}\rfloor\)
\(\displaystyle P_n=\frac{1}{L^n}\sum_{i=0}^{W} (-1)^i\binom{n+1}{i}(L-iK)^n\)
其意义即为从分成的 \(n+1\) 个 \(Z_i\) 中选择 \(i\) 个强制不合法，然后剩下的随意分布，由此计算概率
\[ \ \]
一般情形
考虑一样的期望转概率，设 \(p_m\) 为 \(m\) 次完成的概率， \(q_m=1-p_m\)
\(\displaystyle q_m=\sum_{j_1+j_2+\cdots +j_n=m} \frac{m!}{j_1!j_2!\cdots j_n!}\prod (\frac{l_i}{\sum l_k})^{j_i}P_{i,j_i}\)
显然这里考虑用 \(\text{EGF}\) 积的形式来表示，设 \(S=\sum l_i\)
回到上一步，这里我们对于 \(i,l_i\) 计算其 \(P_n\) 加上 \(\frac{l_i}{S}\) 系数的 \(\text{EGF}\) ，沿用上面的 \(L=l_i\)
\(\displaystyle F_i(x)=\text{EGF(P)}=\sum_{n\ge 0}\frac{1}{n!}(\frac{L}{S})^n\sum_{i=0}^W(-1)^{i}\binom{n+1}{i}(1-i\frac{K}{L})^{n}x^n\)
\(\displaystyle F_i(x)=\sum_{n\ge 0}\frac{1}{n!}\sum_{i=0}^W(-1)^{i}\binom{n+1}{i}(\frac{L-iK}{S})^{n}x^n\)
设 \(\displaystyle u=\frac{L-iK}{S}x\)
\(\displaystyle F_i(x)=\sum_{i=0}^W\frac{(-1)^{i}}{i!}\sum_{n\ge i-1}\frac{n+1}{(n+1-i)!}u^n\)
令 \(n'=n+1-i\) ， \(n=n'+i-1\) ，将 \(n'\) 带入
\(\displaystyle F_i(x)=\sum_{i=0}^W\frac{(-1)^{i}}{i!}\sum_{n\ge 0}\frac{n+i}{n!}u^{n+i-1}\)
将 \(n,i\) 拆开
\(\displaystyle F_i(x)=\sum_{i=0}^W \frac{(-1)^{i}}{i!}(u^{i}\sum_{n\ge 0}\frac{1}{n!}u^{n}+u^{i-1}\sum_{n\ge 0}\frac{i}{n!}u^{n})\)
\(\displaystyle F_i(x)=\sum_{i=0}^W \frac{(-1)^{i}}{i!}(u^{i}+iu^{i-1})e^u\)
容易发现我们需要多项式是 \(F(x)=e^x-\prod F_i(x)\)
最终 \(F(x)\) 的每一项，都会是 \(x^k e^{cx}\) 的形式
其中 \(e^u\) 中的 \(u\) 总是 \(\frac{1}{S}(L-iK)x\) ，合并之后 \(L\) 之和总是存在，记录 \(\sum i\) 即可，为 \(O(S)\)
而每项要么是 \(u^ie^u\) 要么是 \(u^{i-1}e^u\) ，可以考虑记录一下 \(u^{i-1}e^u\) 出现的次数，为 \(O(n)\)
我们的多项式项数是 \(O(nS)\) 的
\[ \ \]
最终我们还需要对于每一项计算答案
我们要计算 \(\displaystyle \sum_{n\ge 0}n![x^n]F(x)\) ，考虑形如 \(x^ke^{cx}\) 一项的贡献
\(\displaystyle \sum_{n\ge k}n=\sum_{n\ge k}\frac{n!}{(n-k)!}c^{n-k}=k!\sum_{n\ge 0}\binom{n+k}{n}c^{n}\)
由于 \(\displaystyle \binom{n+k}{n}=(-1)^{n}\binom{-k-1}{n}\)
带入广义二项式定理得到
\(\displaystyle k!\sum_{n\ge 0}\binom{n+k}{n}c^{n}=k!(1-c)^{-k-1}\)
根据是否用 \(\text{NTT}\) 优化，复杂度会有所不同
over.
1 |
|
