P16107 [ICPC 2019 NAIPC] XOR Sequences

假设给定两个整数 $m$ 和 $n$。同时还给定一个包含 $n$ 个互不相同整数的列表 $x_1, x_2, \dots, x_n$，满足 $0 \leq x_i \leq 2^m - 1$。对于每个 $0$ 到 $2^m - 1$ 之间的数 $y$，你找到了数 $p_y$，使得 $x_{p_y}$ 与 $y$ 的按位异或值最大。也就是说，对于所有 $i = 1..n$，$i \ne p_y$，均有 $y \oplus x_{p_y} > y \oplus x_i$（$\oplus$ 表示按位异或）。 现在考虑逆向问题。给定 $m$、$n$ 以及序列 $p_0, p_1, \dots, p_{2^m - 1}$，请统计有多少个互不相同的整数序列 $x_1, x_2, \dots, x_n$ 能够通过上述算法生成给定的 $p$ 序列。如果两个 $x$ 序列存在某个下标 $i$ 使得 $x_i$ 不同，则认为它们是不同的。输出该计数对 $10^9 + 7$ 取模的结果。

每个测试用例的第一行包含两个空格分隔的整数 $m$（$0 \leq m \leq 16$）和 $n$（$1 \leq n \leq 2^m$），其中 $2^m$ 是 $p$ 序列的长度，$n$ 是 $x$ 序列的长度。 接下来的 $2^m$ 行，每行包含一个整数 $p$（$1 \leq p \leq n$）。这些是按顺序给出的序列 $p_0, p_1, \dots, p_{2^m - 1}$ 的值。$1$ 到 $n$ 之间的每个整数至少出现一次。

输出一个整数，表示能够通过上述算法生成给定 $p$ 序列的序列 $x_1, x_2, \dots, x_n$ 的数量，对 $10^9 + 7$ 取模。

翻译由 DeepSeek V3.2 完成