1534-C, *1300

Problem - 1534C - Codeforces

문제

• $A \in \mathfrak{Mat_{\text{2, n}}}(\mathbb{N})$
• 행렬 A에서 같은 열이나 같은 행에 같은 수가 없는 상태를 solve 라고 한다
• solve 상태인 A가 주어졌을때 임의의 열의 두 수의 자리를 바꿔서 만들 수 있는 solve 상태 행렬의 수는?

 

$O(nlog\ n)$

1	2	3	4	5
2	1	4	5	3

위와 같은 solve 상태의 행렬 A가 주어졌다고 하자

첫번째 열을 바꾸면 첫 행에 2가 두개가 되므로 두번째 열도 바꿔야한다
이런식으로 동시에 바뀌어야 하는 열을 같은 집합으로 나타낸다면
$$S=\left \{ \left \{ A^{1},\ A^{2} \right \},\ \left \{ A^{3},\ A^{4},\ A^{5}\right \} \right \}$$

따라서 구하는 것은
$$2^{\left | S \right |} mod\ (10^{9}+7)$$

이를 구현하기 위해 union-find 알고리즘을 사용한다
path-compression 을 이용한 Find를 이용하여 $O(log\ n)$
n번 Union 한다 $O(nlog\ n)$

마지막으로 분할정복을 이용하여 $2^{\left | S \right |} mod\ (10^{9}+7)$을 구현한다 $O(log\ \left | s \right |)$

#include <bits/stdc++.h>
#define endl "\n"
#define loop(i, n) for(int i = 1; i <= n; i++)
using namespace std;
 
int n;
int arr1[400001] {};
int arr2[400001] {};
int parent[400001] {};
int mod = 1e9+7;
 
int Find(int a)
{
    if(parent[a] == a) return a;
    return parent[a] = Find(parent[a]);
}
 
void Union(int a, int b)
{
    int pa = Find(a);
    int pb = Find(b);
    parent[pa] = pb;
}
 
long long Pow(int base, int pow, int mod)
{
    if(pow == 1) return base;
    long long half = Pow(base, pow/2, mod);
    long long full = half*half;
    if(pow%2) return full*base%mod;
    else return full%mod;
}
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
 
    int t;
    cin >> t;
    while(t--){
        cin >> n;
        loop(i, n) cin >> arr1[i];
        loop(i, n) cin >> arr2[i];
        loop(i, n) parent[i] = i;
 
        loop(i, n) Union(arr1[i], arr2[i]);
 
        int djs_num = 0;
        loop(i, n){
            if(parent[i] == i) djs_num++;
        }
 
        cout << Pow(2, djs_num, mod) << endl;
    }
 
    return 0;
}cs