P3447 [POI2006]KRY-Crystals

    • 2通过
    • 6提交
  • 题目提供者 洛谷OnlineJudge
  • 评测方式 云端评测
  • 标签 POI 2006 高性能
  • 难度 尚无评定
  • 时空限制 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.

    给定n个数{a1,a2..an},求一个序列{b1,b2..bn}满足:

    1.任意$b_i\le a_i$

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

    3.$sum_{i=1}^{n}b_i>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: 复制
    3
    2 1 3
    输出样例#1: 复制
    5
    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。