AT_abc291_g [ABC291G] OR Sum

题目描述

给定长度为 $N$ 的数列 $A=(A_0,A_1,\ldots,A_{N-1})$ 和 $B=(B_0,B_1,\ldots,B_{N-1})$。

此外，高桥君可以对数列 $A$ 任意次（可以为 $0$ 次）进行如下操作：

• 将 $A$ 向左循环移动一位，即用 $A'_i = A_{(i+1)\%N}$ 定义的新数列 $A'$ 替换 $A$。其中，$x\%N$ 表示 $x$ 除以 $N$ 的余数。

高桥君的目标是最大化 $\displaystyle\sum_{i=0}^{N-1}(A_i|B_i)$。其中，$x|y$ 表示 $x$ 和 $y$ 的按位或（bitwise OR）运算。

请你求出 $\displaystyle\sum_{i=0}^{N-1}(A_i|B_i)$ 的最大可能值。

按位或（bitwise OR）是对每一位的 $0$ 或 $1$ 进行如下表所示的运算：

| $x$ | $y$ | $x|y$ | |-----|-----|-------| | 0 | 0 | 0 | | 0 | 1 | 1 | | 1 | 0 | 1 | | 1 | 1 | 1 |

按位或的结果是：只要 $x$ 或 $y$ 的某一位至少有一个为 $1$，结果的该位就是 $1$；只有两位都为 $0$ 时结果才为 $0$。

具体例子

0110 | 0101 = 0111

输入格式

输入以如下格式从标准输入给出。

$N$ $A_0$ $A_1$ $\ldots$ $A_{N-1}$ $B_0$ $B_1$ $\ldots$ $B_{N-1}$

输出格式

输出 $\displaystyle\sum_{i=0}^{N-1}(A_i|B_i)$ 的最大可能值。

输入输出样例 #1

输入 #1

3
0 1 3
0 2 3

输出 #1

8

输入输出样例 #2

输入 #2

5
1 6 1 4 3
0 6 4 0 1

输出 #2

23

说明/提示

限制条件

• $2 \leq N \leq 5\times 10^5$
• $0 \leq A_i, B_i \leq 31$
• 输入均为整数

样例解释 1

当高桥君一次操作都不进行时，$A$ 仍为 $(0,1,3)$，此时 $\displaystyle\sum_{i=0}^{N-1}(A_i|B_i) = (0|0) + (1|2) + (3|3) = 0 + 3 + 3 = 6$。

当高桥君进行 $1$ 次操作时，$A=(1,3,0)$，此时 $\displaystyle\sum_{i=0}^{N-1}(A_i|B_i) = (1|0)+(3|2)+(0|3)=1+3+3=7$。

当高桥君进行 $2$ 次操作时，$A=(3,0,1)$，此时 $\displaystyle\sum_{i=0}^{N-1}(A_i|B_i) = (3|0)+(0|2)+(1|3)=3+2+3=8$。

进行 $3$ 次及以上操作时，$A$ 会回到上述某种状态，因此 $\displaystyle\sum_{i=0}^{N-1}(A_i|B_i)$ 的最大值为 $8$，输出 $8$。

样例解释 2

最大值出现在高桥君进行 $3$ 次操作时，此时 $A=(4,3,1,6,1)$，$\displaystyle\sum_{i=0}^{N-1}(A_i|B_i) = (4|0)+(3|6)+(1|4)+(6|0)+(1|1)=4+7+5+6+1=23$。

由 ChatGPT 4.1 翻译