题目描述

难度分:$1400$

输入$T(\leq 10^5)$表示$T$组数据。所有数据的$n$之和$\leq 5 \times 10^5$。

每组数据输入$n(1 \leq n \leq 10^5)$和两个$1$~$n$的排列$a$和$b$，

然后输入数组$d$，保证$d[i]$是$(0,a[i],b[i])$中的一个。

构造一个$1$~$n$的排列$c$，满足：

1. 如果$d[i] \gt 0$，那么$c[i]$必须是$d[i]$；
2. 否则$c[i]$可以是$a[i]$，也可以是$b[i]$。

你能构造出多少个不同的排列$c$？模$10^9+7$。输入保证至少能构造一个排列$c$。

输入样例

9
7
1 2 3 4 5 6 7
2 3 1 7 6 5 4
2 0 1 0 0 0 0
1
1
1
0
6
1 5 2 4 6 3
6 5 3 1 4 2
6 0 0 0 0 0
8
1 6 4 7 2 3 8 5
3 2 8 1 4 5 6 7
1 0 0 7 0 3 0 5
10
1 8 6 2 4 7 9 3 10 5
1 9 2 3 4 10 8 6 7 5
1 9 2 3 4 10 8 6 7 5
7
1 2 3 4 5 6 7
2 3 1 7 6 5 4
0 0 0 0 0 0 0
5
1 2 3 4 5
1 2 3 4 5
0 0 0 0 0
5
1 2 3 4 5
1 2 3 5 4
0 0 0 0 0
3
1 2 3
3 1 2
0 0 0

输出样例

4
1
2
2
1
8
1
2
2

算法

图论+组合数学

本题保证输入一定合法有解，做的时候就没有那么多痛苦的边界问题了。但是说来惭愧，看了很久才反应过来是个图论问题，一开始一直在想DP。

直接把$d$看成要构造的$c$，可以进行的操作是往残缺的位置中（$d[i]=0$的位置）填入$a[i]$或$b[i]$。我们可以发现，$c[i] \gt 0$时，如果$c[i]=a[i]$那么另一个有$a[i]$的位置$j$就要填另一个数，它填了这个数之后会对有这个数的下标进一步产生连锁反应，直到形成闭环。

比如第一个$case$，$i=1$的位置有$c[1]=a[1]$，那么另一个有$a[1]$的位置$2$，它拥有的数对是$(a[2]=2,b[2]=3)$，$2$位置就只能填$3$，进一步另一个拥有$3$的位置$3$拥有数对$(a[3]=3,b[3]=1)$就只能填$1$，而这个位置已经填好了$1$，因此扩展过程终止。

BFS预处理

我们先从$c[i] \gt 0$的位置开始，按照这种链式反应规则做一个BFS，把能确定值的位置填好数，再考虑剩下的位置怎么填。

tarjan缩点

然后对于拥有同一个数值$val$的两个位置$u$和$v$连边（如果只有一个位置有$val$说明是自环，不考虑，这个位置填的数只有一种，不会增加方案数），说明确定$c[u]$就可以确定$c[v]$，确定$c[v]$就可以确定$c[u]$。建完图后，跑一遍tarjan算法对整张图进行缩点，得到一个个的强联通分量。

组合数学

每个强联通分量里面确定一个点填的数就可以把整个连通分量里的数填好，而每个点可以选$a[i]$也可以选$b[i]$，所以一个连通分量里就有两种方案。而连通分量之间都是相互独立的，因此总方案数就是全部乘起来，用快速幂或者遍历的时候直接求都行。

复杂度分析

时间复杂度

BFS的时间复杂度是$O(n)$线性的（每个节点的度是$2$，因此边数也是$O(n)$）级别；tarjan缩点的时间复杂度是$O(n)$的；最后遍历所有连通分量计算总方案数只与连通分量的个数有关，在极限情况下连通分量的数量是$O(n)$级别，因此算法整体的时间复杂度为$O(n)$。

空间复杂度

图的邻接表、BFS的队列、以及tarjan算法的栈、辅助数组都是$O(n)$级别的空间。因此，算法整体的额外空间复杂度为$O(n)$。

C++ 代码

#include <bits/stdc++.h>

using namespace std;
const int N = 100010, MOD = 1e9 + 7;
int T, n, a[N], b[N], c[N];
int dfn[N], low[N], id[N], sz[N];
bool in_stk[N];
int ts, scc_cnt;
stack<int> stk;
set<int> mp[N];
vector<int> graph[N];

int fast_power(int a, int k, int p) {
    int res = 1 % p;
    while(k) {
        if(k & 1) res = (long long)res * a % p;
        a = (long long)a * a % p;
        k >>= 1;
    }
    return res;
}

void tarjan(int u) {
    dfn[u] = low[u] = ++ts;
    stk.push(u);
    in_stk[u] = true;
    for(int v: graph[u]) {
        if(!dfn[v]) {
            tarjan(v);
            low[u] = min(low[u], low[v]);
        }else if(in_stk[v]) {
            low[u] = min(low[u], dfn[v]);
        }
    }
    if(dfn[u] == low[u]) {
        ++scc_cnt;
        int y;
        do{
            y = stk.top();
            stk.pop();
            in_stk[y] = false;
            id[y] = scc_cnt;
            sz[scc_cnt]++;
        }while(y != u);
    }
}

int main() {
    scanf("%d", &T);
    while(T--) {
        scanf("%d", &n);
        for(int i = 1; i <= n; i++) {
            scanf("%d", &a[i]);
            dfn[i] = low[i] = id[i] = sz[i] = in_stk[i] = 0;
            mp[i].clear();
            graph[i].clear();
        }
        for(int i = 1; i <= n; i++) {
            scanf("%d", &b[i]);
        }
        // mp[val]表示有val的索引
        queue<int> q;
        for(int i = 1; i <= n; i++) {
            scanf("%d", &c[i]);
            if(a[i] == b[i]) c[i] = a[i];
            if(c[i]) {
                q.push(i);
            }
            mp[a[i]].insert(i);
            mp[b[i]].insert(i);
        }
        while(!q.empty()) {
            int i = q.front();
            q.pop();
            mp[c[i]].erase(i);
            if(mp[c[i]].size()) {
                // i位置填了c[i]，那么另外一个有c[i]的位置就要填另一个数
                int j = *mp[c[i]].begin();
                if(c[j] == 0) {
                    q.push(j);
                    if(a[j] == c[i]) {
                        c[j] = b[j];
                    }else {
                        c[j] = a[j];
                    }
                }
                mp[c[i]].erase(j);
            }
        }
        // 建图
        for(int val = 1; val <= n; val++) {
            if(mp[val].size() == 2) {
                int u = *mp[val].begin(), v = *mp[val].rbegin();
                graph[u].push_back(v);
                graph[v].push_back(u);
            }
        }
        // 缩点
        ts = scc_cnt = 0;
        for(int u = 1; u <= n; u++) {
            if(!dfn[u]) tarjan(u);
        }
        // 按照强连通分量统计
        int p = 0;
        for(int i = 1; i <= scc_cnt; i++) {
            if(sz[i] > 1) p++;
        }
        printf("%d\n", fast_power(2, p, MOD));
    }
    return 0;
}