2021牛客寒假算法基础集训营5

2021牛客寒假算法基础集训营5的补题记录

B 比武招亲（上）

链接：https://ac.nowcoder.com/acm/contest/9985/B
来源：牛客网

题目描述

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

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

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

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

1.1. 在 [1,n] 中任意选择 m 次，得到了 m 个整数（显然数字可能相同）;

2.2. 将选出的 m 个数字排序之后得到一个序列 {a1,a2,…,am}。

定义一个序列的贡献为 max{a1,a2,…,am}−min{a1,a2,…,am}，求所有本质不同的序列的贡献和。

为了防止结果过大，将答案为 998244353 取模后输出。
（对于两个序列长度为m的序列 A、B，若 ∃i∈[1,m]，Ai≠Bi，则序列 A、B 本质不同）

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

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

输入描述

一行输入两个正整数 n，m
【数据规模与约定】
1 <= n, m <= 5*10^5

输出描述

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

示例1

输入

3 2

输出

4

说明

本质不同的序列有如下几种：1 1、2 2、3 3、1 2、1 3、2 3，贡献为 0+0+0+1+2+1=4。

看到的第一感觉是一个dp，思考f[n][m]怎样从f[n-1][m-1]或者f[n][m-1]，f[n-1][m]转移而来，但是没想出来，觉得像是和组合数的方法数统计有关。

前置知识复习：
1.组合数递推。
2.乘法逆元。

1.组合数可以通过用公式算得，所以只需递推出n的阶乘即可。

公式为：C（n,m） = n ! / (n - m) ! * m !

2.乘法逆元的线性递推，这个看起来好像有一点点的复杂，在两三年前我曾经懂得这个的完全推法，但是现在的我已经伤仲永了…. 先记住线性递推逆元的写法，至于原理之后再研究….
但是 ！ 由于这道题的性质， p 是一个质数并且阶乘的数字比较大所以用小费马定理可以比较方便的求出逆元的大小。

inv[i] = (mod-mod/i) * inv[mod % i] % mod; // 一行线性递推乘法逆元。
小费马定理是： inv(x) = power(a, p-2, p);

现在可以开始写这道题了。

思路：

根据问题，计算贡献和大致是dp或者排列组合计数来解。仔细一看发现和DP没啥关系，于是考虑组合计数。

首先根据题意，知道一个序列的最大值和最小值后这个序列的贡献就可以被唯一确定出来，即最大值减最小值。不妨设某个长度为m的序列最大值为mx，最小值为mn，那么这个序列排序后究竟长什么样呢？是mn, .., .., .., ……. .., mx。肯定有一个mx和一个mn是确定的，关键在于剩下m - 2个数有多少种选法。我们用选法数乘以(mx - mn)就能得到最大值为mx最小值为mn的所有序列的总贡献了。而易知剩下m - 2个数肯定都在[mn, mx]内，现在就转化为一个高中常见的排列组合问题：x个相同的小球放入y个盒子，允许有空盒，问一共有多少种放法。答案是C(x + y - 1, y - 1)。对于这个问题而言，相当于m - 2个数分配到[mn, mx]的区间内，允许有数不被覆盖，问有多少种分配方法。即C(m - 2 + mx - mn, mx - mn - 1)。

组合数取模有模版，根据卢卡斯定理，预处理出逆元来就可以计算。那么问题来了：最大值和最小值怎么确定。直接二重循环枚举肯定t得妈妈都不认识，但其实没有必要二重循环。注意到mn = 1, mx = 5和mn = 2, mx = 6的情况其实答案相同，因此我们直接枚举mx - mn（mx - mn其实也是贡献），再乘上这样的区间个数计算即可。

坑点：预处理逆元的时候要开2倍n的大小！这个要根据组合数计算的范围来开！

这中间用到了组合数学的一些知识，那一个盒子放数的模型也要等到后面再研究了。

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e6 + 8;
const int p = 998244353;

ll n, m, ans = 0;
ll f[maxn];

ll power(ll a, ll b, ll p) {
    ll res = 1 % p;
    while(b) {
        if (b&1) res = (ll) res * a % p ;
        a = (ll) a * a % p;
        b >>= 1;
    }
    return res;
}

inline ll inv(ll x) {
	return power(x, p-2, p);
}

void init() {
	cin >> n >> m;
	f[0] = f[1] = 1;
	for (int i=2;i<=maxn;++i) 
		f[i] = f[i - 1] * i % p; 
}

inline ll C(ll n, ll m) {
	if (n == m|| m == 0)	return 1;
	return (f[n] * inv(f[m]) % p * inv(f[n - m]) % p);
}

int main() {
	init();
	for (int d=1;d<=n-1;++d) {
		ll tmp = d * (n - d) % p;
		ans = (ans + tmp * C(d + m - 2, m - 2) % p) %p;
	}
	cout << ans;
	return 0;
} 

这篇题解是从csdn上我的账号搬运过来的，新的博客搭好啦，开始搬运计划√