P8576 「DTOI-2」星之界 题解

lzh0220 · 2025-04-10 16:05:22 · 题解

题意

给你一个序列 a，有两种操作：

• 操作一：将 [l,r] 内所有 a_i=x 的 a_i 改为 y。

• 操作二：求 \prod\limits_{i = l}^{r} C_{\sum_{j = l}^{i}a_j}^{a_i}\ \bmod 998244353 的值。

思路

发现求的那个式子可以转换成 \frac{(\sum\limits_{i=l}^ra_i)!}{\prod\limits_{i=l}^r(a_i!)}。

即我们需要维护区间和、区间阶乘之积。

观察到 n\le10^5，因此考虑分块。

每一次修改操作暴力重构散块。对于整块 k，我们可以用并查集维护相同的数，对该块中每一个出现的数，记录第一个出现的位置，将其他相同的数的父亲指向该位置。同时维护块中每一个数的出现次数，查询时将相同的 a_i! 合并，光速幂计算。

时间复杂度 O(n\sqrt n)，代码比较丑就不贴了。

注意并查集不要递归，否则会 MLE。

做完这道题可以去做一下未来日记，一样的套路。