1312D.md (1201B)
1 Source: https://codeforces.com/problemset/problem/1312/D 2 3 D. Count the Arrays 4 5 time limit per test 6 7 2 seconds 8 9 memory limit per test 10 11 512 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 Your task is to calculate the number of arrays such that: 22 23 * each array contains $n$ elements; 24 * each element is an integer from $1$ to $m$; 25 * for each array, there is exactly one pair of equal elements; 26 * 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 $a_j \lt a_{j + 1}$, if $j \lt i$, and $a_j \gt a_{j + 1}$, if $j \ge i$). 27 28 Input 29 30 The first line contains two integers $n$ and $m$ ($2 \le n \le m \le 2 \cdot 10^5$). 31 32 Output 33 34 Print one integer — the number of arrays that meet all of the aforementioned conditions, taken modulo $998244353$. 35 36 Examples 37 38 Input 39 40 ``` 41 3 4 42 ``` 43 44 Output 45 46 ``` 47 6 48 ``` 49 50 Input 51 52 ``` 53 3 5 54 ``` 55 56 Output 57 58 ``` 59 10 60 ``` 61 62 Input 63 64 ``` 65 42 1337 66 ``` 67 68 Output 69 70 ``` 71 806066790 72 ``` 73 74 Input 75 76 ``` 77 100000 200000 78 ``` 79 80 Output 81 82 ``` 83 707899035 84 ``` 85 86 Note 87 88 The arrays in the first example are: 89 90 * $[1, 2, 1]$; 91 * $[1, 3, 1]$; 92 * $[1, 4, 1]$; 93 * $[2, 3, 2]$; 94 * $[2, 4, 2]$; 95 * $[3, 4, 3]$.