组合数学CF1312D CountArrays

Educational Codeforces Round 83（针对Div. 2选手的评级赛事）D题：计算数组数量
题目链接

题目描述

给定一个长度为n的数组，其元素取值范围在1到m之间，该数组中包含一组重复的数值。此外，该数组存在一个最大值，使得数组在该点之前严格递增，在该点之后严格递减（形成山峰状结构）。请计算满足上述条件的数组数量，并将结果对998244353取模。

思路

选取 n-1 个数值，将其中单调递增的序列置于左侧，此时共有 C[n-1][m] 种不同的组合方式。接下来，在左侧剩余的 n-2 个数值中挑选一个数，使其满足特定条件。随后，通过枚举该最大值所处的位置，即从左侧选择若干数值移动至右侧，此时剩余 n-3 个数值可供选择。对于这些数值的组合方式总和为：C[0][n-3] + C[1][n-3] + C[2][n-3] + … + C[n-4][n-3] + C[n-3][n-3] = 2^(n-3)。因此，最终得出的答案为 C[n-1][m] × (n-2) × 2^(n-3)。

补一个组合数的知识点

采用 乘法逆元结合快速幂与阶乘 的方式，提供取模组合数的实现模板。
`（a / b) mod m = ( a *