Vodka

题目描述

Alan 喝了假的绝对伏特加，想问你一个问题：

Alan 在玩骰子游戏，Alan 会玩 \(n\) 轮骰子，每轮的数值在 \([1, K]\) 中随机出现。记 \(a_i\) 表示 \(n\) 轮投掷中，数值 \(i\) 出现的次数，求 \(a_1^F\times a_2^F\times \cdots \times a_L^F\) 的期望。

\(0\le n,k\le 10^9\)，\(1\le F\le 10^3\)，\(1\le LF\le 50000\)，\(L\le K\)。

题解

现场得分：20/40（暴力写挂）。

先考虑 \(L=1\) 怎么做：

考虑 \(a^k\) 的组合意义：从 \(a\) 中可以重复地选 \(k\) 个。把每轮看成一个数 \(b_i=0/1\) 表示取或不取，答案为 \((b_0+b_1+\cdots+b_n) ^k\)。

我们钦定 \(k\) 个中间总共取了 \(t\) 个不同的轮，对应的期望为 \(\begin{Bmatrix}n\\ t\end{Bmatrix}\frac{1}{K^{t}}\)。

对于 \(L\ne 1\)，考虑在前面加一维，记录前 \(i\) 个数，总共用了 \(j\) 个不同的轮，背包卷积即可。