시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
10 초 | 512 MB | 54 | 28 | 22 | 46.809% |
Assuming people numbered from \(1\) to \(2n\) are assigned to two teams of size \(n\) using the following non-deterministic procedure, find the probability that all people from the set \(A^i = \{a^i_1, a^i_2, \dots , a^i_{k_i}\}\) end up on the same team, for each of the given sets \(A^1, A^2, \dots , A^m\), and display it modulo 998 244 353:
The first line contains two integers \(n\) and \(m\) (\(2 \le n \le 10^5; 1 \le m \le 10^5\)).
The \(i\)-th of the next \(m\) lines describes set \(A^i\) and contains an integer \(k_i\) (\(2 \le k_i \le n\)), followed by \(k_i\) integers \(a^i_1, a^i_2, \dots , a^i_{k_i}\) (\(1 \le a^i_1 < a^i_2 < \dots < a^i_{k_i} \le 2n\)).
The sum of \(k_i\) does not exceed \(2 \cdot 10^5\).
For each \(i\) from \(1\) to \(m\), display the probability that all people from the set \(A^i\) end up on the same team.
It can be shown that any sought probability can be represented as an irreducible fraction \(\frac{p}{q}\) such that \(q \not\equiv 0 \mod{998 244 353}\). Then, there exists a unique integer \(r\) such that \(r \cdot q \equiv p \mod {998 244 353}\) and \(0 \le r < 998 244 353\), so display this \(r\).
2 6 2 1 2 2 1 3 2 1 4 2 2 3 2 2 4 2 3 4
499122177 748683265 748683265 748683265 748683265 499122177
3 5 3 2 3 5 2 2 4 2 5 6 3 1 4 6 2 2 5
935854081 623902721 374341633 935854081 686292993
In the first test case, people 1 and 2 (and people 3 and 4) end up on the same team with probability \(\frac{1}{2}\). For any other pair the probability is \(\frac{1}{4}\).