UOJ Logo Universal Online Judge

UOJ

#182. 【UR #12】a^-1 + b problem

统计

在你的帮助下,跳蚤国王终于打开了最后一间房间的大门。然而,picks 博士和他的猴子们早已通过地道逃跑了。万幸的是,因为阿姆斯特朗回旋加速喷气式阿姆斯特朗炮本身太过笨重,无法从地道中运走,所以还被静静的停放在房间的正中央。

拥有了征服世界的力量,跳蚤国王感觉非常一颗赛艇。为了试验这个传说中的武器的威力,跳蚤国王让士兵们把炮口对准空无一人的实验室开炮。

然而,事情总是没有这么顺利。片刻之后,一个士兵匆匆跑到跳蚤国王身前:“报!picks 博士给它设置了保险!但是我们根本不知道解除方法!”

经过研究,跳蚤国王发现,picks 博士所设置的保险措施可以简化为这样一个问题:

首先炮身的屏幕上显示了 $n$ 个数,接着在模 $998244353(7\times 17 \times 2^{23}+1$,一个质数$)$ 意义下,给出了 $m$ 条指令,每一条指令都是下列两种之一:

  1. 所有数加上某一个数。
  2. 所有数都变成原来的逆元。(保证这时所有数的逆元都存在)

在每个指令完成之后,你要回答当前屏幕上所有数的和。

跳蚤国王思索了片刻,发现这个问题奥妙重重,于是他让你——这附近最著名的民间科学家来帮他解决这个难题。

输入格式

第一行两个正整数 $n, m$,含义如题意所述。

第二行$n$个数,表示屏幕上最初显示的 $n$ 个数。

接下来$m$行,表示 $m$ 条指令,第 $i$ 行第一个数$ t_i $表示第 $i$ 个操作的类型。

若 $t_i = 1$ 则接下来有一个整数 $x_i$,表示给所有数都加上 $x_i$。

若 $t_i = 2$ 则表示将所有数都变成原来的逆元。

输出格式

输出$m$行,第$i$行一个整数表示第$i$条指令之后当前屏幕上每个数的和。

样例一

input

5 5
1 2 3 4 5
1 1
2
1 1
2
2

output

20
349385525
349385530
292342993
349385530

explanation

执行每个指令后的数列分别如下:

2 3 4 5 6

499122177 332748118 748683265 598946612 166374059

499122178 332748119 748683266 598946613 166374060

665496236 249561089 399297742 831870295 142606337

499122178 332748119 748683266 598946613 166374060

样例二

见样例数据下载。这组数据符合1号测试点的限制与约定。

样例三

见样例数据下载。这组数据符合3号测试点的限制与约定。

限制与约定

测试点编号限制与约定
1$n, m \leq 1000$
2$n \leq 100000$, $m \leq 60000$, $t_i = 1$
3$n, m \leq 10000$
4$n, m \leq 20000$
5$n, m \leq 30000$
6$n \leq 100000$, $m \leq 30000$
7
8$n \leq 100000$, $m \leq 60000$
9
10

对于所有数据,$1 \le n \le 100000$, $1 \le m \le 60000$, $t_i \in \{1, 2\}$,其他所有数均为区间$[1, 998244352]$中的整数。

保证任何时候每个数的逆元均存在。

时间限制:$4\texttt{s}$

空间限制:$256\texttt{MB}$

下载

样例数据下载

后记

在你的帮助下,保险被成功解除,并进入了发射倒计时状态。

“5,4,3,2,1,发射!”然而,就在所有人屏息以待,想要见证它超强的破坏力的时候,预想当中的炮击声并没有出现——炮口上弹出了一大簇鲜花!

这时从旁边的地(窨)道(井)口(盖)下,跳出来了一个 picks 博士,他手上举着一支鲜花并大喊:“愚人节快乐!”

P.S. 跳蚤国的愚人节是2月28号!(一本正经的胡说八道ing)

嘿嘿嘿

从此跳蚤国王和 picks 博士过上了幸(没)福(羞)快(没)乐(臊)的生活(o(*////▽////*)q 好像剧情往奇怪的方向发展了)