题解 AT3576 【Popping Balls】

Yajnun · 2019-09-17 01:08:08 · 题解

组合计数

据题意，每当从0拿球，s、t都会右移一格；从s处拿球，t会右移一格。

当s，t都存在场上时，若s处是红球，从0处拿球一定不劣于从s处拿球；若s处是蓝球，从t处拿球一定不劣于从s处拿球；所以，只有t出队后，s处才会有球被拿。

考虑判断一个状态是否合法。当拿到第一个蓝球时，t选在蓝球的队首一定不劣，这会之后B次拿球，每次都有两种合法选择，直到B次拿完后t出队。对s的处理同理。

枚举从t拿走了i个蓝球，从s拿走了j个蓝球，两次都固定第一个拿的是蓝球，则从t拿走了B-i个红球，从s拿走了B-i-j个红球，还剩下A-2B+2i+j个红球要放在从0处拿球的三段中（从s拿球前，从s拿球后，从t拿球后），则可用隔板法计算贡献为C_{B-1}^{i-1}*C_{B-i-1}^{j-1}*C_{A-2B+2i+j+2}^{2}，最后加上蓝球序列为一段的方案数A+1。

代码：

#include<cstdio>
#include<algorithm>
#include<queue>
#include<cmath>
#include<iostream>
#include<cstring>
#define ll long long
#define maxn 5005

#define p 1000000007
#define re(i,a,b) for(int i=a;i<=b;i++)
#define for_edge(x) for(int i=head[x];i;i=e[i].nxt)
using namespace std;
inline int read(){char c=getchar();int f=1;int ans = 0;while(c>'9'||c<'0'){if(c=='-')f=-f;c=getchar();}while(c<='9'&&c>='0'){ans =ans*10+c-'0';c=getchar();}return ans*f;}
//_____________________________________________________________________________________________________
ll _C[maxn][maxn];
inline ll C(int n,int m)
{
    return (n>=0 && m>=0) ? _C[n][m] : 0;
}
int main()
{
    int A = read() , B = read();;
    _C[0][0] = 1;
    re(i,0,5000)
        re(j,0,i)
        {
            _C[i][j] %= p;
            _C[i+1][j] += _C[i][j];
            _C[i+1][j+1] += _C[i][j];
        }
    ll ans = 0;
    re(i,1,B)
        re(j,1,B-i)
                ( ans += C(B-1,i-1)*C(B-i-1,j-1)%p * C( A-2*B+2*i+j+2,2 ) )%=p;

    (ans += A+1)%=p;
    printf("%lld\n",ans);
    return 0;
}