题目描述

Byteman is a scientist who investigates creation of crystals consisting of atoms of different elements.

He has designed a special process for creating crystals and has discovered a formula specifying theamount of elements that can be used to create a crystal. Now, he wonders how many differentcrystals can be created in such process.

For non-negative integers $x$ and $y$, by $x\bigoplus y$ we shall denote their bit-wise xor. The basic xor forsingle bits is defined by:

$1\bigoplus 1=0\bigoplus 0=0$,$0\bigoplus 1=1\bigoplus 0=1$.

Byteman knows $n$ different elements that can be used to create crystals -these are numbered from $1$ to $n$. For each element $i$ there is an upper bound $m_i$ on number of atoms of this elementthat can be used to create a crystal. Byteman can create one unique crystal composed of $a_i$ atomsof the element $i$ (for $i=1,\cdots,n$), if and only if:

• $0\le a_i\le m_i$ for $i=1,\cdots,n$

• $a_1\bigoplus\cdots\bigoplus a_n=0$, and

• $a_1+a_2+\cdots+a_n\ge 1$.

Note that the last condition is quite obvious and essentially states that every crystal is composed ofat least one atom.

TaskWrite a programme which:

reads form the standard input: the number of elements and the bounds on numbers of atoms of particular elements, computes the number of different crystals that can be created, writes the result to the standard output.

输入格式

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

The second, last line of the standard input contains $n$ positive integers $m_1,\cdots,m_n$, separated by single spaces,$1\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 $2^{64}$.

题目大意

题目描述

给定 $n$ 个正整数 $m_1$ 到 $m_n$，对长度为 $n$ 且满足以下条件的整数序列 $a$ 计数：

• 对于任意 $1\le i\le n$，$0\le a_i\le m_i$；
• $a_1\oplus a_2\oplus\cdots\oplus a_n=0$，其中 $\oplus$ 为按位异或运算；
• $a_1+a_2+\cdots+a_n\ge1$。

输入格式

第一行有一个正整数 $n$。

第二行有 $n$ 个正整数，表示 $m_1,m_2,\ldots,m_n$。

输出格式

输出一行一个正整数表示序列的个数。

说明/提示

$1\le n\le50$。

$1\le m_i\le2^{32}-1$。

数据保证答案小于 $2^{64}$。

感谢 @FZzzz @UnyieldingTrilobite 提供翻译。

3
2 1 3

5