問題一覧 > 通常問題

No.1696 Nonnil

レベル : / AI推定難易度 : 2350 / 実行時間制限 : 1ケース 3.500秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 38
作問者 : eSeF / テスター : platinum ygussany
お気に入りにしたユーザー ProblemId : 5174 / 自分の提出
問題文最終更新日: 2021-09-30 19:14:58
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 316 (順位表) の他の問題:

Problem Statement

Find the number, modulo $998244353$, of possible sequences $A=(A_1,\ \dots ,A_N)$ that satisfy all of the following conditions.

  • The elements of $A$ are integers between $1$ and $K$, inclusive, and the number of elements is $N$.
  • For every $i=1,\ 2,\dots ,M$, the following holds.
    • There exists an integer $j\ (1\le j\le N)$ such that $L_i\le A_j\le R_i$.

Input

$N\ \ K$
$M$
$L_1\ \ R_1$
$\vdots$
$L_M\ \ R_M$
[Constraints]
  • $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$
  • $(L_i,\ R_i)\neq (L_j,\ R_j)$ if $i\neq j$
  • All inputs are integers.

Output

Output the answer modulo $\bmod 998244353$.

Sample

Sample 1
Input
2 5
2
1 3
4 5
Output
12

$(1,\ 4),\ (1,\ 5),\ (2,\ 4),\ (2,\ 5),\ (3,\ 4),\ (3,\ 5)$ and their permutations satisfy the conditions, so the answer is $12$.

Sample 2
Input
2 5
2
1 3
3 4
Output
13

$(1,\ 3),\ (1,\ 4),\ (2,\ 3),\ (2,\ 4),\ (3,\ 3),\ (3,\ 4),\ (3,\ 5)$ and their permutations satisfy the conditions, so the answer is $13$.

Sample 3
Input
2 12
3
1 2
3 6
7 11
Output
0

The conditions cannot be satisfied with only two elements.

Sample 4
Input
924844033 1500
6
1 314
159 265
358 979
271 818
1123 1349
1499 1500
Output
520302805

Output the answer modulo $\bmod 998244353$.

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