最优分割
题目描述:
一个数字序列是回文的，当且仅当其从前往后读与从后往前读不变。
形式地，一个序列\(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 \dots \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