#P18228. Light Up the Hypercube

Light Up the Hypercube

Light Up the Hypercube

2040 年的一天下午,Sulfox 正在玩 Little Q 设计的二维点灯游戏。他的定制 AI 误以为他想要更难的挑战,于是提供了一个高维版本,还挡住了屏幕。Sulfox 决定自己求出最优操作方案所需的费用。

原题中的定制 AI 系统

游戏在一个 nn 维超立方体上进行。它的每条边只沿某一个维度延伸,每个顶点装有一盏灯,共有 2n2^n 盏灯。每盏灯可以亮或者灭;翻转一盏灯会使亮变灭、灭变亮。

共有 2n2^n 类操作,编号为 0,1,…,2n−10,1,\ldots,2^n-1。第 ii 类操作的费用为 aia_i,可以按以下规则选择并翻转一个子立方体上的全部顶点:

  • 将 ii 写成 nn 位二进制 bnbn−1…b1b_n b_{n-1}\ldots b_1,其中 bjb_j 是从低到高第 jj 位。
  • 设其中有 kk 个 11,则本次选择一个 kk 维面。
  • 对每个 bj=1b_j=1 的维度,所选面必须沿第 jj 维延伸,也就是该维坐标可以取两种值。
  • 对每个 bj=0b_j=0 的维度,所选面沿该维没有厚度,也就是固定该维坐标;可以选择固定为两种坐标值中的任意一种。
  • 翻转所选面全部 2k2^k 个顶点上的灯。

例如,第 00 类操作以费用 a0a_0 翻转任意一个顶点的灯;第 2j−12^{j-1} 类操作以费用 a2j−1a_{2^{j-1}} 翻转任意一条沿第 jj 维延伸的边的两个端点;第 2n−12^n-1 类操作以费用 a2n−1a_{2^n-1} 翻转所有灯。

游戏已经开始,但 Sulfox 完全看不到灯的状态。初始状态可能是全部 22n2^{2^n} 种状态中的任意一种。唯一的反馈是:每执行一次操作后,若所有灯都亮着,就会响起提示音。 初始时即使所有灯已经亮着,也不会因此直接获得提示。

他需要找出一个操作序列,使得不论初始状态是哪一种,按顺序执行这些操作时,总会在某次操作后听到提示音。

求这样的序列的最小总费用,答案对 998244353998244353 取模。

输入格式

第一行包含一个整数 TT,表示测试用例数。

每个测试用例:

  • 第一行包含一个整数 nn,表示超立方体的维数。
  • 第二行包含 2n2^n 个整数 a0,a1,…,a2n−1a_0,a_1,\ldots,a_{2^n-1},表示各类操作的费用。

数据范围:

$$1\le T\le10^4,\qquad 2\le n\le20,\qquad 1\le a_i\le10^6.$$

所有测试用例的 2n2^n 之和不超过 2202^{20}。

输出格式

对于每个测试用例,输出一行一个整数,表示最小总费用对 998244353998244353 取模的结果。

样例

2
2
4 2 2 1
4
3 3 2 3 1 3 2 2 2 3 2 1 1 2 3 2
25
65666