No.3450 Permutation of Even Scores
Problem Statement
You are given a positive integer $N$ and a sequence of positive integers $A=(A_{1},A_{2},\dots, A_{M})$ of length $M$.
Here, all elements of $A$ are integers between $1$ and $N$, inclusive, and are pairwise distinct.
For a permutation $P = (P_{1}, P_{2}, \dots, P_{N})$ of $(1, 2, \dots, N)$, the score of $P$ is defined as the number of integers $i$ between $1$ and $M$, inclusive, that satisfy the following condition.
- There exists a contiguous subarray of $P$ that is a permutation of $(1, 2, \dots, A_{i})$.
Find the number, modulo $998244353$, of permutations $P$ of $(1, 2, \dots, N)$ whose score is even.
Constraints
- $1\leq M\leq N\leq 2\times 10^{5}$
- $1\leq A_{i}\leq N$
- The elements of $A$ are pairwise distinct.
- All input values are integers.
Input
$N$ $M$
$A_{1}$ $A_{2}$ $\cdots$ $A_{M}$
Output
Output the answer.
Sample
Sample 1
Input
4 1 2
Output
12
Permutations such as $P = (1, 2, 3, 4), (3, 4, 2, 1)$ have a score of $1$, which is not even.
Permutations such as $P = (4, 1, 3, 2), (2, 3, 4, 1)$ have a score of $0$, which is even.
There are $12$ permutations with an even score like those above, so output $12$.
Sample 2
Input
5 3 4 3 2
Output
68
Sample 3
Input
92 4 16 7 1 67
Output
622918974
Sample 4
Input
16 7 16 7 9 2 4 6 8
Output
522888621
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。
noya2