TRZ_2007 的博客

TRZ_2007 的博客

【题解】暗夜密语

posted on 2019-08-29 14:29:19 | under 团队题解 |

Remarks

这道题目很有意思,因为它的题目描述十分的迷,所以我们先把它翻译过来。

Solution

我们设这一基础值的集合为 $a$ ,特殊值为 $G$ ,神秘值为 $F$ ,则特殊值的求值公式如下:
求 $G$ 集合第 $x$ 个数的公式为
$$G_x = \sum\limits_{k = 1}^xa_k.p^k \text{ mod }t$$
求 $F$ 集合第 $x$ 个数的公式为
$$F_x = \sum\limits_{k = 1}^x(G_k)^k \text{ mod }t$$
这样我们就解决了前两步的操作,其实最后一步也很简单,就是让你求 $[a,b]$ 中的区间第 $k$ 小,不会主席树怎么办?没事,出题人良心地给了20分的暴力分,于是正解的复杂度是 $O(nlog_2^n)$ ,很快吧。
代码自己写吧,相信你一定能写出来的哦!