問題一覧 > 通常問題

No.2133 Take it easy!

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 28
作問者 : iro_iro_ / テスター : taiga0629kyoprotaiga0629kyopro penguinmanpenguinman
4 ProblemId : 8363 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2022-11-26 12:12:30

お知らせ

問題文に分かりづらい箇所が複数あったため、コンテスト中に修正を行いました(21:58)。

問題文

$(1,2,…,N)$ を並び替えて得られる数列 $P = (P_1,P_2,...,P_N)$ のうち以下の $2$ つの条件をすべて満たすものの個数を求め、$998244353$ で割ったあまりを出力してください。

  1. すべての $i (1 ≤ i ≤ Q)$ において以下の条件が成り立つ。
    • すべての $j (L_i ≤ j ≤ R_i)$ において $(P_{L_i}$ から $P_j$ までの偶数の個数 $) \leq ( P_{L_i}$ から $P_j$ までの奇数の個数 $)$ を満たす。
    • $( P_{L_i}$ から $P_{R_i}$ までの偶数の個数 $) = ( P_{L_i}$ から $P_{R_i}$ までの奇数の個数 $)$ を満たす。
  2. すべての $k (1 ≤ k ≤ N)$ において $ ( P_1$ から $P_k$ までの偶数の個数 $) \leq ( P_1$ から $P_k$ までの奇数の個数 $)$ を満たす。
ここで、「$P_a$ から $P_b$ までの〜」$(a \leq b)$ という文章は「$P_a,\ P_{a+1}, \ldots, P_b$ のうちの〜」という意味で使われています。

入力

$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\\$ ・入力はすべて整数

出力

個数を $998244353$ で割ったあまりを出力せよ。

サンプル

サンプル1
入力
4 1
1 2
出力
4

条件を満たす数列は $(1,2,3,4)$、 $(1,4,3,2)$、 $(3,2,1,4)$、 $(3,4,1,2)$ です。

サンプル2
入力
7 2
1 4
2 6
出力
0

条件を満たす $P$ が存在しない場合があることに注意してください。

サンプル3
入力
13496 8
9414 12593
5086 6861
7912 8981
448 9427
11018 12581
1836 8405
8042 9605
3722 9873
出力
262975011

$998244353$ で割ったあまりを出力することに注意してください。

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