← 返回题目列表

AtCoder · yahoo_procon2018_qual_d

D. 异或异或

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

配点 : 800 点

問題文

斯努克君在黑板上 2 两个不同的整数 X,Y 和 按字典顺序比较 K 行 K 画了列的格子。 接着,斯努克君在格子的 i 行 j 列写了整数 A_{i,j} 。

斯努克君用这个,长度 K 序列 使用 a 满足以下条件时 a 该值应乘以 良好的数列 我们称之为 他决定称之为。

  • 条件:1 \leq i,j \leq K 对满足该条件的任何 (i,j) ,以下成立
    • a_i xor a_j xor X 或 通过替换为 a_i xor a_j xor Y 是 在 A_{i,j} 匹配。
    • 但是, 运算前设定中包含的xor 表示按位异或。

潜伏 我有 N 个整数。i 个整数是 x_i 。 S努克君打算从这些 N 个数字中选择 K 个并排列,制作长度为 K 的数列。 在努克君可以制作的数列中,有多少是好的数列呢?模 10^{9} + 7 找到它。

请注意,一种数列的制作方法可能有多种,但如果最终得到的数列相同,则不区分。 详情请参见样例 1 。

制約

  • 1 \leq N \leq 2048
  • 1 \leq K \leq {\rm min}(1024,N)
  • 0 \leq X,Y,x_i, A_{i,j} < 2048
  • X \neq Y
  • 给出的所有输入均为整数

入力

输入是按以下格式从标准输入给出的。

N K X Y
x_{1} ... x_{N}
A_{1,1} ... A_{1,K}
:
A_{K,1} ... A_{K,K}

出力

打印答案。 来自


入力例 1

6 3 1 0
0 8 1 2 15 8
1 2 8
2 0 10
8 10 1

出力例 1

2
  • 。 作为答案可能出现的数列是 (0,2,8) 和 按字典顺序比较 (1,2,8) 可以得到第 2 是的。 请注意,我们正在寻找除以
  • (0,2,8) ,按照 2 种方式选择并排列数字,但请注意不区分它们。 无论是什么样的数列,都不会满足条件。

入力例 2

2 2 0 4
0 1
8 16
110 12

出力例 2

0
  • 无论是哪种数列,都无法满足条件。

入力例 3

35 4 11 1
23 2 17 16 22 22 6 0 0 15 16 5 12 21 0 9 17 0 2 26 22 19 6 16 13 7 26 8 22 29 26 13 8 32 14
1 0 15 31
0 11 14 20
5 4 1 17
21 20 27 1

出力例 3

26