11336: [yosupo] Enumerative Combinatorics - Number of Increasing Sequences Between Two Sequences
[Creator : ]
Description
Given integers $N,M$ and two non-negative integer sequences $A = \left( A_0, A_1, \cdots, A_{N-1} \right), B = \left( B_0, B_1, \cdots, B_{N-1} \right)$.
Find the number of a non-negative integer sequences $x = \left( x_0, x_1, \cdots, x_{N-1} \right)$ which satisfies the following conditions, and print it $\bmod \ 998244353$.
- $0 \leq x_0 \leq \cdots \leq x_{N-1} < M$
- $A_i \leq x_i < B_i$
Find the number of a non-negative integer sequences $x = \left( x_0, x_1, \cdots, x_{N-1} \right)$ which satisfies the following conditions, and print it $\bmod \ 998244353$.
- $0 \leq x_0 \leq \cdots \leq x_{N-1} < M$
- $A_i \leq x_i < B_i$
Input
$N$ $M$
$A_0$ $A_1$ $\cdots$ $A_{N-1}$
$B_0$ $B_1$ $\cdots$ $B_{N-1}$
$A_0$ $A_1$ $\cdots$ $A_{N-1}$
$B_0$ $B_1$ $\cdots$ $B_{N-1}$
Constraints
- $1 \leq N \leq 2^{17}$
- $1 \leq M \leq 2^{17}$
- $0 \leq A_i < B_i \leq M$ ($0 \leq i \leq N - 1$)
- $1 \leq M \leq 2^{17}$
- $0 \leq A_i < B_i \leq M$ ($0 \leq i \leq N - 1$)
Sample 1 Input
5 9
0 0 3 2 5
8 3 4 5 9
Sample 1 Output
48
Sample 2 Input
5 9
0 0 5 2 0
8 3 9 5 9
Sample 2 Output
0
Sample 3 Input
12 100
7 10 12 17 18 20 27 36 41 52 52 62
48 50 52 67 68 71 100 100 100 100 100 100
Sample 3 Output
13329431