分数: 400 点
问题陈述
给你一个正整数序列 A=(a_1,\ldots,a_N) 长度 N.
有 (2^N-1) 选择一项或多项的方式 A。 其中有多少具有整数值平均值? 求计数模数 998244353.
约束
- 1 \leq N \leq 100
- 1 \leq a_i \leq 10^9
- 输入中的所有值都是整数。
输入
输入由标准输入按以下格式给出:
N a_1 \ldots a_N
输出
打印答案。
示例输入 1
3 2 6 2
示例输出 1
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,这是一个整数。 选择
-
If a_1 和 a_2 ,平均值为 \frac{a_1+a_2}{2}=\frac{2+6}{2} = 4,这是一个整数。 选择
-
If a_1 和 a_3 ,平均值为 \frac{a_1+a_3}{2}=\frac{2+2}{2} = 2,这是一个整数。 选择
-
If a_2 和 a_3 ,平均值为 \frac{a_2+a_3}{2}=\frac{6+2}{2} = 4,这是一个整数。 选择
-
If a_1, a_2,和 a_3 ,平均值为 \frac{a_1+a_2+a_3}{3}=\frac{2+6+2}{3} = \frac{10}{3},它不是整数。
因此, 6 满足条件的方式。
示例输入 2
5 5 5 5 5 5
示例输出 2
31
无论选择一项或多项 A,平均值等于 5.