P5390 [Cnoi2019] Math Homework

Gensokyo, the Spring Festival, and lights in every home. Teacher Kamishirasawa Keine would of course not miss such a good chance... and assigned homework.

Now Cirno has homework for $T$ days. The homework for each day can be represented by an ordered pair $(n, V)$, where $n$ is the size of the set, and $V$ is a set of size $n$. Now Cirno needs to compute the sum of the XOR values over all subsets of $V$. The answer should be taken modulo $998\,244\,353$. Formally: $$ \text{ans}\equiv \sum_{S \subseteq V} \mathop{\bigoplus}\limits_{ s \in S } s \pmod {998\,244\,353} $$

The first line contains an integer $T$. The following $T$ lines each contain an ordered pair $(n, V)$.

Output $T$ lines, each containing one integer representing the answer.

- Subtask 1 (17 pts): $T, n \le 8$. - Subtask 2 (22 pts): $T, n \le 100$. - Subtask 3 (61 pts): $T, n \le 3\times 10^6$. For $100\%$ of the testdata, $\sum |V| \le 3 \times 10^6, 0 \le p \le 10^9$. Translated by ChatGPT 5