311377: CF1976E. Splittable Permutations

Memory Limit：512 MB Time Limit：2 S
Judge Style：Text Compare Creator：
Submit：0 Solved：0

Description

E. Splittable Permutationstime limit per test2 secondsmemory limit per test512 megabytesinputstandard inputoutputstandard output

Initially, we had one array, which was a permutation of size $n$ (an array of size $n$ where each integer from $1$ to $n$ appears exactly once).

We performed $q$ operations. During the $i$-th operation, we did the following:

  • choose any array we have with at least $2$ elements;
  • split it into two non-empty arrays (prefix and suffix);
  • write two integers $l_i$ and $r_i$, where $l_i$ is the maximum element in the left part which we get after the split, and $r_i$ is the maximum element in the right part;
  • remove the array we've chosen from the pool of arrays we can use, and add the two resulting parts into the pool.

For example, suppose the initial array was $[6, 3, 4, 1, 2, 5]$, and we performed the following operations:

  1. choose the array $[6, 3, 4, 1, 2, 5]$ and split it into $[6, 3]$ and $[4, 1, 2, 5]$. Then we write $l_1 = 6$ and $r_1 = 5$, and the arrays we have are $[6, 3]$ and $[4, 1, 2, 5]$;
  2. choose the array $[4, 1, 2, 5]$ and split it into $[4, 1, 2]$ and $[5]$. Then we write $l_2 = 4$ and $r_2 = 5$, and the arrays we have are $[6, 3]$, $[4, 1, 2]$ and $[5]$;
  3. choose the array $[4, 1, 2]$ and split it into $[4]$ and $[1, 2]$. Then we write $l_3 = 4$ and $r_3 = 2$, and the arrays we have are $[6, 3]$, $[4]$, $[1, 2]$ and $[5]$.

You are given two integers $n$ and $q$, and two sequences $[l_1, l_2, \dots, l_q]$ and $[r_1, r_2, \dots, r_q]$. A permutation of size $n$ is called valid if we can perform $q$ operations and produce the given sequences $[l_1, l_2, \dots, l_q]$ and $[r_1, r_2, \dots, r_q]$.

Calculate the number of valid permutations.

Input

The first line contains two integers $n$ and $q$ ($1 \le q < n \le 3 \cdot 10^5$).

The second line contains $q$ integers $l_1, l_2, \dots, l_q$ ($1 \le l_i \le n$).

The third line contains $q$ integers $r_1, r_2, \dots, r_q$ ($1 \le r_i \le n$).

Additional constraint on the input: there exists at least one permutation which can produce the given sequences $[l_1, l_2, \dots, l_q]$ and $[r_1, r_2, \dots, r_q]$.

Output

Print one integer — the number of valid permutations, taken modulo $998244353$.

ExamplesInput
6 3
6 4 4
5 5 2
Output
30
Input
10 1
10
9
Output
1814400
Input
4 1
2
4
Output
8

Output

题目大意：
一开始有一个长度为n的排列（即一个长度为n的数组，其中每个整数从1到n恰好出现一次）。执行q个操作，第i个操作如下：

1. 选择至少有2个元素的任意数组；
2. 将其拆分为两个非空数组（前缀和后缀）；
3. 记录两个整数l_i和r_i，其中l_i是拆分后左部分的最大元素，r_i是右部分的最大元素；
4. 将选中的数组从可用数组池中移除，并将得到的两个部分添加到数组池中。

给定两个整数n和q，以及两个序列[l_1, l_2, ..., l_q]和[r_1, r_2, ..., r_q]，长度为n的排列如果可以通过执行q个操作生成给定的序列，则称为有效的排列。计算有效排列的数量。

输入输出数据格式：
输入：
- 第一行包含两个整数n和q（1 ≤ q < n ≤ 3 × 10^5）。
- 第二行包含q个整数l_1, l_2, ..., l_q（1 ≤ l_i ≤ n）。
- 第三行包含q个整数r_1, r_2, ..., r_q（1 ≤ r_i ≤ n）。
- 输入数据保证至少存在一个排列可以生成给定的序列。

输出：
- 打印一个整数，即有效排列的数量，模998244353。

示例输入输出：
输入：
```
6 3
6 4 4
5 5 2
```
输出：
```
30
```

输入：
```
10 1
10
9
```
输出：
```
1814400
```

输入：
```
4 1
2
4
```
输出：
```
8
```题目大意： 一开始有一个长度为n的排列（即一个长度为n的数组，其中每个整数从1到n恰好出现一次）。执行q个操作，第i个操作如下： 1. 选择至少有2个元素的任意数组； 2. 将其拆分为两个非空数组（前缀和后缀）； 3. 记录两个整数l_i和r_i，其中l_i是拆分后左部分的最大元素，r_i是右部分的最大元素； 4. 将选中的数组从可用数组池中移除，并将得到的两个部分添加到数组池中。 给定两个整数n和q，以及两个序列[l_1, l_2, ..., l_q]和[r_1, r_2, ..., r_q]，长度为n的排列如果可以通过执行q个操作生成给定的序列，则称为有效的排列。计算有效排列的数量。 输入输出数据格式： 输入： - 第一行包含两个整数n和q（1 ≤ q < n ≤ 3 × 10^5）。 - 第二行包含q个整数l_1, l_2, ..., l_q（1 ≤ l_i ≤ n）。 - 第三行包含q个整数r_1, r_2, ..., r_q（1 ≤ r_i ≤ n）。 - 输入数据保证至少存在一个排列可以生成给定的序列。 输出： - 打印一个整数，即有效排列的数量，模998244353。 示例输入输出： 输入： ``` 6 3 6 4 4 5 5 2 ``` 输出： ``` 30 ``` 输入： ``` 10 1 10 9 ``` 输出： ``` 1814400 ``` 输入： ``` 4 1 2 4 ``` 输出： ``` 8 ```

Source/Category

加入题单

上一题 下一题 算法标签：