Educational Codeforces Round 83 (Rated for Div. 2) D.Count the Arrays

Educational Codeforces Round 83 (Rated for Div. 2) D.Count the Arrays

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

input

3 4

output

6

input

3 5

output

10

input

42 1337

output

806066790

input

100000 200000

output

707899035

emmm，就是排列组合找规律的题，只要想法没错一般就可以了，我简单讲解一下我的思路：
1.因为一组数里肯定有一对是重复的，所以我们只要从 $m$ 个数里挑 $n-1$ 个数即可，即为 $C_m^{n-1}$
2.下面挑重复的数字，因为必须要一对重复且这对重复的数不能在同一边，所以能重复的数只有 $n-2$ 个
3.判断这 $n-1$ 个数的排列情况，不能发现就是 $2^{n-3}$ 种
4.上述相乘即为答案，我套了一个快速乘和Lucas定理的模板，可能有些复杂了，还请见谅
AC代码如下：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll mod=998244353;

ll f(ll a,ll b)
{
    ll k=0;
    while(b)
    {
        if(b&1) k=(k+a)%mod;
        a=(a+a)%mod;
        b>>=1;
    }
    return k;
}

ll pow_mod(ll a, ll n)
{
    if(n == 0) return 1;
    ll x = pow_mod(a, n/2);
    ll ans = x * x % mod;
    if(n % 2 == 1) ans = ans *a % mod;
    return ans%mod;
}

ll C(ll n,ll m) {
    if(n < m) return 0;
    ll res = 1;
    for(ll i=1; i<=m; i++) {
        ll a = (n+i-m)%mod;
        ll b = i%mod;
        res = res*(a*pow_mod(b,mod-2)%mod)%mod;
    }
    return res;
}

ll Lucas(ll n,ll m) {
    if(m == 0) return 1;
    return C(n%mod, m%mod) * Lucas(n/mod,m/mod)%mod;
}

int main(){
    ll n,m;
    cin>>n>>m;
    ll ans=f(f(Lucas(m,n-1),(n-2)),pow_mod(2,n-3));
    cout<<ans;
	return 0;
}