AT_code_festival_2017_qualb_e Popping Balls 题解

题意：

有 $A+B$ 个球排成一行，其中左边 $A$ 个是红色的，右边 $B$ 个是蓝色的。

你可以选定一对整数 $(s,t)~(1\le s<t\le A + B)$，然后重复进行以下操作直到球被取完：

将第一个球或第 $s$ 个球或第 $t$ 个球（当前球的数量必须够才能执行）拿出来。

求最后拿出来的球的颜色序列有多少种不同方案数。答案对 $10^9+7$ 取模。

方案不同当且仅当存在某一次取出的球的颜色不同。

输入：$A,B$ 。输出：一行答案。数据范围：$A, B \leq 2000$。

非常有趣的计数题。

注意到每次在 $1$ 处拿球时，$s,t$ 相当于向右移动一格；而从 $s$ 处拿球，$t$ 相当于向右一格。

那么当 $s,t$ 均可用时，

若 $s$ 处是红球，那么从 $0$ 处拿球一定不劣于从 $s$ 处拿球。
若 $s$ 处是蓝球，那么从 $t$ 处拿球一定不劣于从 $s$ 处拿球。

因此只有 $t$ 不可用时才会从 $s$ 拿球。（以上的“不劣于”筛掉了很多重复且复杂的情况）

考虑判断一个状态是否合法。当拿到第一个蓝球时，$t$ 放在蓝球的队首一定不劣。

而之后的 $B$ 次拿球，每次都有两种合法选择，知道 $B$ 次拿完后 $t$ 失效。然后就到 $s$ 了，处理方式类似。

因此考虑钦定从 $s,t$ 处拿走的第一个球均为蓝球，根据上面的推导这样是不重不漏的。

枚举从 $t$ 处拿走了 $i~(1 \le i < B)$ 个蓝球，从 $s$ 处拿走了 $j~(1\le j \le B - i)$ 个蓝球，

那么从 $t$ 处拿球的过程中 $0$ 拿走了 $B-i$ 个红球，从 $s$ 处拿球的过程中 $0$ 拿走了 $B-i-j$ 个红球，

还剩下 $A-2 B+2 i+j$ 个红球是从 $0$ 处直接拿的，要放在 $s$ 拿球过程后和 $t$ 拿球过程后这两段之间

在加上 $i=B$ 即蓝球是一整段的 $A+1$ 种情况，那么总方案数为

$\mathrm{Ans}=(A+1) + \sum_{i=1}^{B-1}\sum_{j=1}^{B-i}\binom{B-1}{i-1}\binom{B-i-1}{j-1}\binom{A-2B + 2i+j+2}{2}$

时间复杂度 $\mathcal{O}(n^2)$

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
const int mod = 1e9 + 7;
void up(int &x, int y) { x < y ? x = y : 0; }
void down(int &x, int y) { x > y ? x = y : 0; }
void add(int &x, int y) { (x += y) >= mod ? x -= mod : 0; }
#define rep(i, a, b) for(int i = (a), i##END = (b); i <= i##END; i++)
#define Rep(i, a, b) for(int i = (a), i##END = (b); i >= i##END; i--)
#define N ((int)(5e3 + 15))

int C[N][N];
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    int A, B; cin >> A >> B;
    rep(i, 0, N - 5) C[i][0] = 1;
    rep(i, 1, N - 5) rep(j, 1, i) add(C[i][j] = C[i - 1][j - 1], C[i - 1][j]);
    int res = 0;
    rep(i, 1, B - 1) rep(j, 1, B - i)
    {
        const int _1 = C[B - 1][i - 1] * C[B - i - 1][j - 1] % mod;
        const int _2 = C[max(0ll, A - 2 * B + 2 * i + j + 2)][2]; add(res, _1 * _2 % mod);
    }
    cout << (res + (A + 1)) % mod << '\n';
    return 0;
}