「Summary」2022-08-17 做题记录

纯纯的白齿

2022-08-17

$\mathbb{CF1278F}$

原来 $E(x^k) \not = E(x)^k$

考虑枚举这 $n$ 次中有多少次第一张牌是 $\mathcal{Joker}$ ，则式子为 $\sum_{i = 0}^{n}\binom{m}{i} (\frac{1}{m})^i(1 - \frac{1}{m})^{n - i} i^k$ 。

然后就推不下去了。，。

看到 $Dead\_X$ 的题解，通俗易懂，配合 $nKessi$ 的现场解说，我不能不懂。

但是似乎还有一个推式子的做法。

这个后面的 $i^k$ 可以转化为第二类 $\mathrm{Stiring}$ 数的形式，则原式变成 $\sum_{i = 0}^{n} \binom{m}{i} (\frac{1}{m})^i(1 - \frac{1}{m})^{n - i} \sum_{j = 0}^{k} \begin{Bmatrix} k \\ j \end{Bmatrix} i^{j}$ 。

然后开始推

$$ \begin{aligned} &\sum_{i = 0}^{n} \binom{m}{i} (\frac{1}{m})^i(1 - \frac{1}{m})^{n - i} \sum_{j = 0}^{k} \begin{Bmatrix} k \\ j \end{Bmatrix} i^{j} \\ =&\sum_{j = 0}^{k} \begin{Bmatrix} k \\ j \end{Bmatrix} \sum_{i = 0}^{n} \binom{m}{i} (\frac{1}{m})^i(1 - \frac{1}{m})^{n - i} i^j \\ =&\sum_{j = 0}^{k} j! \begin{Bmatrix} k \\ j \end{Bmatrix} \sum_{i = 0}^{n} \binom{m}{i} (\frac{1}{m})^i(1 - \frac{1}{m})^{n - i} \binom{i}{j} \\ =& 这里是一些奇妙重重的变换 🤡 \\ =& \sum_{j = 0}^{k} \begin{Bmatrix} k \\ j \end{Bmatrix} - (\frac{1}{m})^j \end{aligned} $$

$\mathbb{CF482C}$

$Rabbit\_Mua$ 👎 $nKessi$ 👍

一个显而易见的想法是枚举每一个字符串，定义 $dp_{sta}$ 表示猜的字符集合为 $sta$ 到才出来的期望步数。

那么转移从大往小就是 $dp_{sta} = 1 + \sum_{1<

时间复杂度为 $O(nm2^m)$ 时限一秒 ，过不了。

考虑不去枚举当前的字符串。

定义 $num_{sta}$ 表示在 $sta$ 情况下不能确定的字符串的个数，这样就可以实现同时转移，方程为 $dp_{sta} = 1 + \sum_{1<

现在就行了。