D. 等价表达式

    传统题 1000ms 256MiB

等价表达式

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

说明

本题不再提供附加样例文件。

题目描述

已知一个仅包含减号的表达式 x1−x2−…−xnx_1 - x_2 - … - x_n。

现在让你在表达式中添加 m 对括号,得到新的表达式。

括号可以嵌套。当然,你要保证添加的括号是合法的。

比如,以下是一些不合法的操作:

  • x1x_1 的左侧添加右括号

  • xnx_n 的右侧添加左括号

  • 减号的左侧紧邻位置添加左括号

  • 减号的右侧紧邻位置添加右括号

  • 左括号的总数量不等于右括号的总数量

  • ……

显然,不同的添加方式,会得到形式不同的表达式。

例如,当 n = 3, m = 2, 即在表达式 x1−x2−x3x_1-x_2-x_3 中添加 2 对括号,可以得到以下的表达式:

  • ((x1))−x2−x3((x_1))-x_2-x_3
  • (x1)−(x2−x3)(x_1)-(x_2-x_3)
  • x1−((x2−x3))x_1-((x_2-x_3))
  • ……

对于两个表达式,如果对于任意的 nn 元组 (x1,x2,…,xn)(x_1, x_2, …, x_n) 两个表达式的值都是相同的,则称两个表达式是等价的,否则就是不等价的。

例如,上面所述的 ((x1))−x2−x3((x_1))-x_2-x_3 和 (x1)−(x2−x3)(x_1)-(x_2-x_3) 是不等价的,而 (x1)−(x2−x3)(x_1)-(x_2-x_3) 和 x1−((x2−x3))x_1-((x_2-x_3)) 是等价的。

现在的问题是,合法地添加 m 对括号后,你最多可能得到多少个互不等价的表达式?

输入格式

一行,包含两个整数 n,mn, m。

输出格式

一行,一个整数,表示答案。

样例1输入

3 1

样例1输出

2

样例1解释

n=3, m=1,可以得到的新表达式有 6 个:

(x1)−x2−x3(x_1)-x_2-x_3

x1−(x2)−x3x_1-(x_2)-x_3

x1−x2−(x3)x_1-x_2-(x_3)

(x1−x2)−x3(x_1-x_2)-x_3

(x1−x2−x3)(x_1-x_2-x_3)

x1−(x2−x3)x_1-(x_2-x_3)

其中前 5 个都是等价的,而他们与最后一个都是不等价的。

样例2输入

100 40

样例2输出

316912650051316086760499818118

数据范围

30% 的数据:1≤n,m≤101 ≤ n, m ≤ 10。

70% 的数据:1≤n,m≤501 ≤ n, m ≤ 50。

100% 的数据:1≤n,m≤1001 ≤ n, m ≤ 100。

2026-01-24

未参加
状态
已结束
规则
OI
题目
4
开始于
2026-1-24 7:30
结束于
2026-1-24 12:00
持续时间
4.5 小时
主持人
参赛人数
20