← 返回题目列表

Codeforces · 1554/B

B. 科布

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

给你 $$$n$$$ 整数 $$$a_1、a_2、\ldots、a_n$$$ 和整数 $$$k$$$。求 $$$i \cdot j - k \cdot (a_i | a_j)$$$ 在所有 $$$(i, j)$$$ 且 $$$1 \le i < j \le n$$$ 的整数对上的最大值。这里,$$$|$$$ 是按位或运算符。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10\,000$$$) — 测试用例的数量。

每个测试用例的第一行包含两个整数 $$$n$$$ ($$$2 \le n \le 10^5$$$) 和 $$$k$$$ ($$$1 \le k \le \min(n, 100)$$$)。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i \le n$$$)。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$3 \cdot 10^5$$$。

输出

对于每个测试用例,打印一个整数 - $$$i \cdot j - k \cdot (a_i | a_j)$$$ 的最大可能值。

示例

输入 #1

4
3 3
1 1 3
2 2
1 2
4 3
0 1 2 3
6 6
3 2 0 0 5 6

输出 #1

-1
-4
3
12

注意

设 $$$f(i, j) = i \cdot j - k \cdot (a_i | a_j)$$$。

在第一个测试用例中,

- $$$f(1, 2) = 1 \cdot 2 - k \cdot (a_1 | a_2) = 2 - 3 \cdot (1 | 1) = -1$$$。
- $$$f(1, 3) = 1 \cdot 3 - k \cdot (a_1 | a_3) = 3 - 3 \cdot (1 | 3) = -6$$$。
- $$$f(2, 3) = 2 \cdot 3 - k \cdot (a_2 | a_3) = 6 - 3 \cdot (1 | 3) = -3$$$。

因此最大值为 $$$f(1, 2) = -1$$$。

在第四个测试用例中,最大值为 $$$f(3, 4) = 12$$$。