codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

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]$.