本文共 2027 字，大约阅读时间需要 6 分钟。

D. Count the Arrays

time limit per test

2 seconds

memory limit per test

512 megabytes

input

standard input

output

standard output

Your task is to calculate the number of arrays such that:

• each array contains nn elements;
• each element is an integer from 11 to mm;
• for each array, there is exactly one pair of equal elements;
• for each array aa, there exists an index ii such that the array is strictly ascending before the ii-th element and strictly descending after it (formally, it means that aj<aj+1aj<aj+1, if j<ij<i, and aj>aj+1aj>aj+1, if j≥ij≥i).

Input

The first line contains two integers nn and mm (2≤n≤m≤2⋅1052≤n≤m≤2⋅105).

Output

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

Examples

input

Copy

3 4

output

Copy

6

input

Copy

3 5

output

Copy

10

input

Copy

42 1337

output

Copy

806066790

input

Copy

100000 200000

output

Copy

707899035

Note

The arrays in the first example are:

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

构造一个长度为n的数列。

这个数列要满足每个数的大小都是1-m, 有且仅有一对数字相等。 一定存在一个i ，使得i左侧严格递增，右侧严格递减。 输出方案数。 【方法】

卢卡斯定理，，组合数，，存在一对数字相等，肯定在最大值点的左右两侧相等。

因为肯定存在一个最大值，所以我们枚举最大值点，2<=i<=n−1 

对于每个i，我们细想，只存在一对相等的数字，也就是有n−1 个不等的数字。相当于从m 中取出n−1 个数字， 

 ，这n−1 个数字中肯定有一个最大值，假设在i 处，然后从剩下的n−2 中选i−2 个数字到i 左面，原本有i−1个，但是有一个和右边相等，所以取i−2 个数字，然后那个可以和右边相等的数字可以取右边数字中的任何一个，即(n−i) 个数。

综上，对于每个最大值点i 来说，方案数为：CM,N-1*CN-2,I-2*(n-i).

#include 
   
    using namespace std;const int p=998244353;const int N=20000005;typedef long long ll;ll qmi(ll a,ll k,ll p){    ll res=1;    while(k)    {        if(k&1)            res=res*a%p;        a=a*a%p;        k>>=1;    }    return res;}ll fac[N];void init(){    fac[0]=1;    for(int i=1;i<=N-10;++i)        fac[i]=fac[i-1]*i%p;}ll C(ll n,ll m){    return fac[n]*qmi(fac[n-m]*fac[m]%p,p-2,p)%p;}int main(){    init();    ll n,m;    ios::sync_with_stdio(false);    cin>>n>>m;    ll ans=0;    for(int i=2;i<=n-1;++i)    {        ans=(ans+C(m,n-1)*C(n-2,i-2)%p*(n-i)%p)%p;    }    cout<
    
     <
    
   

 

转载地址：http://xtyzi.baihongyu.com/