#P1522. [POI2006]Kry

    ID: 534 传统题 1000ms 512MiB 尝试: 54 已通过: 47 难度: 7 上传者: 标签>CF2300提高+/省选-数位 DP计数 DP奇偶性分析滚动数组同余的加减乘运算

[POI2006]Kry

题目描述

给定 nn 个数 a1,a2,⋯ ,an{a_1,a_2,\cdots,a_n},求一个序列 b1,b2,⋯ ,bn{b_1,b_2,\cdots,b_n} 满足:

  1. 每个 bib_i 都是非负整数,满足 0≤bi≤ai0\le b_i\le a_i。 2.b1 xor b2 xor b3 xor⋯xor bn=0b_1\ xor\ b_2\ xor\ b_3\ xor\cdots xor\ bn=0 3.sumi=1nbi>0sum_{i=1}^{n}b_i>0

求这样序列的个数。

输入格式

The first line of the standard input contains the number of elements nn, 1≤n≤501\le n\le 50.

The second, last line of the standard input contains nn positive integers m1,⋯ ,mnm_1,\cdots,m_n, separated by single spaces,1≤mi<232−11\le m_i < 2^{32}-1.

输出格式

Your programme should write one integer to the standard output - total number of different crystals that can be created. You can assume that this number is less than 2642^{64}.

3
2 1 3
5