1005. Yougou Cleansing

题目描述

「千枝万脉，请除祸灾。」

「…于此，宣其祓却。」

---

雷樱乃神樱之移枝，代神樱吸纳地脉中的不净。如今，一处小祓结界内的污秽再度躁动。Index 已经取得与之对应的「镇物」；为了完成祓除，她还需要辨认并依次调整结界中用于祓祝的石座，使其与祝式相合，从而摧破结界，逼出其中的污秽化身。

结界中共有 $n$ 个依次排列的石座，每个石座上有 $k$ 个纹样。Index 将第 $i$ 个石座的状态记为 $a_i$，从而得到一个长度为 $n$ 的非负整数数组 $a_1,a_2,\ldots,a_n$，且数组中的每个元素都严格小于 $2^k$。

然而，污秽遮蔽了石座上的部分纹样。不妨将 Index 此时能够辨认的纹样记作掩码 $S\in[0,2^k-1]$，并定义第 $i$ 个石座在这一视野下呈现的状态为 $A_S[i]=a_i\mathbin{\&}S$，其中 $\mathbin{\&}$ 表示按位与运算。

Index 希望对于每个 $S=0,1,\ldots,2^k-1$，找出尽可能长的一段连续石座 $[l,r]$，使得存在一个整数 $C$，使得对任意 $i\in[l,r]$，均有 $A_S[i]=(C-i)\mathbin{\&}S$。

考虑到巨大的输出量，不妨令 $\text{ans}_S$ 为 $S$ 的答案，请你输出如下哈希值，其中，$B=218,105,633=\text{0x0d000721}$：

$$\lparen\sum_{S=0}^{2^k-1} (\text{ans}_S\times B^S \bmod 998244353)\rparen\bmod 2^{64}$$

请注意取模运算在求和内部。

输入格式

第一行包含一个整数 $T$（$T \le 100$），表示测试数据的组数。

对于每组测试数据：

• 第一行包含两个整数 $n,k$（$1\le n\le 2\times 10^5,1\le k\le 20$）；

• 第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$（$0\le a_i<2^k$）。

保证对于所有测试数据，$\sum 2^k\le 2^{22}$，$\sum n \le 5\times 10^5$。

输出格式

对于每组测试数据，输出一行一个整数，表示该组数据的答案哈希值。

样例输入

3
4 2
3 2 1 0
5 2
0 0 0 0 0
4 2
0 1 0 1

样例输出

1309248575
851317235
1589957732

提示

三组数据的真实答案分别是 $[4,4,4,4],[5,1,2,1],[4,4,2,2]$。

请注意 IO 效率对程序运行时间的影响。本场比赛的 Multicon 一题中下发了快速读入与输出模板，你也许希望在本题中使用它。

「与君相别离，不知何日是归期，我如朝露转瞬晞。」

来源：2026杭电多校-测试专用（山西实验） 原题链接：http://acm.hdu.edu.cn/contest/problem_show.php?cid=1234&pid=1005