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;
}