No.2801 Unique Maximum
問題文最終更新日: 2024-06-28 21:06:37
English (AI translation)
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence.
Back to the original
yukicoder contest 435
(順位表)
の他の問題:
Problem Statement
Find the number, modulo $998244353$, of sequences of positive integers $A=(A_1,A_2,\dots ,A_N)$ of length $N$ that satisfy the following conditions.
- $1\le A_i\le M\ (1\le i\le N)$
-
Every non-empty contiguous subarray $B$ of $A$ satisfies the following condition.
- Let $x$ be the maximum value of the elements of $B$. Then $x$ appears exactly $1$ time in $B$.
Constraints
- All inputs are integers.
- $1\le N\le 2\times 10^5$
- $1\le M\le 10^9$
Input
$N$ $M$
Output
Output the answer.
Sample
Sample 1
Input
4 3
Output
10
Examples of $A$ that satisfy the conditions include the following.
- $(1,2,3,2)$
- $(1,3,1,2)$
- $(3,1,2,1)$
Conversely, the following $A$ do not satisfy the conditions.
-
$(2,1,2,3)$
- In the contiguous subarray $(2,1,2)$, the maximum value $2$ appears $2$ times.
-
$(2,1,1,1)$
- In the contiguous subarray $(1,1,1)$, the maximum value $1$ appears $3$ times.
Sample 2
Input
628 628
Output
652208441
Sample 3
Input
62862 86286
Output
451956562
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。
noya2