30分：$n\leq 20$

爆搜即可。

30分：$n\leq 1000,a_i< 128$

$dp_{i,j,k}$表示我考虑了前$i$个位置，用了$j$个$|$，能否让结果为$k$，记录决策后，沿着决策进行bfs最小字典序即可。

或者我们也可以反过来，记$dp_{i,j,k}$表示从$i$开始向后，当前的值是$k$，一共用了$j$个$|$，最终答案最大是多少。然后从起点开始贪心。

（这个部分实际上不好拿）

10分：$k=1$

我们枚举$k$放在哪个位置，通过计算区间内每一位上有多少个$1$，就可以快速得到答案。

正解

首先，考虑这样一个结论：任意时刻，肯定都是把$\&$放前面，$|$放后面，结果能取得最大的。

原因很简单：假设有三个相邻的位置$x,y,z$，左边是$|$，右边是$\&$，那么结果最大是$z$，假设左边是$\&$，右边是$|$，那么结果最小是$z$。所以我们调整使得整个序列不存在$\&$在$|$后，一定不会使得答案变差。

那么我们就可以考虑按位贪心了：

对于当前位置来说，如果能放$|$，且放了$|$之后，后续的最大答案依旧是理论最大值，则放$|$，否则放$\&$。

#include<bits/stdc++.h>
#define ll long long
#define maxn 200005
using namespace std;
int n,k;
ll a[maxn],sum[maxn][63];
ll check(int l,ll now,int k)
{
	//[n-k+1,n]这一段是|,[l,n-k]这一段是&
	if (l<=n-k)
	{
		ll tt[63]={0};
		for (int i=0;i<60;i++) tt[i]=sum[n-k][i]-sum[l-1][i];
		for (int i=0;i<60;i++) if (tt[i]!=(n-k-l+1) && ((now>>i)&1)) now^=(1ll<<i);
	} 
	if (n-k+1<=n)
	{
		ll tt[63]={0};
		for (int i=0;i<60;i++) tt[i]=sum[n][i]-sum[n-k][i];
		for (int i=0;i<60;i++) if (tt[i]) now|=(1ll<<i);
	}
	return now;
}
int main()
{
	cin>>n>>k;
	for (int i=1;i<=n;i++) cin>>a[i];
	for (int i=1;i<=n;i++)
	{
		for (int j=0;j<60;j++) sum[i][j]=sum[i-1][j];
		for (int j=0;j<60;j++) if ((a[i]>>j)&1) sum[i][j]++;
	}
	//2往后最后k个是|,其他是&,初始时候是a[1]的结果
	ll zd=check(2,a[1],k); 
	cout<<zd<<endl;
	int nowk=k; ll ans=a[1];
	for (int i=2;i<=n;i++)
	{
		if (nowk>=1 && check(i+1,ans|a[i],nowk-1)==zd)
		{
			cout<<"|";
			ans=ans|a[i]; nowk--;
		}
		else
		{
			cout<<"&";
			ans=ans&a[i];
		}
//		cout<<i<<" "<<ans<<" "<<nowk<<endl;
	}
	cout<<endl;
	if (ans!=zd) while (1);
}