問題一覧 > 通常問題

No.3450 Permutation of Even Scores

レベル : / AI推定難易度 : 2575 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 24
作問者 : 👑 potato167 / テスター : noya2
お気に入りにしたユーザー ProblemId : 12529 / 自分の提出
問題文最終更新日: 2026-02-16 04:47:53
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 493 (順位表) の他の問題:

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もしくは右上の雲マークをクリックしてアカウントを作成してください。