← 返回题目列表

Codeforces · 2233/E1

E1. 排列传输(简易版)

中文机器翻译题面 查看原题

这是问题的简单版本。在此版本中,$$$n$$$ 的上限以及所有测试用例的 $$$n$$$ 总和为 $$$2\,000$$$;此外,测试用例的最大数量为$$$200$$$。

存在大小为 $$$n$$$$$$^{\text{*}}$$$ 的排列 $$$p$$$。

它是通过通信通道发送的,如下所示:首先,排列中每个数字 $$$p_{i}$$$ 的所有 $$$0$$$ 位都作为 $$$n$$$ 字符的字符串发送 0 和/或 1;然后 $$$1$$$-st 位以相同的格式发送,依此类推,直到数字 $$$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 200$$$)。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 2\,000$$$)。

每个测试用例的接下来的 $$$\lceil\log_2 (n + 1) \rceil$$$ 行包含按接收顺序传输的数据。每行由 $$$n$$$ 字符 $$$0$$$ 和/或 $$$1$$$ 组成。

附加输入限制:

  • 所有测试用例的 $$$n$$$ 总和不超过 $$$2\,000$$$。

输出

对于每个测试用例,打印一个整数 - 问题的答案。

示例

输入
复制

6
1
1
4
1010
0001
0110
7
0101011
1100101
0110110
5
10110
01100
11001
6
001011
111000
000000
7
1100001
1100001
1100011

输出
复制

1
2
6
0
0
0

注意

在第一个示例中,只能有一个排列,$$$p = [1]$$$。

在第二个示例中,有 $$$2$$$ 可能的变体:$$$[1, 2, 3, 4]$$$ 和 $$$[2, 1, 3, 4]$$$。

在第四个示例中,没有合适的原始排列。