← 返回题目列表

Codeforces · 2038/D

D. 分而治之

中文机器翻译题面 查看原题

给定一个数组 $$$[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}]$$$。由于每个元素都应该属于一个数组,因此对于从 $$$1$$$ 到 $$$k-1$$$ 的每个 $$$i$$$,$$$l_1 = 1$$$、$$$r_k = n$$$ 和 $$$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$$$ 中所有元素的按位或。

计算分割数组的方式数,并以 $$$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$$$ 为模。

示例

输入 #1

3
1 2 3

输出 #1

4

输入 #2

5
1000 1000 1000 1000 1000

输出 #2

16

输入 #3

3
3 4 6

输出 #3

3

注意

在前两个示例中,每种拆分数组的方法都是有效的。

在第三个示例中,有三种有效的方法来分割数组:

- $$$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$$$,所以这种分割数组的方式是无效的。