一、題目

1、題目描述

2、輸入輸出

2.1輸入

2.2輸出

3、原題鏈接

1670C - Where is the Pizza?

---

二、解題報告

1、思路分析

考慮兩個數組a，b的每個位置只能從a，b中挑一個

不妨記posa[x]為x在a中位置，posb同理

我們假如位置i挑選a[i]，那么會產生連鎖反應：

posb[a[i]]處不能選b，只能選a，繼而

postb[a[posb[a[i]]]] 處也不能選 b了，只能選a

...

由于是排列，最終一定會回到a[i]

也就是說我們在一個位置處選a或b可以得到1個環，而選a或者選b得到的環上元素的下標是一致的，不過得到的排列是兩個排列

也就是說，對于一個長度大于1的環（長度為1只能得到一種排列），我們有兩種選擇

對于本題，我們計算所有大于1且不含非0d[i]的環的數目cnt，答案就是2 ^ cnt mod 1e9+7

2、復雜度

時間復雜度： O(N)空間復雜度：O(N)

3、代碼詳解

??

#include <bits/stdc++.h>
using i64 = long long;
using i128 = __int128;
using PII = std::pair<int, int>;
const int inf = 1e9 + 7, P = 1e9 + 7;struct UnionFindSet {std::vector<int> p;int n;UnionFindSet(int _n) : p(_n, -1), n(_n) {}int find(int x) {return p[x] < 0 ? x : p[x] = find(p[x]);}void merge(int x, int y) {int px = find(x), py = find(y);if (px == py) return;if (p[px] > p[py]) std::swap(px, py);p[px] += p[py], p[py] = px;}int size(int x) {return -p[find(x)];}};int power (int a, i64 b, int p) {int res = 1;for (; b; b >>= 1, a = 1LL * a * a % p)if (b & 1)res = 1LL * res * a % p;return res;
}void solve() {int n;std::cin >> n;std::vector<int> a(n), b(n), d(n), posa(n), posb(n);for (int i = 0; i < n; i ++ ) std::cin >> a[i], posa[-- a[i]] = i;for (int i = 0; i < n; i ++ )std::cin >> b[i], posb[-- b[i]] = i;for (int i = 0; i < n; i ++ )std::cin >> d[i], -- d[i];UnionFindSet ufs(n);for (int i = 0; i < n; ++ i)ufs.merge(i, posb[a[i]]);std::unordered_set<int> st;for (int i = 0; i < n; ++ i)if (ufs.size(i) > 1)st.insert(ufs.find(i));for (int i = 0; i < n; ++ i)if (~d[i])st.erase(ufs.find(i));std::cout << power(2, st.size(), P) << '\n';
}int main(int argc, char** argv) {std::ios::sync_with_stdio(false), std::cin.tie(0), std::cout.tie(0);int _ = 1;std::cin >> _;while (_ --)solve();return 0;
}