有一个数列A1,A2,…,An(1≤n≤30),其中A1=0,永远不变,从第二个数A2开始.有一个数列A1,A2,…,An(1≤n≤30),其中A1=0,永远不变,从第二个数A2开始,它可以是前面的数加1,也可以是前面的数减1.例如n=4,可能

Question

有一个数列A1,A2,…,An(1≤n≤30),其中A1=0,永远不变,从第二个数A2开始.
有一个数列A1,A2,…,An(1≤n≤30),其中A1=0,永远不变,从第二个数A2开始,它可以是前面的数加1,也可以是前面的数减1.例如n=4,可能的数列有：
0 1 2 3 其和S=6（即4个数的和）
0 1 2 1 S=4
0 1 0 1 S=2
0 1 0 －1 S=0
0 －1 0 1 S=0
0 －1 0 －1 S=－2
0 －1 －2 －1 S=－4
0 －1 －2 －3 S=－6
给出n和S,问满足条件的数列有多少.
【输入描述】 2个整数
【输出描述】 一个整数(满足条件的数列的个数)
【输入样例】 4 0

Answer 1

首先从第二项起,每个都有1 和-1.所以 数列总共有2^(N-1）个
那么S有多少种呢,因为如果都取1的话,那么S=N(N-1)/2 ,相反-1的话为S=-N(N-1)/2 所以每个相差2的S都可满足
因为1 和-1相差2,所以总共的个数有 为首相是-N(N-1)/2,公差是2,未项为N(N-1)/2 数列的项数
即 S个数为 N(N-1)/2+1个