[ABC239Ex] Dice Product 2 题解

原题链接：ABC239Ex。

题意不多赘述。

看到求期望值，我们想到可以用期望 DP。

设 \(dp_{i}\) 表示最终结果大于等于 \(i\) 时的操作次数的期望值。

那么我们可以得到一个基本的状态转移方程：\(dp_{i}=\frac{1}{n} \times \sum_{j=1}^{n}dp_{\left \lceil \frac{i}{j} \right \rceil} + 1\)。

方程表示的意义是，这次骰子的点数 \(j\) 可能是 \(1\) 到 \(n\)，所以每一种的概率为 \(\frac{1}{n}\)，因为乘积为 \(i\)，所以分别对应之前的 \(\left \lceil \frac{i}{j} \right \rceil\)，加上 \(1\) 表示当前需要骰一次。

但是因为当 \(j=1\) 时 \(\left \lceil \frac{i}{j} \right \rceil=i\)，整个方程不好转移，所以我们可以考虑把转移方程变一下，变成：\(dp_{i}=\frac{1}{n-1} \times \sum_{j=2}^{n}dp_{\left \lceil \frac{i}{j} \right \rceil} + \frac{n}{n-1}\)。这里就相当于是把 \(j=1\) 的情况去掉了，但是总数就变成了 \(n-1\) 个，于是整体乘上了一个 \(\frac{n}{n-1}\)。

显然最终我们要去求的答案就是 \(dp_{m+1}\)，注意不是 \(dp_m\)，因为要求严格大于。

如果纯暴力的话时间复杂度是 \(O(nm)\) 的，加上记忆化会优化到 \(O(m)\)，再加上整除分块就可以过了。（1000000000 1000000000 的数据本地要跑 \(5\) 秒，开 O2 的话 \(1.4\) 秒，但是在 Atcoder 上跑得很快）。

评测记录。