Logo Daimayuan Online Judge

Home

时间限制:1 s 空间限制:1024 MB

#468. 函数求和

附加文件 统计

题目

给定$n$个整数$a_1, a_2, \dots, a_n$和正整数$k$满足$(0 \leq a_i \leq 2^k - 1)$。

定义函数$f(x)$为满足$a_i \& x \neq a_i$的最小的$i$,当满足条件的$i$不存在时 $f(x)=0$。

求$\sum_{i = 0}^{2^k - 1}f(i)$。 由于答案可能很大,输出答案取模$998244353$后的值。

输入格式

第一行两个数字$n$, $k$。

接下来一行$n$个整数 $a_1, a_2, \dots, a_n$,表示这$n$个数。

输出格式

一行一个整数,表示答案。

样例输入1

2 1
0 1

样例输出1

2

样例输入2

2 2
2 1

样例输出2

4

样例输入3

5 10
389 144 883 761 556

样例输出3

1118

样例解释

对于样例1, $f(0) = 2$, $f(1) = 0$, 答案 $= 2$。

数据规模

所有数据保证 $1\leq n \leq 100, 1 \leq k \leq 60$。