CF1601F Two Sorts

CF1601F Two Sorts

给定 (n)，将 (1sim n) 按照字典序排序，(a_i) 表示第 (i) 小的数，求：

[left(sum_{i=1}^{n} ((i-a_i)mod 998244353) ight) mod 10^9+7 ]

(1le nle 10^{12})

Solution

先暴力，我们按照字典序搜索（记 ( ext{cnt}) 和 ( ext{val}) 表示第 ( ext{cnt}) 小的数是 ( ext{val})）即可线性。

考虑根号分治（不搜索末 (6) 位），我们同样搜索，处理到 (overline { ext{valxxxxxx}}) 时（假设 (overline{ ext{val999999}} le n)，即没有任何上界限制），会发现可以快速计算这些值的和。

我们记 (cnt_{x}) 表示 (x) 的排名，(cnt'_x) 表示 (x) 在 (overline {abcdef}) （(0le a,b,c,d,e,fle 9)，即可以有前导零）的排名。

那么， (cnt_{overline { ext{valxxxxxx}}}=cnt_{overline{ ext{val}}}+cnt'_{overline{ ext{xxxxxx}}})，因此可以把贡献拆成：

[left((cnt_{overline{ ext{val}}}-10^6cdot val)+(cnt'_{overline{ ext{xxxxxx}}}-overline{ ext{xxxxxx}}) ight) mod 998244353 ]

因此，我们可以预处理 (overline{ ext{xxxxxx}}) 相关的信息，即 ((cnt'_{overline{ ext{xxxxxx}}}-overline{ ext{xxxxxx}}))。

由于上述式子是 ((A+B)mod P) 形式，而 (0le A,B<P)，因此值为 (A+B) 或 (A+B-P)，判断这个可以通过一个二分解决。

因此，总时间复杂度 (mathcal O(sqrt{n} log n))。

提一句，这个实在太难表述了，所以可以对照代码阅读。我的代码码量极小，并且是目前的最优解。