最优分割

题目描述:

一个数字序列是回文的，当且仅当其从前往后读与从后往前读不变。

形式地，一个序列$S[1..n]$是回文的当且仅当对任意$j\in [1..n]$，有$S[j]=S[n-j+1]$。

定义一个回文数字序列$S[1..n]$的能量值为$$P(S[1..n])=(S[1]\oplus S[2]\oplus \cdots \oplus S[\lceil n/2\rceil ])\times n$$

其中$\oplus$表示按位异或，$\lceil n/2\rceil$表示向上取整。

即能量值为序列左半部分数字异或和(若长度为奇数，包括正中间的数字)乘上序列长度。

现给定一个长度为$N$的序列$T$，问将序列$T[1..N]$分割成若干个连续的回文序列，这些回文序列的能量和最大为多少？

请输出使得能量和最大的任一合法分割方案。

输入格式:

第一行一个整数$N$。

第二行$N$个整数表示序列$T$。

$1\le N\le {10}^6,0\le T[i]\le {10}^9$.

输出格式:

第一行输出能得到的最大能量和为多少。

第二行输出一个整数$C$，表示$T$被分割成了$C$块。

接下来$C$行，升序输出每一块的右端点的下标。

样例输入:

6
1 2 1 2 1 2

样例输出:

18
2
3
6

提示:

 $T$的分割方法有$(1),(2),(1),(2),(1),(2);(1),(2,1,2),(1),(2);(1,2,1),(2,1,2)\dots$

其中分割成$(1,2,1),(2,1,2)$能量值为$(1\oplus 2)\times 3+(2\oplus 1)\times 3=3\times 3+3\times 3=18$，为最优解。

时间限制: 3000ms
空间限制: 512MB

---

来源: by Massimo