# B 比武招亲(上)

image-20210306171517109

# 题目大意

给定 n,m,每次从 1-n 中挑选出 m 个数,可以重复挑选,挑选出的数的贡献值等于排序后最大值减去最小值,挑选的序列不同当且仅当两个序列排序后不同,求所有可能的序列的总贡献值?

# 解法

可以枚举贡献值,差值一共有 n-1 种,差值固定了,也就是在 m-2 个空位中随意放置 [min,max] 的数,这里有一个坑,也不是随便放的,因为要求排过序后序列不同,也就是放置要求是单调不减,于是可以把 + 1 看成一个隔板,就是在 m-2+1 个隔板中放置 d (差值) 个隔板,可是隔板可以连续放置,所以放置一个隔板后空位就会增多!所以答案不是 C (m-1,d),雨巨的想法 NB,考虑每一个隔板的左面带有一个空位,那么所有的隔板放完后空位就增加到了 m-1+d 个,在这些空位中放进去 d 个隔板,这个时候隔板就不能连续放了,因为每一个隔板左面都带有一个空位,所以每一个隔板左面都必须至少有一个空位,那最左面也不能放了,所以空位变成了 m-1+d-1,答案就变成了从 m-2+d 个空位中放置 d 个隔板,隔板不能连续放,C (m-2+d,d),到这里题目就做出来一大半了,组合数复杂度为 O (n),这里的 n 和 m 都是 1e5,所以每次都算一遍组合数时间就是 O (n2) 级别的,必定超时,考虑优化组合数,先算出差值为 1 的答案,然后算差值为 2 的组合数时在差值为 1 的基础上 * 分子 * 分母的逆元可以把组合数的时间去掉,时复 O (n)

# CODE

#include <bits/stdc++.h>
#define debug freopen("in.txt","r",stdin); freopen("out.txt","w",stdout)
#define ios ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int MAXN=1e6+100;
const int MOD=998244353;
const int INF=0x3f3f3f3f;
const int SUB=-0x3f3f3f3f;
const int eps=1e-4;
const double E=exp(1);
const double pi=acos(-1);
ll ksm(ll a,ll b){
	ll ret=1;
	while(b){
		if(b&1) ret=ret*a%MOD;
		a=a*a%MOD;
		b>>=1;
	}
	return ret%MOD;
}
ll inv(ll x){
	return ksm(x,MOD-2)%MOD;
}
int n,m;
int main(){
	ios;
	cin>>n>>m;
	if(n==1 || m==1){  // 特判特殊情况
		cout<<0<<'\n';
		return 0;
	}
	ll now=m-2+1,ans=now*(n-1)%MOD;// 先算出差值为 1 的答案
	for(int i=2;i<=n-1;i++){  // 之后在上一个差值的基础上算这个差值的答案
		now=now*(m-2+i)%MOD*inv(i)%MOD;  // 乘上分子和分母的逆元
		ans=(ans+now*i%MOD*(n-i)%MOD)%MOD;  // 现在 now 表示这个差值的种类数记得乘上差值和这个差值下可以取到的区间数量
	}
	cout<<ans<<'\n'; 
	return 0;
}