P15591 [ICPC 2020 Jakarta R] Moon and Sun

设 $S$ 是一个非空整数序列，$K$ 是一个正整数。函数 $moon()$ 和 $sun()$ 定义如下： $$ moon(S_{1..|S|}) = \begin{cases} S & \text{if } |S| = 1 \\ [S_2 - S_1, S_3 - S_2, \dots, S_{|S|} - S_{|S|-1}] & \text{if } |S| > 1 \end{cases} $$ $$ sun(S_{1..|S|}, K) = \begin{cases} S & \text{if } K = 1 \\ sun(moon(S_{1..|S|}), K - 1) & \text{if } K > 1 \end{cases} $$ 例如， - $moon([2, 7]) = [5]$。 - $moon([4, 1, 0, 7, 2]) = [-3, -1, 7, -5]$。 - $sun([4, 1, 0, 7, 2], 5) = sun([-3, -1, 7, -5], 4) = sun([2, 8, -12], 3) = sun([6, -20], 2) = sun([-26], 1) = [-26]$。 注意，$sun(S_{1..|S|}, |S|)$ 总是得到一个只有一个元素的序列。 给定一个包含 $N$ 个整数的序列 $A_{1..N}$。称下标 $i = [1..N]$ 是 **热** 的，当且仅当存在一个序列 $A'_{1..N}$ 满足以下条件： - $A'_i \ne A_i$，且 $A'_i$ 是 $[-100\,000, 100\,000]$ 内的整数； - 对于所有 $j \ne i$，有 $A'_j = A_j$； - $sun(A'_{1..N}, N)$ 的唯一元素是 $235\,813$ 的倍数。 你的任务是计算给定 $A_{1..N}$ 中热下标的个数。 例如，在 $A_{1..5} = [4, 1, 0, 7, 2]$ 中有 $3$ 个热下标，即 $\{1, 3, 5\}$。 - $i = 1$，$A'_1 = 30$ → $A'_{1..5} = [30, 1, 0, 7, 2]$ → $sun([30, 1, 0, 7, 2], 5) = [0]$ - $i = 3$，$A'_1 = -78\,600$ → $A'_{1..5} = [4, 1, -78\,600, 7, 2]$ → $sun([4, 1, -78\,600, 7, 2], 5) = [-471\,626]$ - $i = 5$，$A'_1 = 28$ → $A'_{1..5} = [4, 1, 0, 7, 28]$ → $sun([4, 1, 0, 7, 28], 5) = [0]$ 注意，$0$ 和 $-471\,626$ 都是 $235\,813$ 的倍数。另一方面，下标 $i = 2$ 不是热的，因为不存在满足条件的整数 $A'_2 \ne A_2$ 在 $[-100\,000, 100\,000]$ 内，使得 $sun(A'_{1..5}, 5)$ 的唯一元素是 $235\,813$ 的倍数。下标 $i = 4$ 同样不是热的。

输入第一行包含一个整数 $N$（$1 \leq N \leq 100\,000$），表示序列 $A$ 中整数的个数。下一行包含 $N$ 个整数 $A_i$（$-100\,000 \leq A_i \leq 100\,000$），表示整数序列。

输出一行一个整数，表示给定 $A_{1..N}$ 中热下标的个数。

#### 样例 #1 解释 这是题目描述中的例子。 #### 样例 #2 解释 - $i = 1$，$A'_1 = -70$ → $A'_{1..4} = [-70, 20, 30, -40]$ → $sun([-70, 20, 30, -40], 4) = [0]$ - $i = 2$，$A'_2 = 78\,651$ → $A'_{1..4} = [10, 78\,651, 30, -40]$ → $sun([10, 78\,651, 30, -40], 4) = [235\,813]$ - $i = 3$，$A'_3 = -78\,601$ → $A'_{1..4} = [10, 20, -78\,601, -40]$ → $sun([10, 20, -78\,601, -40], 4) = [235\,813]$ - $i = 4$，$A'_4 = 40$ → $A'_{1..4} = [10, 20, 30, 40]$ → $sun([10, 20, 30, 40], 4) = [0]$ 翻译由 DeepSeek 完成