题解 AT3576 【Popping Balls】
ywy_c_asm
2019-06-02 10:00:41
组合神题。
首先这题比较奇怪的地方就是你可以在一开始决定$(s,t)$的值，但是我们最终要统计所有的本质不同的最终颜色序列数，我们不能傻乎乎的枚举$(s,t)$然后算。但是注意到只有红蓝两种颜色，而由于我们一直都可以取第一个，所以红色实际上是可以任意取的，关键就在于**当前时刻能否选蓝色**。
那么我们现在就很清楚了$s$和$t$主要是为了取蓝的而设立的，那么我们就不妨先考虑$t$，因为如果$s$能取蓝的那$t$如果可以的话也能取，当球不够$t$个的时候，此时$t$已经没用了，我们到那时再考虑$s$。我们就这样**分阶段**的取考虑。
但是我们该如何确保不重的统计所有的$t$呢？我们不妨就钦定第一个蓝球就必须是在$t$处被取的，因为如果你就不想在确定$(s,t)$的情况下让第一个蓝球在$t$处取到，那么此时的$t$是没有任何意义的，我们肯定对于任意的合法颜色序列都有一种取的方案使得第一个蓝球在某个钦定的$t$被取到（这里我们假设$t$能够为1）。我们发现这样做的话就必须保证在取第一个蓝球之前必须先取$A-(t-1)$个红球，那么这样对于每一个不同的$t$统计出来的颜色序列显然就是不同的，这样好啊，那我们就可以从$[1,A+1]$枚举$t$了（显然$t$不能比$A+1$更大，咱要取的是第一个蓝球）。
现在我们相当于已经有了$t-1$个红球和$B-1$个蓝球，然后由于$t$现在指向的是一个蓝球，那么$t$在不能取任何球之前显然只会取蓝球，所以现在这个阶段是**红球和蓝球可以任意取**的，那么我们这个阶段需要取$B-1$个球才能使得$t$无效，那就可以直接枚举取的这$B-1$个球里有$i$个红球，就$C_{B-1}^i$。
现在$t$挂掉了，我们就不得不考虑$s$的问题了。但是注意到我们现在还没有确定$s$，而我们现在有$t-1-i$个红球和$i$个蓝球，那么我们可以和确定$t$一样的方法来确定$s$，即先取一些红球，然后让剩下的这$i$个蓝球里的第一个在$s$上取就行了，然后直到只剩下$s-1$个就直接都从1取完就行了。
那么我们最终的答案就是：
$ans=\sum_{t=1}^{A+1}\sum_{i=0}^{t-1}C_{B-1}^i\sum_{j=1}^{t-i}\sum_{k=0}^{j-1}C_{i-1}^k$
考虑优化，注意到后面那个$\sum_{j=1}^{t-i}\sum_{k=0}^{j-1}C_{i-1}^k$可以表示为$f(a,b)=\sum_{i=0}^b\sum_{j=0}^iC_{a}^j$的形式，我们可以先搞出一个组合数的行前缀和$g(a,b)=\sum_{i=0}^bC_a^j$，那么$f(a,b)=\sum_{i=0}^bg(a,i)$，那么这题就可以$O(n^2)$做了。
上代码~
```cpp
#include <iostream>
#include <cstdio>
#include <cstring>
#define ll long long
#define p 1000000007
using namespace std;
namespace ywy {
int c[4044][4044], f[4044][4044], g[4044][4044];
inline void pre(int n) {
c[0][0] = 1;
for (register int i = 1; i <= n; i++) {
c[i][0] = 1;
for (register int j = 1; j <= i; j++) c[i][j] = (c[i - 1][j - 1] + c[i - 1][j]) % p;
}
for (register int i = 0; i <= n; i++) {
g[i][0] = c[i][0];
for (register int j = 1; j <= n; j++) g[i][j] = (g[i][j - 1] + c[i][j]) % p;
}
for (register int i = 0; i <= n; i++) {
f[i][0] = g[i][0];
for (register int j = 1; j <= n; j++) f[i][j] = (f[i][j - 1] + g[i][j]) % p;
}
}
void ywymain() {
int A, B;
cin >> A >> B;
pre(A + B);
ll ans = 0;
for (register int t = 1; t <= A + 1; t++) {
for (register int i = 0; i < t; i++) {
if (i == 0) {
ans++;
continue;
}
ans = (ans + (ll)c[B - 1][i] * f[i - 1][t - i - 1]) % p;
}
}
cout << ans << endl;
}
}
int main() {
ywy::ywymain();
return (0);
}
```