P3747 [六省联考 2017] 相逢是问候

> Informatik verbindet dich und mich. > 信息将你我连结。 B 君希望以维护一个长度为 $n$ 的数组，这个数组的下标为从 $1$ 到 $n$ 的正整数。 一共有 $m$ 个操作，可以分为两种： - `0 l r` 表示将第 $l$ 个到第 $r$ 个数（ $a_l,a_{l+1} ...a_r$）中的每一个数 $a_i$ 替换为 $c^{a_i}$，即 $c$ 的 $a_i$ 次方，其中 $c$ 是输入的一个常数，也就是执行赋值 $a_i = c^{a_i}$。 - `1 l r` 求第 $l$ 个到第 $r$ 个数的和，也就是输出： $\sum_{i=l}^{r}a_i$ 因为这个结果可能会很大，所以你只需要输出结果 $\bmod \space p$ 的值即可。

无

无

【数据范围】 对于 $0\%$ 的测试点，和样例一模一样； 对于另外 $10\%$ 的测试点，没有修改； 对于另外 $20\%$ 的测试点，每次修改操作只会修改一个位置（也就是 $l = r$ ），并且每个位置至多被修改一次； • 对于另外 $10\%$ 的测试点， $p = 2$； 对于另外 $10\%$ 的测试点， $p = 3$； 对于另外 $10\%$ 的测试点， $p = 4$； 对于另外 $20\%$ 的测试点， $1\le n,m \le 100$； 对于 $100\%$ 的测试点， $1\le n,m \le 5\times 10^4$，$1 \le p \le 10^8$，$0< c < p$，$0 \le a_i < p$。