CF2038D.Divide OR Conquer

给定一个由 $[a_1, a_2, \ldots, a_n]$ 组成的数组，其中每个元素都是 $0$ 到 $10^9$ 之间的整数。你需要将该数组划分为若干个连续的段（也可以只划分为一个段），使得每个元素恰好属于一个段。

设第一个段为 $[a_{l_1}, a_{l_1 + 1}, \ldots, a_{r_1}]$，第二个段为 $[a_{l_2}, a_{l_2+ 1}, \ldots, a_{r_2}]$，……，最后一个段为 $[a_{l_k}, a_{l_k+ 1}, \ldots, a_{r_k}]$。由于每个元素都应恰好属于一个段，所以 $l_1 = 1$，$r_k = n$，并且对于每个 $i$（$1 \le i \le k-1$），都有 $r_i + 1 = l_{i+1}$。划分还需满足以下条件：$f([a_{l_1}, a_{l_1 + 1}, \ldots, a_{r_1}]) \le f([a_{l_2}, a_{l_2+ 1}, \ldots, a_{r_2}]) \le \dots \le f([a_{l_k}, a_{l_k+1}, \ldots, a_{r_k}])$，其中 $f(a)$ 表示数组 $a$ 所有元素的按位或（bitwise OR）。

请计算有多少种不同的划分方式，并输出对 $998\,244\,353$ 取模的结果。如果两个划分方式对应的 $[l_1, r_1, l_2, r_2, \ldots, l_k, r_k]$ 序列不同，则认为它们是不同的划分方式。

第一行包含一个整数 $n$（$1 \le n \le 2 \cdot 10^5$），表示数组 $a$ 的长度。

第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$0 \le a_i \le 10^9$），表示给定数组的元素。

输出一个整数，表示不同划分方式的数量，对 $998\,244\,353$ 取模。

在前两个样例中，任何一种划分方式都是合法的。

在第三个样例中，有三种合法的划分方式：

• $k = 3$；$l_1 = 1, r_1 = 1, l_2 = 2, r_2 = 2, l_3 = 3, r_3 = 3$；得到的数组为 $[3]$、$[4]$、$[6]$，且 $3 \le 4 \le 6$；
• $k = 2$；$l_1 = 1, r_1 = 1, l_2 = 2, r_2 = 3$；得到的数组为 $[3]$ 和 $[4, 6]$，且 $3 \le 6$；
• $k = 1$；$l_1 = 1, r_1 = 3$；只有一个数组 $[3, 4, 6]$。

如果将数组划分为 $[3, 4]$ 和 $[6]$，则第一个数组的按位或为 $7$，第二个数组的按位或为 $6$，$7 > 6$，因此这种划分方式不合法。

由 ChatGPT 4.1 翻译