← 返回题目列表

AtCoder · abc262_d

G. 我讨厌非整数

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

分数: 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.