2021牛客寒假算法基础集训营5 B.比武招亲(上)

81 阅读 0 评论 54 点赞

我是靠谱客的博主潇洒台灯，最近开发中收集的这篇文章主要介绍2021牛客寒假算法基础集训营5 B.比武招亲(上)，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

B.比武招亲(上)

题目链接：https://ac.nowcoder.com/acm/contest/9985/B

题目描述：

众所周知，天姐姐只喜欢天下最聪明的人，为了找到这样的人，她决定比武招亲！

只见天姐姐在榜上留下了这样一道问题，谁做出来了就可以俘获她的芳心！

爱慕天姐姐已久的泽鸽鸽问询赶来，只见榜上写着：

给定 n,m，定义一种序列，构造方法如下：

1.在 [1,n]中任意选择 m 次，得到了 m 个整数（显然数字可能相同）;

2.将选出的 m 个数字排序之后得到一个序列{a1,a2,…,am}。

定义一个序列的贡献为 max{a1,a2,…,am}−min{a1,a2,…,am}，求所有本质不同的序列的贡献和。

为了防止结果过大，将答案为 998244353 取模后输出。

(对于两个序列长度为m的序列 A、B，若∃i∈[1,m]，Ai≠Bi，则序列 A、B 本质不同）

泽鸽鸽心有余而力不足，而你作为他最好的基友决定帮助泽鸽鸽俘获美人心！

现在，这个重任就交给你啦！

输入描述：

一行输入两个正整数 n，m

【数据规模与约定】

1 <= n, m <= 5*10^5

输出描述：

一行一个整数，为答案对 998244353 取模后的结果。

示例1：

输入
3 2
输出
4
说明

本质不同的序列有如下几种：1 1、2 2、3 3、1 2、1 3、2 3，贡献为 0+0+0+1+2+1=4。

解题思路：

隔板法
贡献是最大值-最小值（一个序列的最大值和最小值确定之后，其他数在此范围内任意选）

例如：
max=10,min=1
max=11,min=2
max=12,min=3
……方法数相同

枚举差值x，当max-min=x时，min从1~n-x取值，共有n-x种，min到max之间是一个单调不减的序列(已排序)，中间共有m-2个数，把每次数字加一看做一个隔板(隔板的实际意义)，m-3个空位放d个隔板，强制给每一个隔板自带一个空位(值得注意的是：第一个隔板只能以第2位置开始放隔板，否则自带的空位就芜湖lia因此首位无法插隔板。)因此m+d个空位放d个隔板也就是C(d,m+d-2)。

代码如下：

#include<algorithm>
#include<iostream>
#include<cstdio>
using namespace std;
#define ll long long
const ll mod=998244353;
ll qsm(ll a,ll b){
	ll res=1;
	while(b){
		if(b&1)
			res=(res*a)%mod;
		a=(a*a)%mod;
		b>>=1;	
	}
	return res;
}
int main(){
	ll n,m;
	scanf("%lld%lld",&n,&m);
	ll ans=0;
	ll x=m-1;
	for(ll i=1;i<n;i++){
		ans=(ans+i*x%mod*(n-i))%mod;
		x=x*(m+i-1)%mod*qsm(i+1,mod-2)%mod;
	}
	printf("%lldn",ans);
	return 0;
}