2022杭电多校第三场

1012 Two Permutations

f[i][0]表示序列S前i个元素已完成匹配且第i个元素来自序列P的方案数
f[i][1]表示序列S前i个元素已完成匹配且第i个元素来自序列Q的方案数

#include<bits/stdc++.h>
using namespace std;

#define IOS ios::sync_with_stdio(0),cin.tie(0)
#define endl '\n'

typedef long long ll;

const ll mod = 998244353;
const int N = 2e6 + 10;

int n;
int a[N], b[N], c[N], cnt[N], pos[N][2];

ll f[N][2];

void solve(){
    

    cin >> n;
    for (int i = 1;i <= n;++i)cin >> a[i], pos[a[i]][0] = i;
    for (int i = 1;i <= n;++i)cin >> b[i], pos[b[i]][1] = i;

    memset(cnt + 1, 0, n * 4);
    for (int i = 1;i <= n * 2;++i)cin >> c[i], ++cnt[c[i]];
    if (*max_element(cnt + 1, cnt + 1 + n) > 2){
    
        cout << 0 << endl;
        return;
    }

    for (int i = 1;i <= n * 2;++i)
        f[i][0] = f[i][1] = 0;
    f[1][!(a[1] == c[1])] = 1, f[1][b[1] == c[1]] = 1;

    for (int i = 2, j;i <= n * 2;++i){
    

        if (pos[c[i - 1]][0] + 1 == pos[c[i]][0])f[i][0] = (f[i][0] + f[i - 1][0]) % mod;
        if (pos[c[i - 1]][1] + 1 == pos[c[i]][1])f[i][1] = (f[i][1] + f[i - 1][1]) % mod;

        j = i - pos[c[i - 1]][0];
        if (b[j] == c[i])f[i][1] = (f[i][1] + f[i - 1][0]) % mod;
        j = i - pos[c[i - 1]][1];
        if (a[j] == c[i])f[i][0] = (f[i][0] + f[i - 1][1]) % mod;
    }
    cout << (f[n * 2][0] + f[n * 2][1]) % mod << endl;
}

int main(){
    

    IOS;
    int T;
    cin >> T;
    while (T--){
    
        solve();
    }

    return 0;
}