Sum Difference

题目描述

我们有一个长度为 $N$ 的整数序列 $A$，其中 A_1 = X, A_{i+1} = A_i + D (1 \leq i < N ) 成立。 Takahashi 将从这个序列中取出若干个（可能全部或一个也不取）元素，Aoki 将取走所有其他元素。 令 $S$ 与 $T$ 分别为 Takahashi 和 Aoki 取走的数的和。$S - T$ 有多少种可能的取值？

输入格式

输入从标准输入按如下格式给出： $N$ $X$ $D$

输出格式

输出 $S - T$ 的不同可能值的数量。

3 4 2

8

2 3 -3

2

100 14 20

49805

提示

$-10^8 \leq X, D \leq 10^8$ $1 \leq N \leq 2 \times 10^5$ 输入中的所有数值均为整数。$A$ 为 $(4, 6, 8)$。 对于 Takahashi 和 Aoki 取元素的方式共有八种：$((), (4, 6, 8)), ((4), (6, 8)), ((6), (4, 8)), ((8), (4, 6))), ((4, 6), (8))), ((4, 8), (6))), ((6, 8), (4)))$, 和 $((4, 6, 8), ())$。 这些方式中 $S - T$ 的值分别为 $-18, -10, -6, -2, 2, 6, 10$ 和 $18$，因此共有八种可能的 $S - T$。
$A$ 为 $(3, 0)$。$S - T$ 有两种可能值：$-3$ 和 $3$。

标签: AtCoder|abc147F

来源

AtCoder|abc147F