No.2133 Take it easy!
タグ : / 解いたユーザー数 34
作問者 :
penguinman
taiga0629kyopro
Notice
Because several parts of the problem statement were hard to understand, corrections were made during the contest (21:58).
Problem Statement
Among the sequences $P = (P_1,P_2,...,P_N)$ obtained by permuting $(1,2,…,N)$, find the number of those satisfying all of the following $2$ conditions, and output it modulo $998244353$.
- For every $i (1 ≤ i ≤ Q)$, the following conditions hold.
- For every $j (L_i ≤ j ≤ R_i)$, $(P_{L_i}$ to $P_j$: number of even numbers $) \leq ( P_{L_i}$ to $P_j$: number of odd numbers $)$ is satisfied.
- $( P_{L_i}$ to $P_{R_i}$: number of even numbers $) = ( P_{L_i}$ to $P_{R_i}$: number of odd numbers $)$ is satisfied.
- For every $k (1 ≤ k ≤ N)$, $ ( P_1$ to $P_k$: number of even numbers $) \leq ( P_1$ to $P_k$: number of odd numbers $)$ is satisfied.
Input
$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\\$ ・All input values are integers.
Output
Output the count modulo $998244353$.
Sample
Sample 1
Input
4 1 1 2
Output
4
The sequences satisfying the conditions are $(1,2,3,4)$, $(1,4,3,2)$, $(3,2,1,4)$, and $(3,4,1,2)$.
Sample 2
Input
7 2 1 4 2 6
Output
0
Note that there may be no $P$ satisfying the conditions.
Sample 3
Input
13496 8 9414 12593 5086 6861 7912 8981 448 9427 11018 12581 1836 8405 8042 9605 3722 9873
Output
262975011
Note that you must output the remainder modulo $998244353$.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。