01-Trie 上状压 dp

首先可以发现，如果两个数的二进制前面 $B$ 位相等，那么这 $B$ 位数无论 $x$ 为多少都无法产生贡献。

然后还可以发现，第一个不相等的位可以确定两个数的大小。

考虑把 $a$ 序列插到 01-Trie 里面，这样从顶点到某个点的路径代表这棵子树中的值前面的位数都相等，接下来只需考虑这棵子树里的贡献就好了。

先假设 $x=0$，此时 Trie 里面的所有点都是原来的值。

考虑如果从一个点的 $0$ 子树选一个数 $p$，$1$ 子树选一个数 $q$，很显然 $p<q$，答案是 $q-p$。所以想要 $p$ 尽量大，$q$ 尽量小。

而如果两个数都在同一棵子树中，由于包括这一位前面位数相等，所以直接递推到子树考虑即可。

所以可以记 $mn{u},mx{u},rs{u}$ 分别表示 $u$ 子树能取到的最小最大值和最小差值就可以转移了。

再考虑把 $x$ 的限制加上，实际上相当于给某些曾的儿子进行了翻转，而对某一个子树 $u$ 的答案的影响仅限于 $u$ 以下的层。

所以每一个节点只需要记录它子树内的每一种翻转情况的答案即可。

可以发现 Trie 上深度为 $i$ 的点最多有 $2^i$ 个，而状态数最多有 $2^{n-i}$ 个，每一层乘起来刚好就是 $2^n$，所以直接搞就行了。

时空复杂度 $O(k2^k)$，有点费空间。

代码：

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
#include<cstdio>
#define rep(a,b,c) for(int c(a);c<=(b);++c)
inline int read()
{
	int res=0;char ch=getchar();while(ch<'0'||ch>'9')ch=getchar();
	while(ch<='9'&&ch>='0')res=res*10+(ch^48),ch=getchar();return res;
}
template<typename T> inline T min(const T&x,const T&y){return x<y?x:y;}
template<typename T> inline T max(const T&x,const T&y){return x<y?y:x;}
const int INF=0x3f3f3f3f,N=5e7+10,NN=3e7+10;
int DP[50332000],*mx[1048576],*mn[1048576],*rs[1048576],*buf=DP,ch[1048576][2],n,cnt=1;
inline bool ins(int k)
{
	int p=1;bool flag=0;for(int i=n-1;~i;--i)
	{
		int &x=ch[p][k>>i&1];
		if(!x)flag=true,p=x=++cnt;else p=x;
	}
	return flag;
}
inline void dfs(int p,int B,bool v)
{
	if(!p)return;rs[p]=buf;buf+=(1<<B);if(p!=1){++B;mx[p]=buf;buf+=1<<B;mn[p]=buf;buf+=1<<B;--B;}
	if(!B){mx[p][0]=mn[p][0]=v;mx[p][1]=mn[p][1]=v^1;rs[p][0]=INF;return;} dfs(ch[p][0],B-1,0);dfs(ch[p][1],B-1,1);
	if(ch[p][0]&&ch[p][1])for(int S=0;S<(1<<B);++S)
	{ 
		if(S>>(B-1))
		{
			int T=S^(1<<(B-1));rs[p][S]=min(min(rs[ch[p][0]][T],rs[ch[p][1]][T]),mn[ch[p][0]][S]-mx[ch[p][1]][S]);
			if(p!=1)
			{
				mn[p][S]=mn[ch[p][1]][S]|(v<<B);
				mx[p][S]=mx[ch[p][0]][S]|(v<<B);
				mn[p][S^(1<<B)]=mn[ch[p][1]][S]|((v^1)<<B);
				mx[p][S^(1<<B)]=mx[ch[p][0]][S]|((v^1)<<B);
			}
		}
		else
		{
			rs[p][S]=min(min(rs[ch[p][0]][S],rs[ch[p][1]][S]),mn[ch[p][1]][S]-mx[ch[p][0]][S]);
			if(p!=1)
			{
				mn[p][S]=mn[ch[p][0]][S]|(v<<B);
				mx[p][S]=mx[ch[p][1]][S]|(v<<B);
				mn[p][S^(1<<B)]=mn[ch[p][0]][S]|((v^1)<<B);
				mx[p][S^(1<<B)]=mx[ch[p][1]][S]|((v^1)<<B);
			}
		}
	}
	else
	{
		int c=ch[p][0]|ch[p][1]; for(int S=0;S<(1<<B);++S)
		{
			if(S>>(B-1)){int T=S^(1<<(B-1));rs[p][S]=rs[c][T];} else {rs[p][S]=rs[c][S];}
			if(p!=1)
			{
				mn[p][S]=mn[c][S]|(v<<B);
				mx[p][S]=mx[c][S]|(v<<B);
				mn[p][S^(1<<B)]=mn[c][S]|((v^1)<<B);
				mx[p][S^(1<<B)]=mx[c][S]|((v^1)<<B);
			}
		}
	}
}
int main()
{
	int Q=read();n=read();while(Q--)if(!ins(read())){n=1<<n;while(n--)putchar('0'),putchar(' ');return 0;}
	dfs(1,n,0);for(int S=0;S<(1<<n);++S)printf("%d ",rs[1][S]);putchar('\n');return 0;
}