307165: CF1312D. Count the Arrays

Memory Limit:512 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

Count the Arrays

题意翻译

求满足如下条件的长度为 $n$ 的序列 $a$ 的个数: - $\forall 1 \leq i \leq n$,都有 $1 \leq a_i \leq m$。 - $a$ 中存在且仅存在一对相同的元素 - 存在一个位置 $p$,使得 $a_1 \sim a_p$ 为严格单增序列,$a_p \sim a_n$ 为严格单减序列。即 $\forall 0 < j < p$,都有 $a_{j} < a_{j + 1}$,且 $\forall p \leq j < n$,都有 $a_j > a_{j + 1}$。 $1 \leq n, m \leq 2 \times 10^5$。 答案对 $998,244,353$ 取模。

题目描述

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 $ a_j < a_{j + 1} $ , if $ j < i $ , and $ a_j > a_{j + 1} $ , if $ j \ge i $ ).

输入输出格式

输入格式


The first line contains two integers $ n $ and $ m $ ( $ 2 \le n \le m \le 2 \cdot 10^5 $ ).

输出格式


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

输入输出样例

输入样例 #1

3 4

输出样例 #1

6

输入样例 #2

3 5

输出样例 #2

10

输入样例 #3

42 1337

输出样例 #3

806066790

输入样例 #4

100000 200000

输出样例 #4

707899035

说明

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

Input

题意翻译

求满足如下条件的长度为 $n$ 的序列 $a$ 的个数: - $\forall 1 \leq i \leq n$,都有 $1 \leq a_i \leq m$。 - $a$ 中存在且仅存在一对相同的元素 - 存在一个位置 $p$,使得 $a_1 \sim a_p$ 为严格单增序列,$a_p \sim a_n$ 为严格单减序列。即 $\forall 0 < j < p$,都有 $a_{j} < a_{j + 1}$,且 $\forall p \leq j < n$,都有 $a_j > a_{j + 1}$。 $1 \leq n, m \leq 2 \times 10^5$。 答案对 $998,244,353$ 取模。

加入题单

上一题 下一题 算法标签: