CF1844H Multiple of Three Cycles

一个长度为 $n$ 的数组 $a_1,\dots,a_n$ 初始为空。接下来有 $n$ 次操作，每次将 $a$ 中的一个位置赋值为某个数，最终 $a$ 会变成 $1,2,\dots,n$ 的一个排列。 每次操作后，求有多少种方案（对 $998\,244\,353$ 取模）填补剩余的空白位置，使得 $a$ 变成 $1,2,\dots,n$ 的一个排列，并且所有置换的环长度都是 $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$，当且仅当 $k \equiv 0 \pmod 3$ 时，$k$ 是 $3$ 的倍数。

第一行包含一个整数 $n$（$3 \le n \le 3 \cdot 10^5$，$n \equiv 0 \pmod 3$）。 接下来的 $n$ 行，每行包含两个整数 $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$ 行，第 $i$ 行表示前 $i$ 次操作后，填补剩余空白位置使 $a$ 满足条件的方案数，对 $998\,244\,353$ 取模。

在第一个样例中，例如第 $3$ 次操作后，$a = [4,\_,2,5,\_,\_]$，有 $3$ 种方式补全排列： - $[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$ 的倍数。 由 ChatGPT 4.1 翻译