P1329 数列

· · 题解

这是一道彻底的数学题

题目化简

有一个长度为 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 的有多少种可能,每一种可能都对应着原题的一种方案.