← 返回题目列表

Codeforces · 1844/H

H. 三个周期的倍数

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

长度为 $$$n$$$ 的数组 $$$a_1,\dots,a_n$$$ 最初全为空白。有 $$$n$$$ 更新,其中 $$$a$$$ 的一个条目被更新为某个数字,使得 $$$a$$$ 在所有更新后变成 $$$1,2,\dots,n$$$ 的排列。

每次更新后,找出填充 $$$a$$$ 剩余空白条目的方法数(模 $$$998\,244\,353$$$),使 $$$a$$$ 成为 $$$1,2,\dots,n$$$ 的排列,并且 $$$a$$$ 中的所有循环长度都是 $$$3$$$ 的倍数。

$$$1,2,\dots,n$$$ 的排列是一个长度为 $$$n$$$ 的数组,由从 $$$1$$$ 到 $$$n$$$ 的 $$$n$$$ 个不同的整数以任意顺序组成。排列 $$$a$$$ 中的循环是成对不同整数 $$$(i_1,\dots,i_k)$$$ 的序列,使得 $$$i_2 = a_{i_1},i_3 = a_{i_2},\dots,i_k = a_{i_{k-1}},i_1 = a_{i_k}$$$。这个循环的长度是数字$$$k$$$,它是$$$3$$$的倍数当且仅当$$$k \equiv 0 \pmod 3$$$。

输入

第一行包含一个整数 $$$n$$$ ($$$3 \le n \le 3 \cdot 10^5$$$, $$$n \equiv 0 \pmod 3$$$)。

接下来的$$$n$$$行的第$$$i$$$行包含两个整数$$$x_i$$$和$$$y_i$$$,表示第$$$i$$$更新将$$$a_{x_i}$$$更改为$$$y_i$$$。

保证 $$$x_1,\dots,x_n$$$ 和 $$$y_1,\dots,y_n$$$ 是 $$$1,2,\dots,n$$$ 的排列,即 $$$a$$$ 在所有更新后变成 $$$1,2,\dots,n$$$ 的排列。

输出

输出 $$$n$$$ 行:第一个 $$$1,2,\dots,n$$$ 更新后的路数(模 $$$998\,244\,353$$$)。

示例

输入 #1

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

输出 #1

32
8
3
2
1
1

输入 #2

3
1 1
2 3
3 2

输出 #2

0
0
0

输入 #3

18
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
15 16
16 17
17 18
18 1

输出 #3

671571067
353924552
521242461
678960117
896896000
68992000
6272000
627200
62720
7840
1120
160
32
8
2
1
1
1

注意

在第一个示例中,例如,在 $$$3$$$rd 更新后,$$$3$$$ 完成排列 $$$a = [4,\_,2,5,\_,\_]$$$ 的方法如下:

- $$$[4,1,2,5,6,3]$$$:唯一的循环是$$$(1\,4\,5\,6\,3\,2)$$$,长度为$$$6$$$。
- $$$[4,6,2,5,1,3]$$$:周期为 $$$(1\,4\,5)$$$ 和 $$$(2\,6\,3)$$$,长度为 $$$3$$$ 和 $$$3$$$。
- $$$[4,6,2,5,3,1]$$$:唯一的循环是$$$(1\,4\,5\,3\,2\,6)$$$,长度为$$$6$$$。

在第二个示例中,第一次更新创建了一个长度为 $$$1$$$ 的循环,因此无法使所有循环长度成为 $$$3$$$ 的倍数。