P17711 Red Face 选数字（choose）

题目来源：【HT-122-Div.3】核桃 CSP-J 组模拟赛

Red Face 有一个长度为 $n$ 的数组 $a$。 现在，Red Face 需要选择一个同样长度为 $n$ 数组 $b$。对于数组 $b$ 中的每一个元素 $b_i$，都必须满足： $$ b_i \in [-k,k] $$ 也就是说，$b_i$ 可以选择为 $-k$ 到 $k$ 之间的任意一个整数，包括 $-k$ 和 $k$。 在确定数组 $b$ 后，Red Face 会根据数组 $a$ 和数组 $b$ 构造出一个新的长度为 $n$ 的整数数组 $c$。对于每一个位置 $i$，数组 $c$ 的元素满足： $$ c_i=a_i+b_i $$ 你需要计算，一共有多少种不同的数组 $b$，能够使构造出的数组 $c$ 全部相等。也就是说，需要满足： $$ c_1=c_2= \cdots = c_n $$ 请输出满足上述条件的方案数。

第一行输入一个正整数 $n,k$ 表示数组长度，和可选数字范围。 第二行输入 $n$ 个正整数 $a_i$。

输入一行一个整数，表示答案。

### 样例解释 对于样例 $1$： 所有 $c_i$ 可以同时取 $2,3,4$，因此共有 $3$ 种方案。 对应的数组 $b$ 分别为： - 当所有 $c_i=2$ 时，$b=\{0,-1,-2,0,-1\}$； - 当所有 $c_i=3$ 时，$b=\{1,0,-1,1,0\}$； - 当所有 $c_i=4$ 时，$b=\{2,1,0,2,1\}$。 以上数组中的每个 $b_i$ 均满足 $b_i \in [-2,2]$。 ### 数据规模与约定 ::cute-table{tuack} | 测试点编号 | $n \le$ | | :----------: | :-------------: | | $1 \sim 4$ | $10$ | | $5 \sim 8$ | $500$ | | $9 \sim 12$ | $2000$ | | $13 \sim 16$ | $2 \times 10^5$ | | $17 \sim 20$ | $10^6$ | 对于 $100\%$ 的测试点，保证： - $1 \le n \le 10^6$ - $1 \le a_i,k \le 10^9$