C. Little Alawn‘s Puzzle-Codeforces LATOKEN Round 1 (Div. 1 + Div. 2)-并查集判环与快速幂

110 阅读 0 评论 73 点赞

我是靠谱客的博主漂亮睫毛膏，最近开发中收集的这篇文章主要介绍C. Little Alawn‘s Puzzle-Codeforces LATOKEN Round 1 (Div. 1 + Div. 2)-并查集判环与快速幂，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题目链接Problem - 1534C - Codeforces

C. Little Alawn's Puzzle

time limit per test

2.5 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

When he's not training for IOI, Little Alawn enjoys playing with puzzles of various types to stimulate his brain. Today, he's playing with a puzzle that consists of a 2×n2×n grid where each row is a permutation of the numbers 1,2,3,…,n1,2,3,…,n.

The goal of Little Alawn's puzzle is to make sure no numbers on the same column or row are the same (we'll call this state of the puzzle as solved), and to achieve this he is able to swap the numbers in any column. However, after solving the puzzle many times, Little Alawn got bored and began wondering about the number of possible solved configurations of the puzzle he could achieve from an initial solved configuration only by swapping numbers in a column.

Unfortunately, Little Alawn got stuck while trying to solve this harder problem, so he was wondering if you could help him with it. Find the answer modulo 109+7109+7.

Input

Each test contains multiple test cases. The first line contains the number of test cases tt (1≤t≤1041≤t≤104). Description of the test cases follows.

The first line of each test case contains a single integer nn (2≤n≤4⋅1052≤n≤4⋅105).

The next two lines of each test case describe the initial state of the puzzle grid. Each line will be a permutation of the numbers 1,2,3,…,n1,2,3,…,n and the numbers in each column and row will be pairwise distinct.

It is guaranteed that the sum of nn over all test cases does not exceed 4⋅1054⋅105.

Output

For each test case output a single integer, the number of possible solved configurations of the puzzle Little Alawn can achieve from an initial solved configuration only by swapping numbers in a column. As the answer can be very large, please output it modulo 109+7109+7.

The answer for each test case should be on a separate line.

Example

input

Copy

2
4
1 4 2 3
3 2 1 4
8
2 6 5 1 4 3 7 8
3 8 7 5 1 2 4 6

output

Copy

2
8

Note

The two possible puzzle configurations for example 11 are:

[1,4,2,3][1,4,2,3] in the first row and [3,2,1,4][3,2,1,4] in the second;
[3,2,1,4][3,2,1,4] in the first row and [1,4,2,3][1,4,2,3] in the secon
---------------------------------------------------------------------------------------------------------------------------

题目首先已经说明，不能有相同的在同一列或者同一行，同一行满足条件可以通过移动列的两个元素来实现，但是同一列相同时无论如何也形成不了，所以言外之意题目也根本不会给你列上元素相同的情况。

我们模拟这一过程

2 6 5 1 4 3 7 8
3 8 7 5 1 2 4 6

我们如果想要完成3 2的交换，必须同时移动红色的，68同理

如果我们想交换5 7我们必须移动74又必须移动41，还必须移动15

所以我们可以把操作时移动某一个牵扯到的全部元素加入并查集的环中，环中的每一个元素想要换位置，必须同时全部移动全部元素，且不同元素交换后，结果相同。

那么我们就相当于有了三个大元素，题目并没有要求我们求交换方案数，而是结果方案数，每一个环中元素无论哪一个交换，最后结果肯定是全部交换。所以最后结果方案数就是2^cnt个，表示每个环交换与否罢了。另外输入时就已经保证了条件满足，所以全部不交换也是可以的。否则刚开始就存在不满足条件的，我们无法计算。

# include<iostream>
# include<algorithm>
# include<iomanip>
# include<vector>
# include<map>
# include<math.h>
# include<cstring>
using namespace std;
typedef long long int ll;
int f[400000+10];
int a[400000+10],b[400000+10];
int getf(int x)
{
if(x==f[x])
return f[x];
else
{
f[x]=getf(f[x]);
return f[x];
}
}
ll mod=1e9+7;
ll quickpow(ll base,ll pow)
{
ll ans=1;
while(pow)
{
if(pow&1)
ans=ans*base%mod;
pow>>=1;
base=base*base%mod;
}
return ans%mod;
}
int main()
{
int t;
cin>>t;
while(t--)
{
int n;
cin>>n;
for(int i=1;i<=n;i++)
f[i]=i;
for(int i=1;i<=n;i++)
cin>>a[i];
for(int j=1;j<=n;j++)
cin>>b[j];
for(int i=1;i<=n;i++)
{
int t1=getf(a[i]);
int t2=getf(b[i]);
if(t2!=t1)
f[t2]=t1;
}
ll cnt=0;
for(int i=1;i<=n;i++)
{
if(f[i]==i)
cnt++;
}
cout<<quickpow((ll)2,cnt)<<'n';
}
return 0;
}