問題一覧 > 通常問題

No.2605 Pickup Parentheses

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 44
作問者 : 👑 amentorimaruamentorimaru / テスター : 👑 seekworserseekworser
2 ProblemId : 10283 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2024-01-08 13:25:52

問題文

とある仮想空間では様々なものを持つことができるので、バランスのとれた括弧列を持つことができることもあるかもしれません。


以下のいずれかのルールで構成される文字列をバランスのとれた括弧列とします

  • 空文字列
  • バランスのとれた括弧列 $A$ が存在し、 ( $A$ ) をこの順に結合した文字列
  • バランスのとれた括弧列 $A,B$ が存在し、 $AB$ をこの順に結合した文字列

エトワーニュくんはこれからバランスのとれた括弧列を作ろうと思うのですが、$M$ 人のユーザーがそれぞれ $L_i$ 文字目から $R_i$ 文字目の括弧列を持ってしまいそうなことに気づきました。ここで各区間 $[L_i,R_i]$ は互いに交わりを持たないことが保証されています。

次の条件を満たす括弧列の個数を $998244353$ で割った余りを求めてください

  • 長さが $N$ のバランスのとれた括弧列である
  • 全ての $i=1,\dots ,M$ において $L_i$ 文字目から $R_i$ 文字目はバランスのとれた括弧列ではない

入力

$N \ M$
$L_1 \ R_1$
$L_2 \ R_2$
$\vdots$
$L_M \ R_M$

  • 入力は全て整数
  • $1 \le N \le 2\times 10^5$
  • $0 \le M \le N$
  • $1 \le L_1 \le R_1 < L_2 \le R_2 < \dots < L_M \le R_M \le N$

出力

答えを出力せよ。

サンプル

サンプル1
入力
6 1
3 4
出力
3

作成できる括弧列は(()()),(())(),()(())の3通りです。

((()))と()()()も文字列全体がバランスのとれた括弧列ですが、 $L_1=3$ 文字目から $R_1=4$ までの二文字が()とバランスのとれた括弧列になっており条件を満たしません。

((((((は $3$ 文字目から $4$ 文字目がバランスのとれた括弧列ではないですが、全体がバランスのとれた括弧列になっていません。

サンプル2
入力
100 1
1 100
出力
0

完成できる文字列が一つもない場合があります。

サンプル3
入力
100 10
7 8
27 34
35 40
51 52
58 59
61 70
75 84
85 86
87 90
95 98
出力
995943820

$998244353$ で割った余りを求めてください。

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