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

题目链接

题目描述

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

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

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

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

在 $[1,n]$ 中任意选择 $m$ 次，得到了 $m$ 个整数（显然数字可能相同）;
将选出的 $m$ 个数字排序之后得到一个序列 ${ a{1},a{2},…,a_{m} }$。

定义一个序列的贡献为 $max{ a{1},a{2},…,a{m} }-min{ a{1},a{2},…,a{m}}$，求所有本质不同的序列的贡献和。

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

（对于两个序列长度为 $m$ 的序列 A、B，若 ${\exists}i∈[1,m]$，$A_i\neq B_i$，则序列 A、B 本质不同）

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

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

输入描述:

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

输出描述:

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

输入

3 2

输出

数论~
这种题目最简单的方法就是打表找规律，除非你是数论大师😂
很容易发现出现的差值就是 $[0,n-1]$ 一共 $n$ 种情况，关键点就在于这些插值出现了多少次，当 $m=2$ 时，我们很容易找到如下规律：

0:n
1:n-1
2:n-2
......
n-1:1

而当 $m>2$ 时，出现的次数就是乘上一个 $C^{m-2}_{i+1+m-3},i\in[0,n-1]$，那么我们只需要预处理 $1e6$ 内的组合数，就可以在 $O(n)$ 的时间内算出答案了，AC代码如下：

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const ll mod = 998244353;
const int N = 1e6 + 5;
ll n, m, F[N + 1], I[N + 1];

ll power(ll a, ll b) { return b ? power(a * a % mod, b / 2) * (b % 2 ? a : 1) % mod : 1; }

void init() {
    F[0] = 1;
    for (ll i = 1; i <= N; i++) F[i] = F[i - 1] * i % mod;
    I[N] = power(F[N], mod - 2);
    for (ll i = N; i--;) {
        I[i] = I[i + 1] * (i + 1) % mod;
    }
}

ll C(ll n, ll k) {
    return F[n] * I[n - k] % mod * I[k] % mod;
}

int main() {
    init();
    cin >> n >> m;
    ll ans = 0;
    for (ll i = 0; i <= n - 1; i++) {
        ans = (ans + (n - i) % mod * C(i + 1 + m - 3, m - 2) % mod * i) % mod;
    }
    cout << ans << endl;
    return 0;
}