CF2268E Kia Kio and Tree of Life

解锁水晶终端后，Kia 和 Kio 发现了王国被遗忘之心的蓝图：一棵数字生命之树，以数组 $ a_1, a_2, \ldots, a_n $ 为种子。 为了让这棵树重新焕发生机，她们必须把所有可能形态的生命之树编织在一起。对于任意连续区间，Kia 会选一个下标 $ i $ 作为根。Kio 相信她的选择，会仔细编织生命之枝：左子树由前面的区间 $ [1, i-1] $ 构造，右子树由后面的区间 $ [i+1, n] $ 构造。 当一棵生命之树绽放后，它的生命共鸣 $ f(\text{tree}) $ 由树上的联结决定。如果切断 $ n-1 $ 条树枝中的任意一条，树就会分成两个不连通的部分，并释放出 $ X+Y $ 的能量，其中 $ X $ 和 $ Y $ 分别是位于两个部分中的数组元素的按位异或和。 树的总能量 $ f(\text{tree}) $ 就是所有 $ n-1 $ 条树枝释放的能量之和。注意每条边的断开是独立的。 Kia 想知道她们能唤醒的终极生命力。请帮她们计算她们共同创造出的所有合法生命之树的 $ f(\text{tree}) $ 之和，模 $ 998\,244\,353 $。

每个测试包含多个测试用例。第一行包含测试用例数 $ t $（$ 1 \le t \le 10^4 $）。接下来是测试用例描述。 每个测试用例的第一行包含一个整数 $ n $（$ 1 \le n \le 2\cdot10^5 $）——数组的大小。 第二行包含 $ n $ 个整数 $ a_1,a_2,\ldots,a_n $（$ 0 \le a_i \lt 2^{18} $）。 保证所有测试用例中 $ n $ 的总和不超过 $ 2\cdot10^5 $。

对于每个测试用例，输出一个整数——所有合法生命之树的 $ f(\text{tree}) $ 之和对 $ 998\,244\,353 $ 取模后的结果。

对于第一个测试用例，$ n=2 $ 且 $ a = [1,2] $。可以构造两棵合法树：一棵以 $ a_1 $ 为根、$ a_2 $ 为右孩子，另一棵以 $ a_2 $ 为根、$ a_1 $ 为左孩子。 两棵树中，切断唯一的一条树枝都会得到两个连通块，异或和分别为 $ X=1 $ 和 $ Y=2 $。因此每棵树的值都是 $ 1 + 2 = 3 $，两棵生命之树累计的总能量为 $ 3+3=6 $。 对于第二个测试用例，$ n=3 $ 且 $ a = [1,1,1] $。 共有 $ 5 $ 棵合法树： - 根为 $ 1 $：$ \{(1,2), (2,3)\} $，$ \{(1, 3), (2, 3)\} $； - 根为 $ 2 $：$ \{(1,2), (2,3)\} $； - 根为 $ 3 $：$ \{(1,3), (1,2)\} $，$ \{(2, 3), (1, 2)\} $。 所有树都只是一条含三个顶点的路径。切断任意一条树枝后，两个连通块的异或和都是 $ X=1 $、$ Y=0 $。因此每棵树的值都是 $ 2 $，五棵生命之树累计的总能量为 $ 5\cdot 2=10 $。 由 Deepseek V4.1 翻译，人工修改校对。