P13275 [NOI2025] 集合

set.cpp / 2 s / 512 MiB

小 X 有 $2^n$ 个数，编号为 $0$ 到 $2^n - 1$，第 $i$ ($0 \leq i < 2^n$) 个数为 $a_i$。 对于 $S \subseteq \{0, 1, \ldots, 2^n - 1\}$，定义 $f(S)$ 为集合 $S$ 中 **所有数的二进制按位与**。特别地，若 $S$ 为空集，则 $f(S) = 2^n - 1$。 定义两个 $\{0, 1, \ldots, 2^n - 1\}$ 的子集 $P, Q$（可以为空）构成的有序对 $(P, Q)$ 是 **特别的** 当且仅当 $P \cap Q = \varnothing$ 且 $f(P) = f(Q)$。定义有序对 $(P, Q)$ 的 **权值** 为 **编号** 包含在 $P \cup Q$ 内的所有数的乘积，即 $\prod_{i \in P \cup Q} a_i$。特别地，若 $P \cup Q = \varnothing$，则有序对 $(P, Q)$ 的权值为 $1$。 小 X 想要知道所有特别的有序对的权值之和，请你帮助他求出这个值。由于答案可能较大，你只需要求出答案对 $998,244,353$ 取模后的结果。

**本题包含多组测试数据。** 输入的第一行包含两个非负整数 $c, t$，分别表示测试点编号与测试数据组数。$c = 0$ 表示该测试点为样例。 接下来依次输入每组测试数据，对于每组测试数据： 第一行包含一个正整数 $n$，表示有 $2^n$ 个数。 第二行包含 $2^n$ 个非负整数 $a_0, \ldots, a_{2^n - 1}$。

对于每组测试数据，输出一行一个整数，表示所有特别的有序对的权值之和对 $998,244,353$ 取模后的结果。

**【样例 2】** 见选手目录下的 `set/set2.in` 与 `set/set2.ans`。 该样例满足测试点 2 的约束条件。 **【样例 3】** 见选手目录下的 `set/set3.in` 与 `set/set3.ans`。 该样例满足测试点 3 的约束条件。 **【样例 4】** 见选手目录下的 `set/set4.in` 与 `set/set4.ans`。 该样例满足测试点 9 的约束条件。 **【数据范围】** 对于所有测试数据，保证： - $1 \leq t \leq 3$; - $2 \leq n \leq 20$; - 对于所有 $0 \leq i < 2^n$，均有 $0 \leq a_i < 998,244,353$。 ::cute-table{tuack} | 测试点编号 | $n \leq$ | 特殊性质 | | :----------: | :------: | :------: | | $1$ | $4$ | B | | $2$ | ^ | 无 | | $3$ | $8$ | B | | $4$ | ^ | 无 | | $5$ | $10$ | B | | $6$ | ^ | 无 | | $7, 8$ | $12$ | B | | $9$ | ^ | 无 | | $10 \sim 12$ | $16$ | B | | $13, 14$ | ^ | 无 | | $15, 16$ | $20$ | AB | | $17, 18$ | ^ | A | | $19 \sim 21$ | ^ | B | | $22 \sim 25$ | ^ | 无 | 特殊性质 A: 保证至多存在 24 个 $i$ 满足 $a_i \neq 0$。 特殊性质 B: 保证对于所有 $0 \leq i < 2^n$，均有 $a_i \neq 998,244,352$。 附加文件来自于 [QOJ](https://qoj.ac/contest/2316/problem/13083)。