当前没有测试数据。

D - 我讨厌非整数数字

分数: $400$ 分

问题描述

给定一个长度为 $N$ 的正整数序列 $A=(a_1,\ldots,a_N)$。
从 $A$ 中选择一个或多个数字有 $(2^N-1)$ 种方式。有多少种方式的平均值是整数。答案对 $998244353$ 取模。

约束条件

• $1 \leq N \leq 100$
• $1 \leq a_i \leq 10^9$
• 输入中的所有值都是整数。

输入

从标准输入中以以下格式给出：

$N$

$a_1$ $\ldots$ $a_N$

输出

输出答案。

3
2 6 2

6

对于每种选择 $A$ 的方式，平均值计算如下：

• 如果只选择 $a_1$，平均值是 $\frac{a_1}{1}=\frac{2}{1} = 2$，是一个整数。

• 如果只选择 $a_2$，平均值是 $\frac{a_2}{1}=\frac{6}{1} = 6$，是一个整数。

• 如果只选择 $a_3$，平均值是 $\frac{a_3}{1}=\frac{2}{1} = 2$，是一个整数。

• 如果选择 $a_1$ 和 $a_2$，平均值是 $\frac{a_1+a_2}{2}=\frac{2+6}{2} = 4$，是一个整数。

• 如果选择 $a_1$ 和 $a_3$，平均值是 $\frac{a_1+a_3}{2}=\frac{2+2}{2} = 2$，是一个整数。

• 如果选择 $a_2$ 和 $a_3$，平均值是 $\frac{a_2+a_3}{2}=\frac{6+2}{2} = 4$，是一个整数。

• 如果选择 $a_1$、$a_2$ 和 $a_3$，平均值是 $\frac{a_1+a_2+a_3}{3}=\frac{2+6+2}{3} = \frac{10}{3}$，不是一个整数。

因此，有 $6$ 种方式满足条件。

5
5 5 5 5 5

31

不论选择 $A$ 的哪一种方式，平均值都是 $5$。