P6016 [CSGRound3] Trip

The school organized a summer trip, and registration will close on day $T$. There are $n$ students. Student $i$ has $a_i$ friends. The friendship relation is directed. In other words, if student Z has student Y as a friend, it does not mean student Y must have student Z as a friend. Also, a student may be their own friend. On day $0$, each student decides whether to join the trip. Student $i$ decides to join with probability $p_i$, and decides not to join with probability $1-p_i$. During the next $T$ days, each student will decide again whether to join. On that day, student $i$ decides to join if and only if at least one of their friends decided to join on the previous day; otherwise, they do not join. You need to compute the expected number of students who join the trip. Output the answer modulo $998244353$.

The first line contains two integers $n, T$, as described above. The next $n$ lines each start with two integers $p_i, a_i$. Here, $p_i$ is the probability (under modulo $998244353$) that student $i$ decides to join on day $0$, and $a_i$ is the number of their friends. Then follow $a_i$ integers indicating their friends.

Output one integer, the answer modulo $998244353$.

**[Sample 1 Explanation]** | Day | Probability that the first student goes | Probability that the second student goes | Probability that the third student goes | | :--: | :------------------------------------: | :-------------------------------------: | :------------------------------------: | | $0$ | $1$ | $0$ | $\frac 12$ | | $1$ | $\frac 12 $ | $\frac 12 $ | $0$ | --- **[Constraints]** **This problem uses bundled testdata.** - Subtask 1 (3 points): $T = 0$. - Subtask 2 (14 points): $T = 1$. - Subtask 3 (33 points): $n \le 10$. - Subtask 4 (20 points): $T \le 5 \times 10^3$. - Subtask 5 (15 points): $n \le 100$. - Subtask 6 (15 points): No special constraints. For $100\%$ of the testdata: $1 \le n \le 500$, $0 \le T \le 10^9$, $0 \le p_i < 998244353$, $0 \le a_i \le n$, and all friends are distinct. Translated by ChatGPT 5