OrBiTal (easy)

一个粒子增加的强度总和为 $K^2$。设 $S=\sum A_i$，只需检查满足 $K^2\mid S$ 的候选强度。粒子的峰值为 $K$，因此还必须满足 $K\leq\max A_i$。

固定 $K$，从左到右扫描。扣除之前已经开始的三角形贡献后，当前位置的剩余值就等于从这里开始的三角形数量，因为三角形最左端的系数是 $1$。如果需要负数个三角形，或者剩余空间不足 $2K-1$ 时仍需开始新的三角形，则不可行。

令 $A_0=A_{-1}=0$，计算 $C_i=A_i-2A_{i-1}+A_{i-2}$。设 为从位置 开始的三角形数量，将左侧范围外的 视为 ，则可从左到右计算

$$X_i=C_i+2X_{i-K}-X_{i-2K}。$$

检查 $0\leq X_i\leq A_i$，并在 $i>N-2K+2$ 时要求 。

设候选数量为 $D$，时间复杂度为 $O(ND+N)$，空间复杂度为 $O(N)$。子任务 1 可以检查所有 $K\leq10$，时间为 。子任务 2 可以不使用总和筛选，逐个检查所有强度，得到 解法。

证明

考虑最左侧尚未匹配的位置 $i$。从更后面开始的三角形不会影响它。扣除此前三角形的贡献后，剩余部分只能由从 $i$ 开始的三角形填满。由于首项系数为 $1$，数量被唯一确定。重复这个过程不会漏掉任何可行解。

三角形的二阶差分在起点为 $1$，在其后 $K$ 个位置为 $-2$，在其后 个位置为 ，所以递推式恰好计算出被强制的数量。如果所有数量非负且起点合法，那么每个完整三角形都在区间内。生成序列和目标序列具有相同的左侧边界值和二阶差分，因此每个位置都相等。

Solution written by GPT6