CF2233E2 Permutation Transmission (Difficult Version)

这是该问题的困难版本。在本版本中，$n$ 的上限以及所有测试用例中 $n$ 的总和为 $2 \cdot 10^5$；此外，测试用例的最大数量为 $10^4$。 有一个长度为 $n$ 的排列 $p$ $^{\text{∗}}$。 它被通过如下的通信信道发送：首先，将排列中每个数 $p_{i}$ 的第 $0$ 位二进制比特拼成一个长度为 $n$ 的 $01$ 字符串发送；然后，同样方法发送第 $1$ 位比特……依次直到 $n$ 的最高有效二进制位。 例如，当 $p = [3, 1, 2, 4]$ 时，发送的三个字符串如下： 1. "1100"； 2. "1010"； 3. "0001"。 你收到了所有这些字符串，但它们关于每行对应第几比特的信息丢失了，也就是说，这些字符串的顺序被打乱。在上述例子中，字符串可能以 "1010"、"0001" 和 "1100" 的顺序到达。 你的任务是确定有多少种可能的原始排列 $p$ 被发送。有可能在传输过程中数据被损坏，这种情况下不存在合法的原排列 $p$。 $^{\text{∗}}$ 长度为 $n$ 的排列是一个长度为 $n$ 的数组，其中每个 $1$ 到 $n$ 间的整数恰好出现一次。

每组测试数据包含多个测试用例。第一行输入一个整数 $t$（$1 \le t \le 10^4$）。接下来是各个测试用例的描述。 每组测试用例的第一行输入一个整数 $n$（$1 \le n \le 2 \cdot 10^5$）。 接下来每组测试用例输入 $\lceil\log_2 (n + 1) \rceil$ 行，每行包含一个长度为 $n$ 的由 $0$ 和/或 $1$ 组成的字符串（收到的顺序已随机打乱）。 附加输入约束： - 所有测试用例中 $n$ 的总和不超过 $2 \cdot 10^{5}$。

对于每组测试用例，输出一个整数，表示符合条件的原排列个数。

在第一个示例中，只能有一个排列，即 $p = [1]$。 在第二个示例中，有 $2$ 种可能的排列：$[1, 2, 3, 4]$ 和 $[2, 1, 3, 4]$。 在第四个示例中，没有任何合适的原排列。 由 ChatGPT 5 翻译