简单计数

题目链接：CF1312D 【Count the Arrays】

刚开始菜鸡 $\texttt{CXY07}$ 以为这是一道什么 $dp$，瞎想了好久好久......

首先我们可以发现，这个东西是一个单峰的数组，并且里面有且仅有一个数字出现了两次。

很快发现实际上一个这样的长度为 $n$ 的数组，实际上一共有 $n - 1$ 个不同的数字

那我们就先从 $m$ 个数字中拿 $n - 1$ 个，共 $C_{m}^{n-1}$ 种情况

那么显然中间有一个数字是最大的 废话，这个数字必须放在峰顶(?)的位置，其他的 $n - 2$ 个数字自然可以放在峰顶的左侧或者右侧

这里一共多少种情况呢？当然是 $2^{n-2}$ 种（每一个数字可以在左右中任意选择一边）

不难发现只要我们定下这 $n-2$ 个数字分别在峰顶的左边或者右边，整个数组就只有一种构造的方法了，而距离我们完成整个数组，就只差那个重复的值了

然后我们来定这个重复的值是谁，首先这个数字肯定不能是峰顶（题中是严格大于/小于）所以我们只能从剩下 $n-2$ 个值中间选择，并且无论你选择了哪一个值，它一定就已经在数组中出现了一次了。

那么，我们如果选择一个值，那么这个值已经出现在了峰顶的一侧，为了满足 严格大于/小于 的条件，我们只能把这个重复的值放在另外一边了

所以这里我们任意从 $n-2$ 个值中选择都是可行的，这里方案有 $n-2$ 种

但是有一个问题，这里可能会出现重复的情况：

比如：

如果现在我们需要构造一个长度为 $6$ 的序列，我们已经选择了 $1$ ~ $ 5$ 这几个值了，现在有这样两种方案：

1 2 5 4 3

1 5 4 3 2

如果我们想要再加入一个 $2$，那两个序列会同时变成：1 2 5 4 3 2 ，但是我们把他计算了两遍......

容易发现无论你选择哪一个值，都会出现这个情况，所以我们再 $\times \frac{1}{2}$ 就好了

所以最后答案为：

$$C_m^{n-1} \times 2^{n-2} \times (n-2) \times \frac{1}{2}$$

也就是：

$$C_m^{n-1} \times 2^{n-3} \times (n-2)$$

容易发现当 $n < 3$ 时无解，特判即可，我是在判断 $2$ 的幂的时候处理的

用了费马小定理求逆元，所以复杂度貌似带个 $log$

$Code:$

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

#define int long long
#define inv(x) ksm(x,mod - 2)

const int MAXN = 2e5 + 10;
const int INF = 2e9;
const int mod = 998244353;

int n,m;

inline int ksm(int a,int b) {
    if(b < 0) return 0;//判断一下即可
    if(a == 1) return 1;
    int res = 1;
    while(b) {
        if(b & 1) (res *= a) %= mod;
        (a *= a) %= mod;
        b >>= 1;
    }
    return res;
}

inline int C(int a,int b) {
    int res = 1;
    for(register int i = a;i >= a - b + 1; --i)
        (res *= i) %= mod;
    for(register int i = 1;i <= b; ++i)
        (res *= inv(i)) %= mod;
    return res;
}

signed main () {
    cin >> n >> m;
    cout << ksm(2,n - 3) % mod * C(m,n - 1) % mod * (n - 2) % mod << endl;
    return 0;//End.
}

初三的 $OIer$，请多关照