标签：骰子 frac jzoj8132 Max sum prod

jzoj8132 扔骰子

题面

传送门

扔 \(n\) 个骰子，第 \(i\) 个有 \(a_i\) 个面，数值为\(1\)∼\(a_i\)，求扔出点数最大值的期望。

---

先将 \(a_i\) 排序。

则对于 \(Max=[a_{i-1}+1,a_i]\)，有 \(n-i+1\) 个位置对 \(Max\) 有影响。

此时，最大值为 \(Max\) 的概率为：后 \(n-i+1\) 个都小于等于 \(Max\) 的概率，减去后 \(n-i+1\) 个都小于 \(Max\) 的概率，于是答案为：

\[\sum_{i=1}^n \frac{1}{\prod_{k=i}^{n}a_k}\sum_{j=a_{i-1}+1}^{a_i} j(j^{n-i+1}-(j-1)^{n-i+1}) \]

后面和式除了头尾的相邻两项可以消掉，于是得到：

\[\sum_{i=1}^n \frac{1}{\prod_{k=i}^{n}a_k}(a_i^{n-i+2}-(a_{i-1}+1)\times a_{i-1}^{n-i+1}-\sum_{j=a_{i-1}+1}^{a_i}j^{n-i+1}) \]

后面 \(\sum_{i=1}^ni^k\) 就是 CF622F。

具体来说，经过证明可知 \(\sum _{i=1} ^n i^k\) 是一个 \(k+1\) 次多项式 \(f(n)\)。

\(n+1\) 个点确定一个 \(n\) 次多项式，我们用拉格朗日插值代入 \(n=[1,k+2]\) 这 \(k+2\) 个 \((x=n,y=f(n))\) 的值。

给出 \(n\) 次多项式的拉格朗日插值的公式：

\[f(x)=\sum _{i=1}^{n+1}y_i\prod_{j\ne i} \frac{x-x_j}{x_i-x_j} \]

直接做每次 \(O(k^2)\)，考虑优化后面的分子和分母。

带入 \(k+2\) 个值可以发现，分母是 1乘到i-1 再乘 -1乘到i-k-2，可预处理，而分子也可以用一个前缀后缀的乘积表示。

于是复杂度为求 \(k+2\) 个 \(y\) 的 \(O(k\log k)\)。

在这道题中，我们可以 \(O(n^2)\) 预处理 \(y\)，拉格朗日插值变为 \(O(n)\)。

总时间复杂度为 \(O(n^2)\)。

标签：骰子,frac,jzoj8132,Max,sum,prod
From： https://www.cnblogs.com/dccy/p/18353731