P3447 [POI2006]KRY-Crystals

    • 4通过
    • 10提交
  • 题目提供者 洛谷
  • 评测方式 云端评测
  • 标签 POI 2006 高性能
  • 难度 NOI/NOI+/CTSC
  • 时空限制 1000ms / 128MB


  • 提示:收藏到任务计划后,可在首页查看。
  • 体验新版界面

    最新讨论 显示

    推荐的相关题目 显示


    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.


    1.任意$b_i\le a_i$

    2.$b_1\ xor\ b_2\ xor\ b_3\ xor\cdots xor\ bn=0$





    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}$.


    输入样例#1: 复制
    2 1 3
    输出样例#1: 复制