[dp]Two Permutations 2022杭电多校第3场 1012

There are two permutations P_1,P_2,\dots,P_nP1​,P2​,…,Pn​, Q_1,Q_2,\dots,Q_nQ1​,Q2​,…,Qn​ and a sequence RR. Initially, RR is empty. While at least one of PP and QQ is non-empty, you need to choose a non-empty array (PP or QQ), pop its leftmost element, and attach it to the right end of RR. Finally, you will get a sequence RR of length 2n2n.

You will be given a sequence SS of length 2n2n, please count the number of possible ways to merge PP and QQ into RR such that R=SR=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 TT (1 \leq T \leq 3001≤T≤300), the number of test cases. For each test case:

The first line contains a single integer nn (1 \leq n \leq 300\,0001≤n≤300000), denoting the length of each permutation.

The second line contains nn distinct integers P_1,P_2,\dots,P_nP1​,P2​,…,Pn​ (1\leq P_i\leq n1≤Pi​≤n).

The third line contains nn distinct integers Q_1,Q_2,\dots,Q_nQ1​,Q2​,…,Qn​ (1\leq Q_i\leq n1≤Qi​≤n).

The fourth line contains 2n2n integers S_1,S_2,\dots,S_{2n}S1​,S2​,…,S2n​ (1\leq S_i\leq n1≤Si​≤n).

It is guaranteed that the sum of all nn is at most 2\,000\,0002000000.

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\,353998244353 instead.

Sample

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

题意： 给出两个长度为n的排列a和b，以及一个长度为2*n的序列c，求用a和b归并得到c的不同方案数。

分析： 可以设dp[i][j]表示考虑c中前i个数字，包含a中前j个数字的合法归并方法，然后保存a中各数字出现的位置pos1[i]，以及b中各数字出现的位置pos2[i]，状态转移的时候由于对于确定的i，合法的状态只有两个，所以只需要更新两个状态，分别考虑c[i]来自a还是b，如果来自a，那么dp[i][pos1[c[i]]] += dp[i-1][pos1[c[i]]-1]，如果来自b，那么dp[i][i-pos2[c[i]]] += dp[i-1][i-pos2[c[i]]]，i-pos2[c[i]]就是此时a中匹配到的位置。不过这样空间显然是会爆掉的，所以需要滚动数组优化空间，在优化的时候要注意，理论上滚到新的一层时数组应该全部为0，但是由于循环只有一层，所以不可能多用一个for来清空数组，不过可以注意到每层最多只会改变两个位置的值，所以可以记录下改变的位置是哪两个，当下一层用完这层值后就可以将这两个位置置零。

具体代码如下： 

#include 
#include 
#include 
#include 
#include 
#include 
#define int long long
using namespace std;
 
const int mod = 998244353;
int a[300005];
int b[300005];
int ab[600005];
int dp[2][300005];//dp[i][j]表示考虑ab中前i个包含a中前j个的方案数 
int pos1[300005];
int pos2[300005];
 
signed main()
{
	int T;
	cin >> T;
	while(T--){
		int n;
		scanf("%lld", &n);
		for(int i = 1; i <= n; i++){
			scanf("%lld", &a[i]);
			pos1[a[i]] = i;
		}
		for(int i = 1; i <= n; i++){
			scanf("%lld", &b[i]);
			pos2[b[i]] = i; 
		}
		for(int i = 0; i <= 1; i++)
			for(int j = 0; j <= n; j++)
				dp[i][j] = 0;
		for(int i = 1; i <= 2*n; i++)
			scanf("%lld", &ab[i]);
		int p1 = -1, p2 = -1;
		if(ab[1] == a[1]) dp[1][1]++, p1 = 1;
		if(ab[1] == b[1]) dp[1][0]++, p2 = 0;
		for(int i = 2; i <= 2*n; i++){
			//来自a
			dp[i&1][pos1[ab[i]]] = (dp[i&1][pos1[ab[i]]]+dp[(i-1)&1][pos1[ab[i]]-1])%mod;
			//来自b
			if(i-pos2[ab[i]] >= 0)
				dp[i&1][i-pos2[ab[i]]] = (dp[i&1][i-pos2[ab[i]]]+dp[(i-1)&1][i-pos2[ab[i]]])%mod;
			if(p1 != -1) dp[(i-1)&1][p1] = 0;
			if(p2 != -1) dp[(i-1)&1][p2] = 0;
			p1 = pos1[ab[i]];
			if(i-pos2[ab[i]] >= 0) 
				p2 = i-pos2[ab[i]];	
			else
				p2 = -1;
		}
		printf("%lld\n", dp[0][n]);
	}
    return 0;
}