← 返回题目列表

AtCoder · KeioPC2025_o

O. 三个约束

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

配点 : 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) 不存在。