xor-sigma
测试数据来自 system/2001
描述
对于给定的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)