11252: [yosupo] Data Structure - Unionfind with Potential (Non-Commutative Group)
[Creator : ]
Description
There is an unknown sequence of $2 \times 2$ invertible matrices with integer components $(a_0, \ldots, a_{N - 1})$, process $Q$ queries.
- `$t_i$ = 0 $u_i$ $v_i$ $x_{0, 0}$ $x_{0, 1}$ $x_{1, 0}$ $x_{1, 1}$`: You are provided with information that $a_u \equiv a_v x \pmod {998244353}$, where $x$ is a $2 \times 2$ matrix with elements $x_{0, 0}, x_{0, 1}, x_{1, 0}, x_{1, 1}$. This information is valid if it does not contradict any previously given valid information. If this information is valid, output $1$; otherwise, output $0$.
- `$t_i$ = 1 $u_i$ $v_i$`: Based on the valid information provided so far, output the value of $a_v^{-1}a_u \bmod 998244353$ if it can be determined; otherwise, output $-1$.
- `$t_i$ = 0 $u_i$ $v_i$ $x_{0, 0}$ $x_{0, 1}$ $x_{1, 0}$ $x_{1, 1}$`: You are provided with information that $a_u \equiv a_v x \pmod {998244353}$, where $x$ is a $2 \times 2$ matrix with elements $x_{0, 0}, x_{0, 1}, x_{1, 0}, x_{1, 1}$. This information is valid if it does not contradict any previously given valid information. If this information is valid, output $1$; otherwise, output $0$.
- `$t_i$ = 1 $u_i$ $v_i$`: Based on the valid information provided so far, output the value of $a_v^{-1}a_u \bmod 998244353$ if it can be determined; otherwise, output $-1$.
Input
$N$ $Q$
$\textrm{Query}_0$
$\textrm{Query}_1$
:
$\textrm{Query}_{Q - 1}$
$\textrm{Query}_0$
$\textrm{Query}_1$
:
$\textrm{Query}_{Q - 1}$
Constraints
- $1 \leq N \leq 2\times 10^5$
- $1 \leq Q \leq2\times 10^5$
- $0 \leq u_i, v_i \lt N$
- $0 \leq x_{0, 0}, x_{0, 1}, x_{1, 0}, x_{1, 1} < 998244353$
- $x_{0, 0}x_{1, 1} - x_{0, 1}x_{1, 0} \equiv 1 \pmod 998244353$
- $1 \leq Q \leq2\times 10^5$
- $0 \leq u_i, v_i \lt N$
- $0 \leq x_{0, 0}, x_{0, 1}, x_{1, 0}, x_{1, 1} < 998244353$
- $x_{0, 0}x_{1, 1} - x_{0, 1}x_{1, 0} \equiv 1 \pmod 998244353$
Sample 1 Input
4 10
0 1 0 2 998244350 998244350 5
1 0 2
0 2 1 1 2 3 7
0 2 0 998244346 998244336 12 29
0 0 2 1 2 1 3
0 3 1 2 0 0 499122177
1 0 2
1 2 0
1 3 0
1 1 1
Sample 1 Output
1
-1
1
1
0
1
29 17 998244341 998244346
998244346 998244336 12 29
4 499122175 998244347 499122179
1 0 0 1