ARC169-A 分析

· · 个人记录

题意

给定整数列 A(A_1, A_2, \cdots, A_N) 与 P(P_2, P_3, \cdots, P_N) (1 \leq P_i \leq i).

有以下操作：

重复以上操作 10^{100} 次，问 A_i 正负性。

分析

根据样例 1 有推导：

第一次操作后：

\begin{aligned} A_1 = A_i + A_2 \\ A_2 = A_2 + A_3 \\ A_3 = A_3 + A_4 \\ A_4 = A_4 \end{aligned}

第二次操作后：

A_1 = A_1 + A_2 = A_1 + 2A_2 + A_3 \\ A_2 = A_2 + 2A_3 + A_4 \\ A_3 = A_3 + 2A_4 \\ A_4 = A_4 \end{aligned}

第三次操作后：

A_1 = A_1 + 3A_2 + 3A_3 + A_4 \\ A_2 = A_2 + 3A_3 + 3A_4 \\ A_3 = A_3 + 3A_4 \end{aligned}

第 10^{100} 次（在本问题下可以看作趋向正无穷）操作后：

\lim_{n\rightarrow \infty} A_1 = n\times A_2 \\ \lim_{n\rightarrow \infty} A_2 = n \times A_3 \\ \lim_{n\rightarrow \infty} A_3 = n\times A_4 \end{aligned}

显然，A_3 的正负性由 A_4 决定。同理 A_2 的正负性由 A_3 决定，A_1 的正负性便是由 A_2 决定。

于是确定 A_1 的正负性就变成了从 A_n 开始向上的一条推导的长链。

但是我们需要考虑 P 值重复，例如 A_2 = A_2 + A_3 + A_4 的情况。实际上这并不是问题，因为很明显可以将 A_3 + A_4 视作整体处理。

因此我们的策略便是，构建出一颗以 1 为根的树，从下到上推导每一层的正负性，低一层的正负性决定更高一层的。