题意：
有一个序列 \(a_1,\cdots,a_n\)，初始时它们全为 \(1\)。进行 \(d\) 轮操作：每轮操作以正比于 \(a\) 的概率选择一个 \(a_i\) 加 \(1\)。求最后 \(a_1,\cdots,a_n\) 中前 \(r\) 大的和的期望，精度要求 \(10^{-6}\)。
\(n,d,r\leq 500\)。
题解：
即为求：
\[\begin{aligned} &\frac{1}{n(n+1)\cdots(n+d-1)}\sum_{a_1+\cdots+a_n=d}\binom{d}{a_1,\cdots,a_n}\prod_{i=1}^n (a_i!)\sum_{k=1}^{r} kthmax_{i=1}^{n}(a_i)\\ =&\frac{d!}{n(n+1)\cdots(n+d-1)}\sum_{a_1+\cdots+a_n=d}\sum_{k=1}^{r} kthmax_{i=1}^{n}(a_i)\\ =&\frac{1}{\binom{n+d-1}{d}}\sum_{a_1+\cdots+a_n=d}\sum_{k=1}^{r} kthmax_{i=1}^{n}(a_i)\\ \end{aligned} \]
设 \(h_{n,d}\) 表示所有 \(a_1+\cdots+a_n=d\) 的方案中前 \(r\) 大的 \(a_i\) 的和的和。那么：
\[h_{n,d}=\sum_{i=1}^{n}\binom{n}{i}\left(\min(r,i)\binom{(d-i)+i-1}{i-1}+h_{i,d-i}\right) \]
其中 \(i\) 枚举的是有多少 \(a_j\) 至少为 \(1\)。DP 的过程可以理解为从最底层开始一层一层地在上一层的基础上往上填。
对于取模而不必考虑精度的情况，可以做到更快。
对于 \(a_1,\cdots,a_n\) 中前 \(r\) 大的和，可以转为 \(\sum_{i\geq 1}\min(r,(a_1,\cdots,a_n中\geq i的数的个数))\)。
设 \(f_{i,k}\) 表示 \(a_1,\cdots,a_n\) 中恰好有 \(k\) 个数 \(\geq i\) 的方案数，那么：
\[\begin{aligned} f_{i,k}&=\binom{n}{k}[x^d]\left(\frac{x^i}{1-x}\right)^k\left(\frac{1-x^i}{1-x}\right)^{n-k}\\ \end{aligned} \]
我们要求的是：
\[\begin{aligned} &\sum_{i\geq 1}\sum_{k}\min(r,k)f_{i,k}\\ =&\sum_{i\geq 1}\sum_{k}\min(r,k)\binom{n}{k}[x^{d}]\frac{x^{ik}(1-x^i)^{n-k}}{(1-x)^n}\\ =&\sum_{i\geq 1}\sum_{k}\min(r,k)\binom{n}{k}\sum_{j\geq 0}[x^j]\bigg(x^k(1-x)^{n-k}\bigg)[x^{d-ij}]\frac{1}{(1-x)^n}\\ =&\sum_{j\geq 0}\left(\sum_{k}\min(r,k)\binom{n}{k}[x^j]x^k(1-x)^{n-k}\right)\left(\sum_{i\geq 1}[x^{d-ij}]\frac{1}{(1-x)^n}\right)\\ =&\sum_{j\geq 0}A_jB_j\\ \end{aligned} \]
第二步很有技巧性，实现了 \(i,k\) 的分离。
对于 \(A_j\)：
\[\begin{aligned} A_j=&\sum_{k}\min(r,k)\binom nk[x^j]x^k(1-x)^{n-k}\\ =&\sum_{k}\min(r,k)\binom nk(-1)^{j-k}\binom{n-k}{j-k}\\ \end{aligned} \]
其实到这里就已经可以直接 \(O(n\log n)\) 卷了，但事实上：
\[\begin{aligned} A_j=&\sum_{k}\min(r,k)\binom nk[x^j]x^k(1-x)^{n-k}\\ =&\sum_{k=0}^rk\binom nk[x^j]x^k(1-x)^{n-k}+r\sum_{k>r}\binom{n}{k}[x^j]x^k(1-x)^{n-k}\\ \end{aligned} \]
对于后者：
\[\begin{aligned} &\sum_{k=0}^r\binom{n}{k}[x^j]x^k(1-x)^{n-k}\\ =&\sum_{k=0}^r[u^kx^j]\binom{n}{k}{(ux)}^k(1-x)^{n-k}\\ =&\sum_{k=0}^r[u^kx^j]((ux)+(1-x))^n\\ =&[u^rx^j]\frac{(ux+1-x)^n}{1-u}\\ =&[u^rx^j]\frac{((u-1)x+1)^n}{1-u}\\ =&\binom{n}{j}[u^r]\frac{(u-1)^j}{1-u}\\ =&\binom{n}{j}(-1)^{j-r}\binom{j-1}{r} \end{aligned} \]
对于前者也是类似的。
对于 \(B_j=\sum_{ij\leq d}c_{ij}\)，其中 \(c_p=[x^{d-p}]\frac{1}{(1-x)^n}\)。这相当于一个高维后缀和（一维对应一个质数幂），可以做到 \(O(n\log \log n)\)。
总时间复杂度 \(O(n\log \log n)\)。
原文地址：http://www.cnblogs.com/ez-lcw/p/16837414.html
1. 本站所有资源来源于用户上传和网络，如有侵权请邮件联系站长！
2. 分享目的仅供大家学习和交流，请务用于商业用途!
3. 如果你也有好源码或者教程，可以到用户中心发布，分享有积分奖励和额外收入！
4. 本站提供的源码、模板、插件等等其他资源，都不包含技术服务请大家谅解！
5. 如有链接无法下载、失效或广告，请联系管理员处理！
6. 本站资源售价只是赞助，收取费用仅维持本站的日常运营所需！
7. 如遇到加密压缩包，默认解压密码为"gltf",如遇到无法解压的请联系管理员！
8. 因为资源和程序源码均为可复制品，所以不支持任何理由的退款兑现，请斟酌后支付下载
声明：如果标题没有注明"已测试"或者"测试可用"等字样的资源源码均未经过站长测试.特别注意没有标注的源码不保证任何可用性
