While searching for the pizza, baby Hosssam came across two permutations?aa?and?bb?of length?nn.
Recall that a permutation is an array consisting of?nn?distinct integers from?11?to?nn?in arbitrary order. For example,?[2,3,1,5,4][2,3,1,5,4]?is a permutation, but?[1,2,2][1,2,2]?is not a permutation (22?appears twice in the array) and?[1,3,4][1,3,4]?is also not a permutation (n=3n=3?but there is?44?in the array).
Baby Hosssam forgot about the pizza and started playing around with the two permutations. While he was playing with them, some elements of the first permutation got mixed up with some elements of the second permutation, and to his surprise those elements also formed a permutation of size?nn.
Specifically, he mixed up the permutations to form a new array?cc?in the following way.
- For each?ii?(1≤i≤n1≤i≤n), he either made?ci=aici=ai?or?ci=bici=bi.
- The array?cc?is a permutation.
You know permutations?aa,?bb, and values at some positions in?cc. Please count the number different permutations?cc?that are consistent with the described process and the given values. Since the answer can be large, print it modulo?109+7109+7.
It is guaranteed that there exists at least one permutation?cc?that satisfies all the requirements.
Input
The first line contains an integer?tt?(1≤t≤1051≤t≤105) — the number of test cases.
The first line of each test case contains a single integer?nn?(1≤n≤1051≤n≤105) — the length of the permutations.
The next line contains?nn?distinct integers?a1,a2,…,ana1,a2,…,an?(1≤ai≤n1≤ai≤n) — the first permutation.
The next line contains?nn?distinct integers?b1,b2,…,bnb1,b2,…,bn?(1≤bi≤n1≤bi≤n) — the second permutation.
The next line contains?nn?distinct integers?d1,d2,…,dnd1,d2,…,dn?(didi?is either?00,?aiai, or?bibi) — the description of the known values of?cc. If?di=0di=0, then there are no requirements on the value of?cici. Otherwise, it is required that?ci=dici=di.
It is guaranteed that there exists at least one permutation?cc?that satisfies all the requirements.
It is guaranteed that the sum of?nn?over all test cases does not exceed?5?1055?105.
Output
For each test case, print the number of possible permutations?cc, modulo?109+7109+7.
Example
input
Copy
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
output
Copy
4 1 2 2 1 8 1 2 2
Note
In the first test case, there are?44?distinct permutation that can be made using the process:?[2,3,1,4,5,6,7][2,3,1,4,5,6,7],?[2,3,1,7,6,5,4][2,3,1,7,6,5,4],?[2,3,1,4,6,5,7][2,3,1,4,6,5,7],?[2,3,1,7,5,6,4][2,3,1,7,5,6,4].
In the second test case, there is only one distinct permutation that can be made using the process:?[1][1].
In the third test case, there are?22?distinct permutation that can be made using the process:?[6,5,2,1,4,3][6,5,2,1,4,3],?[6,5,3,1,4,2][6,5,3,1,4,2].
In the fourth test case, there are?22?distinct permutation that can be made using the process:?[1,2,8,7,4,3,6,5][1,2,8,7,4,3,6,5],?[1,6,4,7,2,3,8,5][1,6,4,7,2,3,8,5].
In the fifth test case, there is only one distinct permutation that can be made using the process:?[1,9,2,3,4,10,8,6,7,5][1,9,2,3,4,10,8,6,7,5].
思路：这个题是说根据c的要求将a与b能排列出多少种组合，在看题时就发现了一个可奇妙的东西，这个数确定出现过之后，在后面又出现就只能选另一个，另一个又去确定别的，它们似乎构成了环，其实就是构成了很多环，环中的一个确定，那么整个环就被确定了。那么难点来了怎样将它们变成环呢？有两种方法：1.并查集。2.邻接表。在一个环中，只要一个数确定，那么选法就被固定了；一个环中没有数固定，选择一对，那么是a的，要么是b的，也只有两种。当环的大小是1时，也就是自环，自己连自己，所以只能有一种选法。
先说并查集吧：并查集是解决元素分组问题的最简洁最优雅的数据结构之一。我们只要将上下的a b数组做链接就可以了，只要连接过的元素出现过就会接着将两块合并。没有出现过它俩就是1块。也就是将在别的地方出现的合到一块，这样就自然成了环。并查集在使用时标记的是它祖宗， 也就是好多操作都在使用查询操作，标记的都是祖宗节点
再来说邻接表：它是存图的，它是将一个数组当作下标指向另一数组的值的，这个倒没啥，特殊的在于它的遍历方式，他需要有一个数组记录出现没有，停止的时候是出现以前出现过的，这刚好不是接上了，成了环。遍历的时候是将当前的值作为下一个的下标处理的，这好像和并查集有点类似。他只要判断出现的数是否在C中出现过没有即可。环是只有单边的甚至是有指向性的，不会出现多边，不会出现一个点连多个边。 而邻接表不同，只需要分别标记每个点即可。
并查集：并查集分为3步：
1.初始化将自己的fa数组初始化为自己：
for(int i=1;i<=n;i++) fa[i]=i;2.插入，即合并。将有关系的合并成一个集合：
for(int i=1;i<=n;i++) fa[ff(a[i])]=ff(b[i]);3.查询，查询是否在一个集合，环，分组：
void ff(int x)
{
if(fa[x]==x) return x;
return fa[x]=ff(fa[x]);
}完整代码：
并查集：
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int mod=1e9+7;
const int N=1e5+10;
int a[N],b[N],c[N],fa[N],vis[N],sz[N];
int ff(int x)
{
if(fa[x]==x)return x;
return fa[x]=ff(fa[x]);
}
void solve()
{
int n;
cin>>n;
for(int i=1;i<=n;i++)fa[i]=i,vis[i]=0,sz[i]=0;
for(int i=1;i<=n;i++)cin>>a[i];
for(int i=1;i<=n;i++)cin>>b[i];
for(int i=1;i<=n;i++)cin>>c[i];
for(int i=1;i<=n;i++)fa[ff(a[i])]=ff(b[i]);
for(int i=1;i<=n;i++)vis[ff(c[i])]=1;
for(int i=1;i<=n;i++)sz[ff(i)]++;
for(int i=1;i<=n;i++)if(sz[ff(i)]==1)vis[ff(i)]=1;
int ans=1;
for(int i=1;i<=n;i++)
{
if(!vis[ff(i)])
{
ans=ans*2%mod;
vis[ff(i)]=1;
}
}
cout<<ans<<endl;
}
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t;
cin>>t;
while(t--)
{
solve();
}
return 0;
}邻接表：
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int mod=1e9+7;
const int N=1e5+10;
int a[N],b[N],c[N],p[N];
bool st[N],v[N];
void solve()
{
int n;
cin>>n;
for(int i=0;i<=n;i++) v[i]=st[i]=0;
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=1;i<=n;i++) cin>>b[i];
for(int i=1;i<=n;i++) cin>>c[i];
for(int i=1;i<=n;i++) p[a[i]]=b[i];
for(int i=1;i<=n;i++) if(c[i]) st[a[i]]=st[b[i]]=1;
int res=1;
for(int i=1;i<=n;i++)
{
if(!v[i])
{
int cnt=0;
bool flag=false;
for(int j=i;!v[j];j=p[j])
{
v[j]=1;
cnt++;
flag=flag|st[j];
}
if(cnt>=2&&!flag)res=res*2%mod;
}
}
cout<<res<<endl;
}
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t;
cin>>t;
while(t--)
{
solve();
}
return 0;
}
