← 返回题目列表

AtCoder · abc407_d

G. 多米诺骨牌覆盖异或

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

分数: 425 点

问题陈述

有一个网格 H 行和 W 列。 让 (i,j) 表示位于 i从顶部算起的第行 (1\leq i\leq H) 和 j左起第 列 (1\leq j\leq W).

细胞 (i,j)\ (1\leq i\leq H,1\leq j\leq W) 有一个非负整数 A_{i,j} 。

让我们在网格上放置零个或多个多米诺骨牌。 多米诺骨牌覆盖两个相邻的单元格,即以下对之一:

  • 细胞 (i,j) 和 (i,j+1) 为 1\leq i\leq H,1\leq j\lt W;
  • 细胞 (i,j) 和 (i+1,j) 为 1\leq i\lt H,1\leq j\leq W.

任何单元格都不能被多于一张多米诺骨牌覆盖。

对于多米诺骨牌的放置,定义其 分数 游戏的 作为单元格中写入的所有整数的按位异或 不 被任何多米诺骨牌覆盖。

找到可能的最大分数。

什么是按位异或?

对于非负整数 A 和 B,它们的按位异或 A \oplus B 定义如下:

  • 在二进制中, 2^k 位(k \ge 0)的 A \oplus B is 1 如果恰好是以下之一 A 和 B 有 1 在那一点上,并且 0 否则。
例如, 3 \oplus 5 = 6 (二进制, 011 \oplus 101 = 110).
对于 k 非负整数 p_1, p_2, p_3, \dots, p_k,它们的按位异或是 (\dots ((p_1 \oplus p_2) \oplus p_3) \oplus \dots \oplus p_k),可以证明与操作数的顺序无关。

约束

  • 1 \le H
  • 1 \le W
  • HW \le 20
  • 0 \le A_{i,j} < 2^{60} (1 \le i \le H,\ 1 \le j \le W)
  • 所有输入值均为整数。

输入

输入由标准输入按以下格式给出:

H W
A _ {1,1} A _ {1,2} \ldots A _ {1,W}
A _ {2,1} A _ {2,2} \ldots A _ {2,W}
\vdots
A _ {H,1} A _ {H,2} \ldots A _ {H,W}

输出

输出答案。


示例输入 1

3 4
1 2 3 8
4 0 7 10
5 2 4 2

示例输出 1

15

网格如下:

例如,以下位置的得分为 15.

没有任何展示位置得分达到 16 或更高,因此输出 15.


示例输入 2

1 11
1 2 4 8 16 32 64 128 256 512 1024

示例输出 2

2047

您也可以选择不放置多米诺骨牌。


示例输入 3

4 5
74832 16944 58683 32965 97236
52995 43262 51959 40883 58715
13846 24919 65627 11492 63264
29966 98452 75577 40415 77202

示例输出 3

131067