/ Vijos / 题库 /

xor-sigma

xor-sigma

描述

对于给定的n和m以及\(a_1, ..., a_n\),请你计算:

\(s = \sum_{i = 1}^{n} \max_{1 \leq j \leq \min \{ m, n - i + 1 \} } \{ a_i \oplus a_{i + 1} \oplus ... \oplus a_{ i + j - 1} \}\)

格式

输入格式

第1行为空格分隔的n和m。

第2行为空格分隔的\(a_1, ..., a_n\)。

输出格式

一个数字,为计算结果s(只保留低31位即可)。

样例1

样例输入1

10 5
1 2 3 4 5 6 7 8 9 10

样例输出1

92

限制

\( 1 \leq m \leq n \leq 5 \times 10^5 \)

\( \forall i \in [1, n], 1 \leq a_i \leq 2^{31} - 1 \)

时间

前三个测试点 1s

剩下的 2s

空间

384MiB

提示

Python Code

n, m = map(int, raw_input().split())
a = map(int, raw_input().split())

def xor(a, b):
    return a ^ b

s = sum(max(reduce(xor, a[i:i + j + 1]) for j in range(min(m, n - i + 1))) for i in range(n))
print(s & 0x7fffffff)

信息

ID
2001
难度
7
分类
Trie树 点击显示
标签
(无)
递交数
133
已通过
26
通过率
20%
被复制
3
上传者

相关

在下列训练计划中:

RP++分类题库