题解 | #Bheith i ngra le#

来一发B题的组合数学的解法
首先考虑比较朴素的做法，枚举区间l,r枚举这个区间的值，然后用隔板法计数，复杂度O(n^3)
我们用公式表示（来自官方题解）

我们发现第一个式子和j没关系，第二个式子和i没关系
操作一个这个公式变成

那么我们只需要预处理出 计为num[i][k]
那么最后答案的计算可以变成

这里如何处理num数组的时候可以使用前缀和的方式，

num[i][k] = pre[n][k] - pre[i-1][k]

Code:

ll fun[maxn],inv[maxn];
ll C(ll n,ll m) {
    if(n<m) return 0;
    if(m==0) return 1;
    if(n==m) return 1;
    return (fun[n]*inv[n-m]%mod)*inv[m]%mod;
}
ll qpow(ll a,ll b) {
    ll ans=1;
    while(b) {
        if(b&1) ans=ans*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return ans;
}
void yu() {
    inv[1]=1,fun[1]=1,fun[0]=1;
    for(int i=2; i<maxn; i++) fun[i]=fun[i-1]*i%mod;
    inv[maxn-1]=qpow(fun[maxn-1],mod-2);
    for(int i=maxn-2; i>=0; i--) inv[i]=inv[i+1]*(i+1)%mod;
}
ll n,m,pre[2020][2020],num[2020][2020];
int main() {
    ios::sync_with_stdio(false);
    cin>>n>>m;
    yu();
    for(int k=1 ;k<=m; k++)
    {
        for(int j=1 ;j<=n ;j++)
        {
            pre[j][k] = pre[j-1][k] + C(n-j+k-1,k-1);
            pre[j][k]%=mod;
        }
    }
    for(int k=1 ;k<=m ; k++)
    {
        for(int i=1 ;i<=n ;i++)
        {
            num[i][k] = pre[n][k] - pre[i-1][k];
            num[i][k]%=mod;
        }
    }
    ll ans=0;
    for(int i=1 ;i<=n ;i++)
    {
        for(int k=1 ;k<=m ;k++)
        {
            ans = (ans+C(i+k-2,k-1)*num[i][k])%mod;
        }
    }
    cout<<(ans+1)%mod<<endl;
    return 0;
}