配点 : 100 点
問題文
非負整数 x, y, z ,一组满足以下所有条件的非负整数: (a,b,c) 的数量 我们将其表示为 f(x, y, z) 。
- a \ \mathrm{AND} \ b \ \mathrm{AND} \ c = x
- a \ \mathrm{OR} \ b \ \mathrm{OR} \ c = y
- a + b + c = z
这里 表示 a \ \mathrm{AND} \ b 是 它仅由 a 和 b 的按位与, 表示a \ \mathrm{OR} \ b 是 它仅由 a 和 b 的按位逻辑和。
正整数 N, M 和
长度由 0, 1, ? 组成
给出了 N 字符串
给出 X,Y,Z 。
将
X 的 ? 是 0 或 1 替换为得到的字符串 2 解释为基本整数的所有可能整数的集合是 S_X 对于Y 以同样的方式定义 S_Y 、 Z 以同样的方式定义 S_Z 。
请解决以下有关
k = 0, 1, \ldots, M-1 的问题。 满足
- x \in S_X, y \in S_Y, z \in S_Z 的整数 3 津美 (x, y, z) 和 判断是否存在满足f(x, y, z) \equiv k \pmod{M} 的情况。 您将获得
T 测试用例,因此请解决每个测试用例。
制約
- 1 \leq T \leq 3000
- 1 \leq N \leq 3000
- 1 \leq M \leq 10^6
- X, Y, Z 是
它仅由
0,1,?组成 给出了 N 字符串 给出 - 在所有测试用例中 N 的总和是 {3000} 以下
- 在所有测试用例中 M 的总和是 10^6 以下
- N,M 是一个整数
入力
输入将以以下形式从标准输入给出。
T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T
每个测试用例均按以下格式给出。
N\ M X Y Z
出力
T 行。
输出i 在线 \mathrm{case}_i ,
最大的使得k = 0, 1, \ldots, M-1 按顺序 f(x, y, z) \equiv k \pmod{M} 纳鲁
如果 (x,y,z) 存在 1 ,否则
对于第 0 。
入力例 1
3 3 5 0?1 ?01 ?11 5 7 ?0??? ?0?1? 01?10 10 10 0000000000 0000000000 0000000000
出力例 1
11010 1011001 0100000000
1 个测试用例,S_x = \lbrace 1,3 \rbrace , S_y = \lbrace 1,5 \rbrace , S_z = \lbrace 3,7 \rbrace 。 k = 0,1,3 , 最大的使得
-
f(3, 1, 3) \equiv 0 \pmod{M} : 满足条件 (a,b,c) 对不存在。 满足
-
f(1, 1, 3) \equiv 1 \pmod{M} : 满足条件 (a,b,c) 是 它仅由 (1,1,1) 的 1 一。 请注意,无法创建
-
f(1, 5, 7) \equiv 3 \pmod{M} : 满足条件 (a,b,c) 是 它仅由 (1,1,5) , (1,5,1) , (5,1,1) 的 3 一。 请注意,无法创建
等条件 您可以看到 (x,y,z) 存在。 从而满足
一方、 k = 2,4 的条件。 (x,y,z) 不存在。