把过去和现在的笔记记录也搬了过来，也算是给以后留个念想吧，想想一开始打acm就是图一乐，后来发现这游戏还挺上头的，也算是度过了一段电竞生涯（xs）
早些时候的笔记写的好中二，连我自己看着都羞耻。
不过，就喜欢这种羞耻的感觉。
收录的题目大部分是个人认为质量不错的题目，以DP为主，非DP的题目都用※进行了标识。
当然，有些题解思路本身也是源自其他人的，不过除非特殊标注，否则都是用的自己的代码。

题目大意：

CF1554B Cobb
恐怖的1700分B题，比D题还难，笑死

题目大意：给一个数组(1e5，数值范围小于等于n)，和一个k（<=min(n,100)），求ij-k(a[i]|a[j])，i,j为下标。

解：

首先n2是不行的，想办法找到a[i]|a[j]的规律和限制，实际上有个显而易见的尝试,min(a,b)<=a|b<=max(a,b)，如果我再成熟点的话应该足以发现，这种条件最适合的就是用来放缩。
原式中ij的数量级显然要比a[i]|a[j]更大，所以不妨假设原本最大的东西就是i=n-1,j=n时的结果，那么如果存在i,j，使得f(i,j)>=f(n-1,n)（这里f表示原式），那么显然max f(i,j)必须>=min f(n-1,n)，a[i]和a[j]的值是无规律的，换句话说可以随便设定，那么a[n-1]|a[n]取最大值时f(n-1,n)取到最小，这个最大值是2n（实际上没这么大，但是因为是放缩所以无所谓），也就是说f(n-1,n)的最小值是n(n-1)-2kn，那么f(i,j)的最大值是多少呢，当然是或值为0了（实际上也不可能这么小），这样我们就得到ij>=n(n-1)-2kn，j取的越大结果肯定越大吧，所以得到了in>=n(n-1-2k)，i>=n-1-2*k，这样的话复杂度瞬间缩小到了O(4k2)，k最大只有100，所以就过了。
只能说是梦回高中数学了属于是，位运算用于放缩的题目这是我碰到的第一个，不过还是狠狠地学习了。

代码

代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
#include <utility>
#include <vector>
#include <istream>
#include <map>
#include <cmath>
#include <stack>
#include <set>
#include <cstring>
#include <string>
#include <fstream>
#define ll long long
#define maxn 300005
#define mdl 1000000007
#define clr(a,n) for(int i=0;i<n;i++)a[i]=0
#define cfast std::ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define pll pair<ll,ll>
#define pii pair<int,int>
#define inc(i,a,n) for(int i=a;i<n;i++)
#define vset(a,n,m) for(int i=0;i<n;i++)a[i]=m;
#define endl '\n'
#define pi 3.141592657
using namespace std;
ll gcd(ll a, ll b) {
	if (a < b)swap(a, b);
	if (b == 0)return a;
	return gcd(b, a % b);
}
ll cpow(ll x, ll n) {
	ll ans = 1;
	while (n > 0) {
		if (n & 1) ans = (ans * x) % mdl;
		x = (x * x) % mdl;
		n >>= 1;
	}
	return ans;
}

/*
-----------------------------------------------------------------------------------

*/

ll a[maxn];
int main() {
	cfast;
	int t=1;
	cin >> t;
	while (t--) {
		int n, k;
		cin >> n >> k;
		ll ans = -1e18;
		inc(i, 0, n) {
			cin >> a[i];
		}
		inc(i, 0, n) {
			inc(j, max(i+1, n - 2 * k), n) {
				ans = max(ans, (ll)(((ll)i+1) * ((ll)j+1) - k * (a[i] | a[j])));
			}
		}
		cout << ans << endl;
	}
}
/*
2022.5.6 12:56
*/