Nowcoder 5889 D

作者: ffacs 分类: 题目 发布时间: 2020-06-10 14:24

题意

给了你一个数组长度 $n$,并规定了 $3$ 种操作次数为 $m$,操作 $1$ 是把一个连续的区间内所有的数字 $x$变为$x^{k} \bmod M$,操作 $2$ 是把一个连续的区间内所有的数字 $x$ 变为$x*k \bmod M$,操作 $3$ 是询问你一个区间中所有数的积的对 $M$ 取模后的结果。其中$M=1e7+19$,$\sum n=10^5,m\le 3n,a_i < M$

解法

首先想到线段树维护的方法。用两个tag,一个tag表示子树要变成几次方,一个tag表示子树要成多少。要先变几次方再乘。那么这样的时间复杂度是$O(n\log^2n)$ 的。被卡了。考虑消去一个$\log$。注意到模数不大而且是个质数。那就用原根进行优化。$6$ 是模数的一个原根。那么每一个小于 $M$ 的数都能表示成 $6$ 的幂次。于是乘法就能变成加法,幂次就能变成乘法了。这样复杂度就是 $O(n\log n)$ 。

发表评论

电子邮件地址不会被公开。 必填项已用*标注