2021牛客寒假算法基础集训营5 B 比武招亲（上）

106 阅读 0 评论 70 点赞

我是靠谱客的博主神勇煎饼，这篇文章主要介绍2021牛客寒假算法基础集训营5 B 比武招亲（上），现在分享给大家，希望可以做个参考。

题目链接

题目描述

B 比武招亲

思路

选取的序列a可能的贡献有 0,1,2,3,…,n-1。

设a的贡献为d。
贡献为d的序列有 [1,…,1+d], [2,…,2+d]… (共有n-d个这样的序列)

对贡献为d的序列a进行分析。
如果a的第一位为v，最后一位就为v+d。(因为a为非递减数列)
剩余m-2个地方需要填充。

问题就转变为，将 [v,v+1,v+2,…,v+d] 中的m-2个数字(可以重复，但序列需要是非递减数列)填入序列，求本质不同的序列个数。

用到的知识点为隔板法

举例说明一下:

将[1,2,3]中的6个数字填入序列，求本质不同的序列(非递减)个数。

设序列为[a,b,c,d,e,f]，将2个板子插入序列中，可以得到其中一个为[a,b|c,d,e|f]

将第一个隔板左边的序列[a,b]视为[1,1]
将第一个隔板和第二个隔板之间的序列[c,d,e]视为[2,2,2]
将第二个隔板右边的序列[f]视为[3]

如果[1,2,3]中每个数字至少挑出来一个的话，结果为 $C^{2}_5$
因为挑出来的个数可以为0，可以当做增加了3个可放置隔板的位置，结果为 $C^{2}_{5+3}$

如果不是很理解的话，可以将这个问题视为盒子问题来考虑，相当于将6个小球放在3个盒子里面，用2个隔板将小球分开。
如果每个盒子里面至少有一个小球的话，结果为 $C^2_5$ (有5个地方可以放隔板)
如果盒子里面的小球个数可以为0的话，将原本盒子里面小球个数视为-1(至少一个就变成了可以是0个)，需要放置的小球个数就变成6+3了，结果为 $C^2_{5+3}$

AC的代码

复制代码

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>
#define int long long
using namespace std;

const int N = 1e7, mod = 998244353;
int fac[N];

// 快速幂 
int power(int a, int b){
    int res = 1;
    while(b){
        if(b & 1) res = res * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return res;
}

// 求逆元 
int inv(int a){
	/*
	因为 x^(p-1) % p = 1(费马小定理)
    所以 [x^(p-2) * x] % p = 1
     x^(p-2) 相当于 x 的逆元
	*/
	return power(a, mod - 2);
}

// 对阶乘预处理 
void f(){
	fac[0] = 1;
	fac[1] = 1;
    for(int i = 2; i <= N; i++)
        fac[i] = fac[i - 1] * i % mod;
}

// C^a_b
int C(int a, int b){
	return fac[b] * inv(fac[b - a]) % mod * inv(fac[a]) % mod;
}

signed main(){
	f();
	int n, m;
	cin>>n>>m;
	int res = 0;
	for(int d = 1; d <= n - 1; d++){
		res += (n - d) * C(d, (m - 3) + (d + 1)) % mod * d % mod;

		res = res % mod;
	}
	cout<<res;
}