#P1442. [Poi2006]Crystal

    ID: 453 传统题 1000ms 512MiB 尝试: 333 已通过: 91 难度: 8 上传者: 标签>CF2400提高+/省选-线性 DP计数 DP加法原理高精度加法高精度减法高精度乘法高精度除法

[Poi2006]Crystal

题目描述

给定 nn 个数 a1⋯na_{1\cdots n},对序列 b1⋯nb_{1\cdots n} 计数,要求其满足:

  1. 任意 bi≤aib_i\le a_i;
  2. ⊕i=1nbi=0\oplus_{i=1}^nb_i=0;
  3. ∑i=1nbi>0\sum_{i=1}^{n}b_i>0。

输入格式

每一行给出数字 nn。

下面一行给出 nn 个数字 a1⋯na_{1\cdots n}。

输出格式

一行一个整数表示答案。

3
2 1 3
5

样例解释

满足条件的 bb 有:(0,1,1)(0,1,1),(1,0,1)(1,0,1),(1,1,0)(1,1,0),(2,0,2)(2,0,2),(2,1,3)(2,1,3)。

数据规模与约定

对于 100%100\% 的数据,2≤n≤502\leq n\leq 50,1≤ai≤232−11\leq a_i\leq 2^{32}-1。