主页
搜索
最近更新
数据统计
赞助我们
系统公告
1
/
1
请查看完所有公告
G - Accumulation of Wealth
最后更新于 2025-06-15 22:57:11
作者
qqqaaazzz_qwq
分类
题解
复制 Markdown
查看原文
更新内容
不难发现那个 $\sum_{i=1}^{m-1} c_i$ 就等于序列长度。所以考虑对于每种元素单独计算答案。 因为非 $1$ 的元素还会有一个奇怪的“出现时间”，即第一次在序列里出现的位置，不好算，所以考虑先算 $1$ 的答案。 设 $f_i$ 表示序列长度为 $i$ 的时候，$1$ 的期望出现次数。则： $$ f_{i+1}=\dfrac{p}{100}f_i+\dfrac{100-p}{100} \dfrac{f_i}{i}(f_i+1)+\dfrac{100-p}{100} \dfrac{i-f_i}{i}f_i $$ 展开之后可以把二次项消掉，得： $$ f_{i+1}=(\dfrac{100-p}{100i}+1)f_i $$ 因此，我们令 $g_i = \dfrac{100-p}{100i}+1$，$g_n=1$，则当某个元素第一次出现的位置是 $k$ 的时候，最终这个元素的期望出现次数就是 $g_k \times g_{k+1} \times ... \times g_n$。 当计算元素 $j$ 的答案的时候，我们枚举元素 $j$ 第一次出现的位置，乘上概率和期望再累加就行了。 进一步的，我们发现这个东西可以用 NTT 卷积来优化，于是就做完了，时间复杂度 $\Theta(n \log n)$。 [$\Theta(n^2)$ 实现](https://atcoder.jp/contests/abc409/submissions/66605411) [$\Theta(n \log n)$ 实现](https://atcoder.jp/contests/abc409/submissions/66605509)
正在渲染内容...
点赞
0
收藏
0
