P12555 [UOI 2024] AND Array

给定一个整数 $b$ 和一个非负整数数组 $a_1,a_2,\ldots,a_n$。数组 $a$ 的所有元素都小于 $2^b$。 定义 $f(s, p)$ ($1\le s\le n$, $0\le p < b$) 为以下伪代码的执行结果： ``` res = 0 x = power(2, p) for i = s to n: if ((x AND a[i]) == 0): x = (x OR a[i]) res = res + i return res ``` 其中，``power(2, p)`` 表示 $2^p$，``AND`` 表示按位与运算，``OR`` 表示按位或运算。 非负整数 $a$ 和 $b$ 的按位与运算结果是一个非负整数，其二进制表示中某一位为 1 当且仅当 $a$ 和 $b$ 的二进制表示在该位都为 1。例如，$3_{10}$ AND $5_{10} = 0011_{2}$ AND $0101_{2} = 0001_{2} = 1_{10}$。 非负整数 $a$ 和 $b$ 的按位或运算结果是一个非负整数，其二进制表示中某一位为 0 当且仅当 $a$ 和 $b$ 的二进制表示在该位都为 0。例如，$3_{10}$ OR $5_{10} = 0011_{2}$ OR $0101_{2} = 0111_{2} = 7_{10}$。 对于每个 $i$ 从 $1$ 到 $n$，计算 $$f(i,0) + f(i, 1) + \ldots + f(i, b-1)$$

第一行包含两个整数 $n$ 和 $b$ ($1 \leq n \leq 10^5$, $1 \leq b \leq 20$) —— 分别表示数组 $a$ 的长度和数组元素的限制。 第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$ ($0 \leq a_i < 2^b$) —— 数组 $a$ 的元素。

输出 $n$ 个整数 —— 要求的计算结果。

在第一个示例中，$f(1,0)=1+2+5=8$，$f(1,1)=1+3+5=9$，$f(1,2)=1+2+3=6$，因此第一个要求的值为 $8+9+6 = 23$。 ### 评分标准 - （10 分）：$n \leq 2\,000$； - （10 分）：$a_i = 2^k$，其中 $k$ 为整数； - （15 分）：$b \leq 8$； - （15 分）：$b \leq 12$； - （25 分）：$b \leq 16$； - （25 分）：无额外限制。 翻译由 DeepSeek V3 完成