← 返回题目列表

Codeforces · 1954/D

D. 彩色球

中文机器翻译题面 查看原题

有 $$$n$$$ 不同颜色的球;第 $$$i$$$ 颜色的球的数量为 $$$a_i$$$。

球可以组合成组。每组最多应包含 $$$2$$$ 个球,每种颜色的球不得超过 $$$1$$$ 个。

考虑所有 $$$2^n$$$ 组颜色。对于一组颜色,我们将其值表示为这些颜色的球可以分配到的最小组数。例如,如果有三种颜色,分别为 $$$3$$$、$$$1$$$ 和 $$$7$$$ 球,则它们可以组合成 $$$7$$$ 组(且不少于 $$$7$$$),因此该组颜色的值为 $$$7$$$。

您的任务是计算所有 $$$2^n$$$ 可能的颜色集的值总和。由于答案可能太大,请打印 $$$998\,244\,353$$$ 模。

输入

第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 5000$$$) — 颜色数量。

第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 5000$$$) — 第 $$$i$$$ 颜色的球的数量。

输入的附加限制:球的总数不超过$$$5000$$$。

输出

打印单个整数 - 所有 $$$2^n$$$ 颜色集的值之和,以 $$$998\,244\,353$$$ 为模。

示例

输入 #1

3
1 1 2

输出 #1

11

输入 #2

1
5

输出 #2

5

输入 #3

4
1 3 3 7

输出 #3

76

注意

考虑第一个例子。有 $$$8$$$ 组颜色:

- 对于空集,其值为$$$0$$$;
- 对于集合$$$\{1\}$$$,其值为$$$1$$$;
- 对于集合$$$\{2\}$$$,其值为$$$1$$$;
- 对于集合$$$\{3\}$$$,其值为$$$2$$$;
- 对于集合$$$\{1,2\}$$$,其值为$$$1$$$;
- 对于集合$$$\{1,3\}$$$,其值为$$$2$$$;
- 对于集合$$$\{2,3\}$$$,其值为$$$2$$$;
- 对于集合$$$\{1,2,3\}$$$,其值为$$$2$$$。

因此,所有 $$$2^n$$$ 组颜色的值之和为 $$$11$$$。