← 返回题目列表

Codeforces · 2226/F

F. 反转入侵

中文机器翻译题面 查看原题

有一个长度为$$$n$$$的数组$$$a$$$。最初,对于所有 $$$1 \le i \le n$$$,$$$a_i = 0$$$。

排列$$$^{\text{*}}$$$ $$$p$$$ 据说是 有效 每个 $$$1 \le i \le n$$$ 满足以下条件的 if 至少一个 所选字符的 :

  • $$$a_i = 0$$$。
  • $$$\gcd(p_i, n) = a_i$$$。

您必须处理 $$$q$$$ 查询。在每个查询中,都会给您两个整数 $$$i$$$ 和 $$$x$$$,并且您必须通过设置 $$$a_i:= x$$$ 来更新数组 坚持不懈.

保证每次查询时$$$a_i = 0$$$,并且保证$$$x$$$ 除$$$n$$$。

执行每个查询后,输出所有查询的反转次数$$$^{\text{†}}$$$ 的总和 有效 每个 $$$1 \le i \le n$$$ 满足以下条件的 排列。由于答案可能非常大,请以 $$$998\,244\,353$$$ 为模报告它们。

$$$^{\text{*}}$$$长度$$$m$$$的排列是一个由从$$$1$$$到$$$m$$$以任意顺序的$$$m$$$不同整数组成的数组。例如,$$$[2,3,1,5,4]$$$是一个排列,但$$$[1,2,2]$$$不是排列($$$2$$$在数组中出现了两次),$$$[1,3,4]$$$也不是排列($$$m=3$$$但数组中有一个$$$4$$$)。

$$$^{\text{†}}$$$排列 $$$p$$$ 中的反转是一对索引 $$$(i, j)$$$,使得 $$$i \lt j$$$ 和 $$$p_i \gt p_j$$$。例如,排列 $$$[4, 1, 3, 2]$$$ 具有 $$$4$$$ 反转:$$$(1, 2)$$$、$$$(1, 3)$$$、$$$(1, 4)$$$ 和 $$$(3, 4)$$$。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。

每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$q$$$ ($$$1 \le n \le 2 \cdot 10^6$$$; $$$1 \le q \le \min(n, 10^6)$$$) — 数组 $$$a$$$ 的长度和查询数量。

接下来的 $$$q$$$ 行包含两个整数 $$$i$$$ 和 $$$x$$$ ($$$1 \le i \le n$$$; $$$1 \le x \le n$$$)。

保证每次查询时$$$a_i = 0$$$,并且保证$$$x$$$ 除$$$n$$$。

保证所有测试用例的$$$n$$$总和不超过$$$2 \cdot 10^6$$$,所有测试用例的$$$q$$$总和不超过$$$10^6$$$。

输出

对于每个测试用例,打印 $$$q$$$ 整数 - 处理每个查询后所有有效排列的反转总数。

由于答案可能很大,请以 $$$998\,244\,353$$$ 为模打印它们。

示例

输入
复制

3
3 2
2 3
3 3
9 3
6 3
7 1
3 3
100 7
67 4
41 25
69 1
99 1
50 100
100 2
9 10

输出
复制

3
0
1461600
1114560
156960
207622048
432575995
443345156
499213668
665624940
770601684
223944735

注意

对于第一个测试用例,最初 $$$a = [0, 0, 0]$$$。

第一次查询后,$$$a = [0, 3, 0]$$$。有效排列为 $$$[1, 3, 2]$$$ 和 $$$[2, 3, 1]$$$。反转总数为 $$$1 + 2 = 3$$$。

第二次查询后,$$$a = [0, 3, 3]$$$。没有有效的排列。