luogu#P1754. 球迷购票问题

    ID: 5812 远端评测题 1000ms 125MiB 尝试: 3 已通过: 1 难度: 3 上传者: 标签>动态规划dp数论数学卡特兰Catalan

球迷购票问题

题目描述

盛况空前的足球赛即将举行。球赛门票售票处排起了球迷购票长龙。

按售票处规定,每位购票者限购一张门票,且每张票售价为 5050 元。在排成长龙的球迷中有 nn 个人手持面值 5050 元的钱币,另有 nn 个人手持面值 100100 元的钱币。假设售票处在开始售票时没有零钱。试问这 2n2n 个球迷有多少种排队方式可使售票处不致出现找不出钱的尴尬局面。

例如当 n=2n=2 时,用 A 表示手持 5050 元面值的球迷,用 BB 表示手持 100100 元钱的球迷。则最多可以得到以下两组不同的排队方式,使售票员不至于找不出钱。

  • 第一种:[A,A,B,B]\mathtt{[A,A,B,B]}
  • 第二种:[A,B,A,B]\mathtt{[A,B,A,B]}

对于给定的 nn,计算 2n2n 个球迷有多少种排队方式,可以使售票处不至于找不出钱。

输入格式

一个整数,代表 nn 的值。

输出格式

一个整数,表示方案数。

2

2

提示

数据范围及约定

对于全部数据,0n200 \le n \le 20