#P13804. [codefestival2017 qualb] Popping Balls

    ID: 13005 传统题 1000ms 256MiB 尝试: 1 已通过: 1 难度: 8 上传者: 标签>CF2400提高+/省选-鸽巢原理双射计数插板法乘法原理加法原理阶乘逆元预处理

[codefestival2017 qualb] Popping Balls

AT_

题目描述

有 A+BA+B 个球排成一行。最左边的 AA 个球被涂成红色,最右边的 BB 个球被涂成蓝色。

你需要进行如下操作:

  • 首先,选择满足 1≤s,t≤A+B1 \leq s, t \leq A+B 的整数 s,ts, t。
  • 然后,重复如下步骤 A+BA+B 次:每一步,你可以从最左边第 11 个、ss 个(如果存在)或 tt 个(如果存在)(均为从 11 开始编号)的球中选一个,把这个球送给“すぬけ君”。

问你有多少种不同的方式把球送给“すぬけ君”?请你输出方案数对 109+710^9+7 取模的结果。

若某个位置第 kk 次送出的球颜色不同,则认为对应的两种方式是不同的。特别地,选择的 s,ts, t 并不会影响方案的区分。另外,同色的球不加区分。

输入格式

输入由一行组成,格式如下:

AA BB

输出格式

输出答案。

输入输出样例 #1

输入 #1

3 3

输出 #1

20

输入输出样例 #2

输入 #2

4 4

输出 #2

67

输入输出样例 #3

输入 #3

7 9

输出 #3

7772

输入输出样例 #4

输入 #4

1987 1789

输出 #4

456315553

说明/提示

限制

  • 1≤A,B≤20001 \leq A, B \leq 2000

样例解释 1

有 33 个红球和 33 个蓝球,共有 2020 种不同的赠送方法,所有情况都可以实现。下面是其中一种操作示例(r 表示红球, b 表示蓝球):

  • 选择 s=3,t=4s=3, t=4。
  • 初始排列为 rrrbbb。
  • 将第 33 个球(r)送出,队列变为 rrbbb。
  • 将第 44 个球(b)送出,队列变为 rrbb。
  • 将第 11 个球(r)送出,队列变为 rbb。
  • 将第 33 个球(b)送出,队列变为 rb。
  • 将第 11 个球(r)送出,队列变为 b。
  • 将第 11 个球(b)送出,队列变为空。

在上述方法中,“すぬけ君”最终获得球的顺序为 rbrbrb。

样例解释 2

有 44 个红球和 44 个蓝球,共有 7070 种赠送方法。其中,bbrrbrbr、brbrbrbr、brrbbrbr 这三种排列无法实现。

由 ChatGPT 5 翻译