F.A.Q
Hand In Hand
Online Acmers
Problem Archive
Realtime Judge Status
Authors Ranklist
 
     C/C++/Java Exams     
ACM Steps
Go to Job
Contest LiveCast
ICPC@China
Best Coder beta
VIP | STD Contests
    DIY | Web-DIY beta
Author ID 
Password 
 Register new ID

Two Permutations

Time Limit: 4000/4000 MS (Java/Others)    Memory Limit: 524288/524288 K (Java/Others)
Total Submission(s): 2726    Accepted Submission(s): 821


Problem Description
There are two permutations $P_1,P_2,\dots,P_n$, $Q_1,Q_2,\dots,Q_n$ and a sequence $R$. Initially, $R$ is empty. While at least one of $P$ and $Q$ is non-empty, you need to choose a non-empty array ($P$ or $Q$), pop its leftmost element, and attach it to the right end of $R$. Finally, you will get a sequence $R$ of length $2n$.

You will be given a sequence $S$ of length $2n$, please count the number of possible ways to merge $P$ and $Q$ into $R$ such that $R=S$. Two ways are considered different if and only if you choose the element from different arrays in a step.
 

Input
The first line contains a single integer $T$ ($1 \leq T \leq 300$), the number of test cases. For each test case:

The first line contains a single integer $n$ ($1 \leq n \leq 300\,000$), denoting the length of each permutation.

The second line contains $n$ distinct integers $P_1,P_2,\dots,P_n$ ($1\leq P_i\leq n$).

The third line contains $n$ distinct integers $Q_1,Q_2,\dots,Q_n$ ($1\leq Q_i\leq n$).

The fourth line contains $2n$ integers $S_1,S_2,\dots,S_{2n}$ ($1\leq S_i\leq n$).

It is guaranteed that the sum of all $n$ is at most $2\,000\,000$.
 

Output
For each test case, output a single line containing an integer, denoting the number of possible ways. Note that the answer may be extremely large, so please print it modulo $998\,244\,353$ instead.
 

Sample Input
2 3 1 2 3 1 2 3 1 2 1 3 2 3 2 1 2 1 2 1 2 2 1
 

Sample Output
2 0
 

Source
 

Statistic | Submit | Discuss | Note
Hangzhou Dianzi University Online Judge 3.0
Copyright © 2005-2024 HDU ACM Team. All Rights Reserved.
Designer & Developer : Wang Rongtao LinLe GaoJie GanLu
Total 0.000000(s) query 1, Server time : 2024-03-29 09:21:01, Gzip enabled