H. Multiple of Three Cycles
combinatorics; data structures; dp; dsu; math
An array \(a_1,\dots,a_n\) of length \(n\) is initially all blank. There are \(n\) updates where one entry of \(a\) is updated to some number, such that \(a\) becomes a permutation of \(1,2,\dots,n\) after all the updates.After each update, find the number of ways (modulo \(998\,244\,353\)) to fill in the remaining blank entries of \(a\) so that \(a\) becomes a permutation of \(1,2,\dots,n\) and all cycle lengths in \(a\) are multiples of \(3\).A permutation of \(1,2,\dots,n\) is an array of length \(n\) consisting of \(n\) distinct integers from \(1\) to \(n\) in arbitrary order. A cycle in a permutation \(a\) is a sequence of pairwise distinct integers \((i_1,\dots,i_k)\) such that \(i_2 = a_{i_1},i_3 = a_{i_2},\dots,i_k = a_{i_{k-1}},i_1 = a_{i_k}\). The length of this cycle is the number \(k\), which is a multiple of \(3\) if and only if \(k \equiv 0 \pmod 3\).
The first line contains a single integer \(n\) (\(3 \le n \le 3 \cdot 10^5\), \(n \equiv 0 \pmod 3\)).The \(i\)-th of the next \(n\) lines contains two integers \(x_i\) and \(y_i\), representing that the \(i\)-th update changes \(a_{x_i}\) to \(y_i\).It is guaranteed that \(x_1,\dots,x_n\) and \(y_1,\dots,y_n\) are permutations of \(1,2,\dots,n\), i.e. \(a\) becomes a permutation of \(1,2,\dots,n\) after all the updates.
Output \(n\) lines: the number of ways (modulo \(998\,244\,353\)) after the first \(1,2,\dots,n\) updates.
In the first sample, for example, after the \(3\)rd update the \(3\) ways to complete the permutation \(a = [4,\_,2,5,\_,\_]\) are as follows: \([4,1,2,5,6,3]\): The only cycle is \((1\,4\,5\,6\,3\,2)\), with length \(6\). \([4,6,2,5,1,3]\): The cycles are \((1\,4\,5)\) and \((2\,6\,3)\), with lengths \(3\) and \(3\). \([4,6,2,5,3,1]\): The only cycle is \((1\,4\,5\,3\,2\,6)\), with length \(6\). In the second sample, the first update creates a cycle of length \(1\), so there are no ways to make all cycle lengths a multiple of \(3\).