UOJ Logo Universal Online Judge

UOJ

#703. 赵云八卦阵

附件下载 统计

功盖三分国,名成八阵图。江流石不转,遗恨失吞吴。 —— 杜甫《八阵图》

三国时期,诸葛亮的八卦阵,可比十万精兵。穿越到 2022 年的赵云,却发现八卦阵早已失传。

不过时代在进步。在这个 64 位计算机横行的年代,赵云开始思考如何超越诸葛亮,发明出更强的新八卦阵 —— 又名 $2^{60}$ 卦阵。正好,UOJ 也需要引入先进技术来保护自己的服务器。

赵云想发明的新八卦阵是一个圆形的多层防御体系,严密地保护住 UOJ 服务器。新八卦阵里里外外一共 $n$ 层子阵,从外到内依次编号为 $1, \dots, n$。每层子阵都设置了精巧的防御手段来防范入侵,其中第 $i$ 层子阵的防御力为 $a_i$,为小于 $2^{60}$ 的非负整数($0 \le a_i < 2^{60}$)。

为了对入侵者进行心理威慑,八卦阵应由从外到内防御力逐渐递增子阵构成,即 $a_1$ 到 $a_n$ 严格递增。在满足这个条件的基础上,八卦阵层数越多越好。然而,在赵云的设计初稿上,$a_1$ 到 $a_n$ 并不一定严格递增。于是他决定按照太极八卦的二进制思维对这些子阵进行多次操作:

  • 修改操作:选择一个层数编号 $2 \le x \le n$,并将 $a_x$ 变成 $a_x\oplus a_{x-1}$(其中$\oplus$表示二进制异或);
  • 删除操作:选择一个层数编号 $1 \le x \le n$,并将这一层删掉,总层数减一,后续层数编号依次平移一位。

看着赵云满头大汗地对付大整数二进制运算的样子,你决定带领三个臭皮匠帮帮他:给定初始的 $a_1, \dots, a_n$,允许多次进行上述修改和删除操作,如果想让操作后的八卦阵从外到内防御力逐渐递增,初始的八卦阵至多可以保留多少层子阵?

人话题面:给定一个序列 $a_1, \dots, a_n$,每次可以将某一项 $a_x$($2 \le x\le n$)变成 $a_{x}\oplus a_{x-1}$,求这个序列最长上升子序列长度的最大值。

输入格式

第一行一个正整数 $n$,表示序列长度。

第二行 $n$ 个正整数 $a_1, \dots, a_n$ 表示赵云的初稿上每一层的防御力。注意初稿上所有 $a_i$ 均大于等于 $1$,但后续使用修改操作时允许产生 $a_i = 0$。

由于本道题输入规模过大,提供一份快速输入输出模板,见下发文件中的 io.cpp

输出格式

一行一个数表示这个八卦阵的防御力。

样例一

input

5
5 4 3 2 1

output

4

explanation

依次对$4,3,4,5,3,2$操作可以得到最终序列为$5,1,3,6,7$,最长上升子序列长度为$4$。同时可以证明不存在更优的方案。

样例二

见附加文件中的ex_xor2.inex_xor2.ans

样例三

见附加文件中的ex_xor3.inex_xor3.ans

数据范围与提示

子任务编号 $n\leq$ $a_i\lt$ 分值
$1$ $5$ $16$ $10$
$2$ $20$ $2^{16}$ $20$
$3$ $1000$ $2^{60}$ $20$
$4$ $10^5$ $20$
$5$ $10^6$ $30$

对于所有数据,$n\leq 10^6,1\leq a_i\lt 2^{60}$。

时间限制:$\texttt{1s}$

空间限制:$\texttt{512MB}$