自动搬运

查看原文

来自洛谷，原作者为

	Hiynyuan 我唯一所知，即我无所知

搬运于2025-08-24 21:23:49，当前版本为作者最后更新于2021-07-27 16:34:05，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

这是一道彻底的数学题

题目化简

有一个长度为 $n$ 的数列,第一个数为 $0$ ,每两位的差的绝对值为 $1$ ,和为 $s$ ,输出有多少种方案并输出 $100$ 种以内的所有方案.

主要思路

设每两位之间的差为 $x_i$( $1$ 或 $-1$ ) ,则:

$a_1=0$

$a_2=a_1+x_1=x_1$

$a_3=a_2+x_2=x_1+x_2$

$a_4=a_3+x_3=x_1+x_2+x_3$

以此类推,可得:

$a_i=x_1+x_2+...+x_\text{i-1}$

则:

$s=a_1+a_2+...+a_n=(n-1)x_1+(n-2)x_2+...+x_\text{n-1}$

所以，从这开始就分成了两种方法。

法一

模拟每一个 $x$ ,如果结果等于 $s$ 就得到一种方案.

法二

假设所有的 $x$ 都为 $1$ 可得:$s=\frac{n(n-1)}{2}$.

设为 $-1$ 的 $x$ 有$y$个,

继续化简可得: $s=\frac{n(n-1)}{2}-2y$.

求出 $y$ 之后,问题就变成了从 $n-1$ 到 $1$ 之中,和为 $y$ 的有多少种可能,每一种可能都对应着原题的一种方案.