問題一覧 > 通常問題

No.1696 Nonnil

レベル : / 実行時間制限 : 1ケース 3.500秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 32
作問者 : eSeFeSeF / テスター : platinumplatinum 👑 ygussanyygussany
5 ProblemId : 5174 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2021-09-30 19:14:58

問題文

以下の条件を全て満たす数列 $A=(A_1,\ \dots ,A_N)$ として考えられるものの個数を $998244353$ で割ったあまりを求めてください。

  • $A$ の要素は $1$ 以上 $K$ 以下の整数からなり、要素数は $N$ である。
  • $i=1,\ 2,\dots ,M$ の全てに対して、以下を満たす。
    • $L_i\le A_j\le R_i$ を満たす整数 $j\ (1\le j\le N)$ が存在する。

入力

$N\ \ K$
$M$
$L_1\ \ R_1$
$\vdots$
$L_M\ \ R_M$
【制約】
  • $1\le N\le 10^9$
  • $1\le K\le 1500$
  • $1\le M\le \min\left( 2\times 10^5,\dfrac{K(K+1)}{2}\right)$
  • $1\le L_i\le R_i\le K$
  • $i\neq j$ ならば $(L_i,\ R_i)\neq (L_j,\ R_j)$
  • 入力は全て整数

出力

答えを $\bmod 998244353$ で出力せよ。

サンプル

サンプル1
入力
2 5
2
1 3
4 5
出力
12

$(1,\ 4),\ (1,\ 5),\ (2,\ 4),\ (2,\ 5),\ (3,\ 4),\ (3,\ 5)$ およびその並び替えが条件を満たすので、 答えは $12$ 通りです。

サンプル2
入力
2 5
2
1 3
3 4
出力
13

$(1,\ 3),\ (1,\ 4),\ (2,\ 3),\ (2,\ 4),\ (3,\ 3),\ (3,\ 4),\ (3,\ 5)$ およびその並び替えが条件を満たすので、 答えは $13$ 通りです。

サンプル3
入力
2 12
3
1 2
3 6
7 11
出力
0

２つの要素だけでは、条件を満たすことができません。

サンプル4
入力
924844033 1500
6
1 314
159 265
358 979
271 818
1123 1349
1499 1500
出力
520302805

$\bmod 998244353$ で出力してください。

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