[CODE FESTIVAL 2017 qual B – E] Popping Balls

E – Popping Balls

为了使得计数不重不漏,对于每个$s$和$t$,我们只将在$s$和$t$只取蓝球并且尽量早取蓝球的序列计入答案。

这样的话取球就可以分为以下几个部分。

此刻$t$上是红球,从$1$一直取直到$t$上出现蓝球,共取走$A-t+1$个红球。当前还剩$t-1$个红球,$B$个蓝球

此刻$t$上有了蓝球,取走一个蓝球。当前还剩$t-1$个红球,$B-1$个蓝球

取走$a$个红球,$b$个蓝球,使得$t$上无球,则$a+b=B-1$。此刻剩下$t-1-a$个红球,$B-1-b=B-1-(B-1-a)=a$个蓝球。

取走$t-1-a-s+1 = t-a-s$个红球,使得$s$上出现蓝球。此刻剩下$t-1-a-(t-a-s) = s-1$个红球,$a$个蓝球。

从$s$上取走一个蓝球,此刻还剩$s-1$个红球和$a-1$个蓝球。

取走$c$个红球,$d$个蓝球,使得$t$上无球,则$c+d = a-1$。剩下的其他球从$1$按顺序取掉就好了。

所以我们现在可以枚举$t, a, s, c$求解,答案就是
$$\sum\limits_{t=1}^{A+1}\sum \limits_{a=0}^{\min(B-1, t-1)}\sum \limits_{s=1}^{t-a}\sum \limits_{c=0}^{\min(s-1, a-1)}{B-1\choose a}\cdot {a-1\choose c}$$

设$s_{n, m} = \sum \limits_{i=0}^{m}\sum \limits_{j=0}^{i}{n\choose j}$,则上式即为
$$\sum\limits_{t=1}^{A+1}\sum \limits_{a=0}^{\min(B-1, t-1)}{B-1\choose a}\cdot s_{a-1, t-a-1}$$

#include <iostream>
#include <cstdio>

#define MX 2010
#define MOD 1000000007

int A, B, C[MX][MX], s[MX][MX];

int main(){
    for(int i = 0; i < MX; i++){
        C[i][0] = s[i][0] = 1;
        for(int j = 1; j <= i; j++)
            C[i][j] = (C[i-1][j] + C[i-1][j-1]) % MOD;
        for(int j = 1; j < MX; j++)
            s[i][j] = (s[i][j-1] + C[i][j]) % MOD;
        for(int j = 1; j < MX; j++)
            s[i][j] = (s[i][j-1] + s[i][j]) % MOD;
    }
    scanf("%d%d", &A, &B);
    int ans = 0;
    for(int t = 1; t <= A+1; t++){
        ans++;
        for(int a = 1; a < std::min(t, B); a++)
            ans = (ans + 1ll * C[B-1][a] * s[a-1][t-a-1] % MOD) % MOD;        
    }
    printf("%d\n", ans);
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注