#K. [Cnoi2019] 数学作业

远端评测题

1000ms

125MiB

该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目背景

幻想乡，春节，万家灯火。

Kamishirasawa Keine 老师自然不会放过这么好的机会，，，布置作业。

现在 Cirno 手上有着 $T$ 天的作业，每天的作业可以用一个二元组 $( n, V )$ 表示，其中 $n$ 表示集合的大小， $V$ 表示大小为 $n$ 的集合. 现在，Cirno 需要求出的是 $V$ 的所有子集的异或和的和，答案对 $998\,244\,353$ 取模。

形式化地：

$$\text{ans}\equiv \sum_{S \subseteq V} \mathop{\bigoplus}\limits_{ s \in S } s \pmod {998\,244\,353} $$

第一行，一个整数 $T$ 。

以下 $T$ 行，每行一个二元组 $( n, V )$ 。

$T$ 行，每行一个整数，表示答案。

1
3 1 2 3

对于 $100\%$ 的数据， $\sum |V| \le 3 \times 10^6, 0 \le p \le 10^9$ 。