No.1696 Nonnil
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もしくは右上の雲マークをクリックしてアカウントを作成してください。
eSeF
platinum