問題一覧 > 通常問題

No.2133 Take it easy!

レベル : / AI推定難易度 : 2050 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (解説公開後に AC するまで非表示) / 解いたユーザー数 34
作問者 : iro_ / テスター : penguinman taiga0629kyopro
お気に入りにしたユーザー ProblemId : 8363 / 自分の提出
問題文最終更新日: 2022-11-26 12:12:30
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 369 (順位表) の他の問題:

Notice

Because several parts of the problem statement were hard to understand, corrections were made during the contest (21:58).

Problem Statement

Among the sequences $P = (P_1,P_2,...,P_N)$ obtained by permuting $(1,2,…,N)$, find the number of those satisfying all of the following $2$ conditions, and output it modulo $998244353$.

  1. For every $i (1 ≤ i ≤ Q)$, the following conditions hold.
    • For every $j (L_i ≤ j ≤ R_i)$, $(P_{L_i}$ to $P_j$: number of even numbers $) \leq ( P_{L_i}$ to $P_j$: number of odd numbers $)$ is satisfied.
    • $( P_{L_i}$ to $P_{R_i}$: number of even numbers $) = ( P_{L_i}$ to $P_{R_i}$: number of odd numbers $)$ is satisfied.
  2. For every $k (1 ≤ k ≤ N)$, $ ( P_1$ to $P_k$: number of even numbers $) \leq ( P_1$ to $P_k$: number of odd numbers $)$ is satisfied.
Here, the phrase "$P_a$ to $P_b$: ..." $(a \leq b)$ is used to mean "... among $P_a,\ P_{a+1}, \ldots, P_b$".

Input

$N\ Q$
$L_1\  R_1$
$L_2\ R_2$
$\hspace{0.4cm}\vdots$
$L_Q\ R_Q$

・$1 \le N \le 2\times10^5\\$ ・$0 \le Q \le 60\\$ ・$1 \le L_i\le R_i \le N\\$ ・All input values are integers.

Output

Output the count modulo $998244353$.

Sample

Sample 1
Input
4 1
1 2
Output
4

The sequences satisfying the conditions are $(1,2,3,4)$, $(1,4,3,2)$, $(3,2,1,4)$, and $(3,4,1,2)$.

Sample 2
Input
7 2
1 4
2 6
Output
0

Note that there may be no $P$ satisfying the conditions.

Sample 3
Input
13496 8
9414 12593
5086 6861
7912 8981
448 9427
11018 12581
1836 8405
8042 9605
3722 9873
Output
262975011

Note that you must output the remainder modulo $998244353$.

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。