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

传送门：https://ac.nowcoder.com/acm/contest/9985/B

题意

思路

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

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

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

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

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

$$\sum_{i=1}^n(n-i+1)*C_{n-i+1+m-2}^{m-1}$$

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

$$\sum_{i=1}^ni*C_{n-i+1+m-2}^{m-1}$$

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

两个减一减得：

$$\sum_{i=1}^n(n-i+1)*C_{n-i+m-1}^{m-1}$$

Code(44MS)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
##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();
}

本文作者：jujimeizuo
本文地址： https://blog.jujimeizuo.cn/2021/02/22/2021-nowcoder-hanjia-5-b/
本博客所有文章除特别声明外，均采用 CC BY-SA 3.0 协议。转载请注明出处！