來(lái)一發(fā)B題的組合數(shù)學(xué)的解法
首先考慮比較樸素的做法，枚舉區(qū)間l,r枚舉這個(gè)區(qū)間的值，然后用隔板法計(jì)數(shù)，復(fù)雜度O(n^3)
我們用公式表示（來(lái)自官方題解）

我們發(fā)現(xiàn)第一個(gè)式子和j沒(méi)關(guān)系，第二個(gè)式子和i沒(méi)關(guān)系
操作一個(gè)這個(gè)公式變成

那么我們只需要預(yù)處理出 計(jì)為num[i][k]
那么最后答案的計(jì)算可以變成

這里如何處理num數(shù)組的時(shí)候可以使用前綴和的方式，

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