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

游戏在一个 维超立方体上进行。它的每条边只沿某一个维度延伸,每个顶点装有一盏灯,共有 盏灯。每盏灯可以亮或者灭;翻转一盏灯会使亮变灭、灭变亮。
共有 类操作,编号为 。第 类操作的费用为 ,可以按以下规则选择并翻转一个子立方体上的全部顶点:
- 将 写成 位二进制 ,其中 是从低到高第 位。
- 设其中有 个 ,则本次选择一个 维面。
- 对每个 的维度,所选面必须沿第 维延伸,也就是该维坐标可以取两种值。
- 对每个 的维度,所选面沿该维没有厚度,也就是固定该维坐标;可以选择固定为两种坐标值中的任意一种。
- 翻转所选面全部 个顶点上的灯。
例如,第 类操作以费用 翻转任意一个顶点的灯;第 类操作以费用 翻转任意一条沿第 维延伸的边的两个端点;第 类操作以费用 翻转所有灯。
游戏已经开始,但 Sulfox 完全看不到灯的状态。初始状态可能是全部 种状态中的任意一种。唯一的反馈是:每执行一次操作后,若所有灯都亮着,就会响起提示音。 初始时即使所有灯已经亮着,也不会因此直接获得提示。
他需要找出一个操作序列,使得不论初始状态是哪一种,按顺序执行这些操作时,总会在某次操作后听到提示音。
求这样的序列的最小总费用,答案对 取模。
输入格式
第一行包含一个整数 ,表示测试用例数。
每个测试用例:
- 第一行包含一个整数 ,表示超立方体的维数。
- 第二行包含 个整数 ,表示各类操作的费用。
数据范围:
$$1\le T\le10^4,\qquad 2\le n\le20,\qquad 1\le a_i\le10^6.$$所有测试用例的 之和不超过 。
输出格式
对于每个测试用例,输出一行一个整数,表示最小总费用对 取模的结果。
样例
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