比武招亲（上）

思路

先特判 $m=1$ 的情况，此时答案为0
我们可以枚举 $max\{ a_{1},a_{2},...,a_{m} \}-min\{ a_{1},a_{2},...,a_{m} \}$ 的值 $[1,n-1]$ (0可以忽略)，并可知一共有n-1~1种情况
因为最大值和最小值已经定了，那么其他的数在这两个值之间就行了
我们可以枚举m,有多少种情况
打表+oeis 可得
当 $m=2$ 时，即枚举0个数，可得 $1,1,1,1,...$ 推出 $C^0_{i}$
当 $m=3$ 时，即枚举1个数，可得 $2,3,4,5,...$ 推出 $C^1_{i+1}$
当 $m=4$ 时，即枚举2个数，可得 $3,6,10,15,...$ 推出 $C^2_{i+2}$
当 $m=5$ 时，即枚举3个数，可得 $4,10,20,...$ 推出 $C^3_{i+3}$
很容易看出规律

所以最终答案为 $ans = \sum_{i = 1} ^ {n - 1} i * (n - i) * C_{m + i - 2}^{m - 2}$

如果T的话，预处理下逆元

代码

// Problem: 比武招亲（上）
// Contest: NowCoder
// URL: https://ac.nowcoder.com/acm/contest/9985/B
// Memory Limit: 524288 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp(aa,bb) make_pair(aa,bb)
#define _for(i,b) for(int i=(0);i<(b);i++)
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,b,a) for(int i=(b);i>=(a);i--)
#define mst(abc,bca) memset(abc,bca,sizeof abc)
#define X first
#define Y second
#define lowbit(a) (a&(-a))
#define debug(a) cout<<#a<<":"<<a<<"\n"
typedef long long ll;
typedef pair<int,int> pii;
typedef unsigned long long ull;
typedef long double ld;
const int N=500010;
const int INF=0x3f3f3f3f;
const int mod=998244353;
const double eps=1e-6;
const double PI=acos(-1.0);

ll n,m,ans;
ll inv[N];

ll C(ll n,ll m,ll p){
    ll ans = 1;
    for(ll i=1;i<=m;i++){
        ans = ans * (n-m+i) % p;
        ans = ans * inv[i] % p;  //求i模p的逆元 
    }
    return ans;
}    

ll res[N];//res[i]=C(i+m-2,m-2,mod)

void solve(){
    cin>>n>>m;
    if(m==1){
        cout<<"0\n";
        return;
    }
    inv[1]=1;
    for(int i=2;i<=5e5;i++) inv[i]=(mod-(mod/i))*inv[mod%i]%mod;
    res[1]=C(1+m-2,m-2,mod);
    rep(i,1,n-1){
        if(i>1) res[i]=res[i-1]*(i+m-2)%mod*inv[i]%mod;
        ans+=i*(n-i)%mod*res[i]%mod;
        ans%=mod;
    }
    cout<<ans<<"\n";
}


int main(){
    ios::sync_with_stdio(0);cin.tie(0);    
//    int t;cin>>t;while(t--)
    solve();
    return 0;
}