趣题: 数列和的最小值

题目大意 #

$2006$ 个不等于 $119$ 的数构成的数列, 满足任意连续子区间之和都不等于 $119$ , 求数列和的最小值.

解答 #

考虑 $119$ 个数 $a_1, a_2, …, a_{119}$, 其假设前缀和数列 $s_1, s_2, …, s_{119}$ 不存在 $119$ 的倍数, 则由抽屉原理可以得到 $\exist 1\leq i< j\leq 119, s.t.\ s_i \equiv s_j\ mod\ 119$ , 作差得到 $\sum_{k=i + 1}^{j}a_k\equiv 0\ mod\ 119$ , 综上任意 $119$ 的数组成的数列必定存在连续子区间和为 $119$ 的倍数. 由题意知不能和不能为 $119$ , 则至少为 $119 × 2 = 338$ . 因为 $2006 = 119 × 16 + 102$ , 故数列和的最小值至少为 $338 × 16 + 102 = 3910$ . 下面给出一个合法的构造: 取 $a_{119}, a_{338}, …, a_{1904} = 120$ , 其余数都为 $1$ . 故最小值为 $3910$