题意:给你一组不重复的序列\(a\),每次可以选择一个数删除它左边或右边的一个数,并将选择的数append到数组\(b\)中,现在给你数组\(b\),问有多少种方案数得到\(b\).

题解:我们可以记录\(b_i\)在\(a_i\)中的位置,然后枚举\(b_i\),取它在\(a_i\)的位置,然后看\(a_{i-1}\)和\(a_{i+1}\)的情况,因为我们append之后必须要删除\(a_{i-1}\)和\(a_{i+1}\)中的一个,并且所有元素都是不重复的,所以\(a_{i-1}\)和\(a_{i+1}\)必然不能出现在\(b_{i+1}…b_{n}\)中,而当我们append \(a_i\)之后,它也就变成了没用的数.

所以我们可以讨论\(a_{i-1}\)和\(a_{i+1}\)的情况,假如它们两个都在\(b_{i+1}…b_{n}\)中出现,那么我们肯定不能构造出\(b\),直接\(ans=0\)然后结束,假如它们两个中有一个在\(b_{i+1}…b_n\)中出现,那么我们删除另外一个,因为删除的方案是固定的,所以对答案没有贡献,假如它们两个都没有出现,因为\(a_{i-1},a_i,a_{i+1}\)都是没有用的数,所以我们可以删去\(a_{i-1}\)或\(a_{i+1}\)中的任意一个,并且\(ans*=2\).

具体实现我们可以用双向链表,并且标记\(b_i,…,b_n\),每次操作后将\(b_i\)的标记删除即可.

代码:

#include
#define ll long long
#define fi first
#define se second
#define pb push_back
#define me memset
#define rep(a,b,c) for(int a=b;a<=c;++a) #define per(a,b,c) for(int a=b;a>=c;--a)
const int N = 1e6 + 10;
const int mod = 998244353 ;
const int INF = 0x3f3f3f3f;
using namespace std;
typedef pair PII;
typedef pair PLL;
ll gcd(ll a,ll b) {return b?gcd(b,a%b):a;}
ll lcm(ll a,ll b) {return a/gcd(a,b)*b;}

struct misaka{
int pre;
int nxt;
}e[N];

int t;
int n,m;
int a[N],b[N];
int pos[N];
bool cnt[N];

void init(){
rep(i,1,n){
e[i].pre=i-1;
e[i].nxt=i+1;
}
e[1].pre=0;
e[n].nxt=0;
}

void Delete(int x){
if(e[x].pre) e[e[x].pre].nxt=e[x].nxt;
if(e[x].nxt) e[e[x].nxt].pre=e[x].pre;
}

int main() {
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
cin>>t;
while(t--){
cin>>n>>m;
rep(i,1,n) cnt[i]=false;
rep(i,1,n){
cin>>a[i];
pos[a[i]]=i;
}
rep(i,1,m){
cin>>b[i];
b[i]=pos[b[i]]; //映射到a数组的位置
cnt[b[i]]=true;
}

    init();   //双向链表的初始化
    cnt[0]=true;
    int ans=1;
rep(i,1,m){
    if(cnt[e[b[i]].pre]){
        if(cnt[e[b[i]].nxt]){
            ans=0;
            break;
        }
        else{
            Delete(e[b[i]].nxt);
        }
    }
    else{
        if(cnt[e[b[i]].nxt]){
            Delete(e[b[i]].pre);
        }
        else{
            ans=ans*2%mod;
            Delete(e[b[i]].nxt);
        }
    }
    cnt[b[i]]=false;
}
cout<<ans<<'\n';
}

return 0;

}