【2021牛客寒假第五场】B-比武招亲（上）排列组合

题意

思路

$考虑最大值和最小值贡献。$

$先看最大值：$
$假设我们选择最大值为x，则剩下m-1个位置只能选不超过x的数字$
$题目表示排完序之后本质不同!$
$所以就是在不超过x的数字中任意重复选择m-1个并且生成不递减序列的个数。$

$没错，n个中选m个数(可重复)且不递减序列个数为C_{n+m-1}^m。请自行百度！$

$x=n时，贡献为n\ast C_{n+m-2}^{m-1}$
$x=n-1时，贡献为(n-1)\ast C_{n-1+m-2}^{m-1}$
…

$所以我们最大值的贡献就是$

$$\sum _{i=1}^n(n-i+1)\ast C_{n-i+1+m-2}^{m-1}$$

$同理，最小值就是m-1个位置必须选择不小于x的数字，贡献就是$

$$\sum _{i=1}^{n}i\ast C_{n-i+1+m-2}^{m-1}$$

$这两个式子是我化简过后的。难点就是不递减序列个数是多少。$

$两个减一减得：$

$$\sum _{i=1}^n(n-i+1)\ast C_{n-i+m-1}^{m-1}$$

Code(44MS)

#include "bits/stdc++.h"

using namespace std;

typedef long long ll;

const int N = 1e6 + 10;
ll f[N], invF[N], inv[N];
void Init()
{
     
    f[0] = f[1] = inv[0] = inv[1] = invF[0] = invF[1] = 1;
    for(int i = 2;i < N; i++)
    {
     
        f[i] = f[i - 1] * i % mod;
        inv[i] = mod - (mod / i) * inv[mod % i] % mod;
        invF[i] = invF[i - 1] * inv[i] % mod;
    }
}

ll C(ll m, ll n)
{
     
    if(m < 0 || n < 0 || n > m)
        return 0;
    ll ans = f[m];
    ans = ans * invF[n] % mod;
    ans = ans * invF[m - n] % mod;
    return ans;
}

//ll quick_pow(ll a, ll b) {
     
//    ll ans = 1;
//    while(b) {
     
//        if(b & 1) ans = ans * a % mod;
//        a = a * a % mod;
//        b >>= 1;
//    }
//    return ans % mod;
//}

void solve() {
     
    Init();
    ll n, m; cin >> n >> m;
    ll ans = 0;
    // C(n + m - 1, m) n个数中选m个不递减个数
    for(ll i = 1;i <= n; i++) {
     
        // cout << "个数：" << C(n - i + 1 + m - 1 - 1, m - 1) << endl;
        ans = (ans + (n - 2 * i + 1) * C(n - i + m - 1, m - 1) % mod) % mod;
    }
    cout << (ans % mod + mod) % mod << endl;
}

signed main() {
     
    solve();
}