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

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
#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;
}