比武招亲（上）

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

解题思路

所有可能的序列中，最大值最小值之差d满足0<=d<n，分别求每一种情况所有可能的序列再相加，就可以得到最终的结果。对于每一种差值d的取值，最小值为x，最大值为x+d，又有(n-d)种情况，这(n-d)种情况可能出现的序列次数相同，只需计算一个即可，以下分析一种情况。

当差值为d，最小值为1，最大值为d+1时，还需从1~d+1中选择(m-2)个数字，此时有 种选法，其中(m-2)是定值，求组合数可以预处理。

下面证明：将m个小球放入n个盒子中，盒子可以为空，也可以不放，有 种放法。
以n=10,m=6为例，用隔板法证明
|●●| | | |●●●| | |●| |
两个隔板之间可以看做是一个盒子，●代表小球，可以发现除了最左边和最右边的挡板不动，剩余的挡板和小球的位置不固定，可以模拟所有情况，有n+m-1个位置，m个小球，因此有 种放法。
以上证明解释了为什么上面有 种情况。

AC代码

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const ll mod=998244353;
const int N=1000010;
ll c[N];

ll ksm(ll a, ll b)  //快速幂
{
    ll ans=1%mod;
    for(;b;b>>=1)
    {
        if(b&1) ans=(ll)ans*a%mod;
        a=(ll)a*a%mod;
    }

    return ans;
}

int main()
{
    ll n,m;
    cin>>n>>m;
    if(m==1)    //只选一个数
    {
        cout<<0<<endl;
    }
    else
    {
        ll ans=0;
        c[m-2]=1;
        for(int i=m-1;i<=m+n;i++)   //求组合数
        {
            c[i]=c[i-1]*i%mod*ksm(i-m+2,mod-2)%mod;
        }
        for(ll d=1;d<n;d++)
        {
            ans=(ans+d*(n-d)%mod*c[d+m-2])%mod;
        }
        cout<<ans<<endl;
    }

    return 0;
}

注意
除法取模要算逆元转化为乘法，不能除完之后取模。