D. Count the Arrays
time limit per test2 seconds
memory limit per test512 megabytes
inputstandard input
outputstandard output
Your task is to calculate the number of arrays such that:

each array contains n elements;
each element is an integer from 1 to m;
for each array, there is exactly one pair of equal elements;
for each array a, there exists an index i such that the array is strictly ascending before the i-th element and strictly descending after it (formally, it means that aj<aj+1, if j<i, and aj>aj+1, if j≥i).
Input
The first line contains two integers n and m (2≤n≤m≤2⋅105).

Output
Print one integer — the number of arrays that meet all of the aforementioned conditions, taken modulo 998244353.

Examples
inputCopy
3 4
outputCopy
6
inputCopy
3 5
outputCopy
10
inputCopy
42 1337
outputCopy
806066790
inputCopy
100000 200000
outputCopy
707899035
Note
The arrays in the first example are:

[1,2,1];
[1,3,1];
[1,4,1];
[2,3,2];
[2,4,2];
[3,4,3].

题意：给了1~m之间的数字，让构造一个长度为n的序列
这个序列必须有一个数字重复 也就是说必须有n-1种数字
对于位置i 前面必须单调递增 后面必须单调递减 求种类数

思路：
m种数字选n-1种 第一步自然就是组合数先求出来C(m,n-1)
然后 我们考虑 重复的数字
因为峰值只能有一个 那么重复的数字一定不是最大值， 所以重复的数字的选择有n-2种
那么对于种类确定了之后，根据题意可以推断出来，重复的数字一定是在峰值的左右个一个，那么去掉这三个数后，还有n-3个数字 并且种类两两不同
对于这n-3个数 也可以说n-3种数，要么他在峰值的左边 要么在右边
其实就是2^(n-3) 种分配方式 不是左就是右 类比二进制位不是0就是1
所以答案就是C(m,n-1)*(n-2)*2^(n-3)
注意特判n==2的时候 因为这时候要选取两个 又因为题中要求要有一对一样数字 这显然不满足峰值那个要求

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=998244353;
ll n,m;
ll qpow(ll a,ll b)
{
    ll ans=1;
    a%=mod;
    while(b)
    {
        if(b&1)
            ans=ans*a%mod;
        b>>=1;
        a=a*a%mod;
    }
    return ans;
}
int main()
{


    scanf("%lld%lld",&n,&m);
    if(n==2) return puts("0"),0;
    ll an=1,res=1;
    n--;
    ll nn=n;
    if(nn*2>m) nn=m-nn;
    for(int i=0; i<nn; i++)
    {
        an=an*(m-i)%mod;
        res=res*(nn-i)%mod;
    }
    an=an%mod*qpow(res,mod-2)%mod;
    an=an*(n-1)%mod*qpow(2ll,n-2)%mod;
    printf("%lld\n",an);

    return 0;
}