数列计算 - 题目详情 - CZOJ

ID: 649

传统题

1000ms

256MiB

普及-

上传者:

标签>

算法基础

递归

枚举

题目描述

有一个数列 $a_1,a_2,\ldots,a_n$ ，其中 $a_1=0$ ，永远不变，从第二个数 $a_2$ 开始，它可以是前面的数加 $1$ ，也可以是前面的数减 $1$ 。例如 $n=4$ ，可能的数列有：

$a_1,a_2,\ldots,a_n$	$S=\sum a_i$
$0,1,2,3$	$6$
$0,1,2,1$	$4$
$0,1,0,1$	$2$
$0,1,0,-1$	$0$
$0,-1,0,1$	$0$
$0,-1,0,-1$	$-2$
$0,-1,-2,-1$	$-4$
$0,-1,-2,-3$	$-6$

给出 $n$ 和 $S$ ，问满足条件的数列有多少。

输入格式

输入两个整数 $n,S$ 。

输出格式

输出满足条件的数列的个数。

4 0

数据范围

$1 \le n \le 30$

$1 \le S \le 10^7$