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
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].
题意：
给定n,m，让你构造一个长度为n的数组，要求这n个数都必须在1~m范围内，且要有两个数相同，数组内的值是先上升再下降的形式，问能够构造的组数。
思路：
昨晚做完C就到时间了，今早一看其实挺好想的。
很容易想到我们选择一个最大值放在倒数第二位，因为要保证了先上升再下降的形式，所以最大值必然只有一个。
我们可以先从m个数里选择n-1个数，这其中包括最大值。再从剩下的n-2个数里选择一个放在最后一位。
再来考虑一下这一组数内部的顺序问题，最大值的位置是不会变的，两个相等的数位置变了也没有影响，剩下的n-3个数，有最大值左边和最大值右边两种情况，所以是2^（n-3）。
被内部的顺序问题卡住了qwq
组合数学模板：传送门
代码：
要注意特判n==2的情况，不然用lucas会t
#include<bits/stdc++.h> using namespace std; typedef long long ll; ll m,n,p=998244353; ll ksm(ll a,ll b,ll p){ ll res=1; while(b){ //&运算当相应位上的数都是1时，该位取1，否则该为0。 if(b&1) res=1ll*res*a%p;//转换为ll型 a=1ll*a*a%p; b>>=1;//十进制下每除10整数位就退一位 } return res; } ll c(ll a,ll b,ll p){ if(b>a) return 0; ll res=1; for(int i=1,j=a;i<=b;i++,j--){ res=res*j%p; res=res*ksm(i,p-2,p)%p;//逆元 } return res; } ll lucas(ll a,ll b,ll p){ if(a<p &&b<p) return c(a,b,p); return c(a%p,b%p,p)*lucas(a/p,b/p,p)%p; } int main(){ cin>>n>>m; if(n==2){ puts("0"); return 0; } ll res=lucas(m,n-1,p)%p*ksm(2,n-3,p)%p*(n-2)%p; cout<<res; return 0; }
