Two Permutations

题目描述
There are two permutations P1,P2,…,Pn​, Q1,Q2,…,Qn​ 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.
输入描述
The first line contains a single integer T (1≤T≤300), the number of test cases. For each test case:
The first line contains a single integer n (1≤n≤300,000), denoting the length of each permutation.
The second line contains n distinct integers P1,P2,…,Pn​ (1≤Pi≤n).
The third line contains n distinct integers Q1,Q2,…,Qn (1≤Qi≤n).
The fourth line contains 2n integers S1,S2,…,S2n (1≤Si≤n).
It is guaranteed that the sum of all n is at most 2,000,000.
输出描述
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.
样例
输入 复制
2
3
1 2 3
1 2 3
1 2 1 3 2 3
2
1 2
1 2
1 2 2 1
输出 复制
2
0
来源
2022年杭电多校-3

---

记忆化搜索：

if(z == 2 * n + 1 ) return 1; //一个可行方案
1、	s[z] == p[x] && s[z] == q[y] 
	return dfs(x+1,y,z+1) + dfs(x,y+1,z+1);
2、 s[z] == p[x] && s[z] != q[y]
	return dfs(x+1,y,z+1);
3、 s[z] == q[y] && s[z] != p[x]
	return dfs(x,y+1,z+1);
4、 s[z] != p[x] && s[z] != q[y]
	return 0;
1
2
3
4
5
6
7
8
9

---

Code：

#include 
using namespace std;
typedef long long ll;
const int N = 3e5 +10;
const int mod = 998244353;
int T,n;
int cnt[N],p[N],q[N],s[N*2];
ll vis[N];
ll dfs(int x,int y,int z) {
	//cout<
	if(z==2*n + 1) return 1;
	if(x<=n&&y<=n&&p[x]==q[y]) {
		if(p[x]==s[z]) {
			//cout<
			if(vis[p[x]]==-1) return vis[p[x]] = (dfs(x+1,y,z+1) + dfs(x,y+1,z+1)) % mod;
			return vis[p[x]];
		} else return 0;
	}
	if(x<=n&&p[x]==s[z]) return dfs(x+1,y,z+1);
	if(y<=n&&q[y]==s[z]) return dfs(x,y+1,z+1);
	return 0;
}
int main() {

	scanf("%d", &T);

	while(T--) {
		memset(cnt,0,sizeof(cnt));
		scanf("%d",&n);
		for(int i=1; i<=n; i++) scanf("%d",&p[i]);
		for(int i=1; i<=n; i++) scanf("%d",&q[i]);
		for(int i=1; i<=2*n; i++) {
			scanf("%d",&s[i]);
			cnt[s[i]]++;
		}
		bool ok = 0;
		for(int i=1; i<=n && !ok; i++)
			if(cnt[i]!=2) ok=1;
		if(ok) {
			puts("0");
			continue;
		}
		memset(vis,-1,sizeof(vis));
	
		printf("%lld\n",dfs(1,1,1));
	}
	return 0;
}
/*
2
4
1 2 3 4
1 2 3 4
1 1 2 2 3 3 4 4
*/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56