Codeforces Round 788 (Div. 2)——C. Where is the Pizza? · znzryb
## 思路讲解（gemini翻译的题解）
---
首先，我们来解决一个简化版的问题，即假设数组 `d` 中全是 `0`（换句话-说，对于需要形成的排列 `c` 没有任何预设的限制）。
我们假设排列 `a` 为 `[1,2,3,4]`，排列 `b` 为 `[3,1,2,4]`。
假设我们已经选择了数组 `c` 的第一个元素为数组 `a` 的第一个元素（即 `c[0] = a[0] = 1`）。这样一来，我们就不能选择数组 `b` 的第一个元素了（`b[0] = 3`）。由于我们希望数组 `c` 是一个完整的排列，那么数字 `3` 就必须在 `c` 中出现，所以我们必须从数组 `a` 中找到 `3` 并将其加入到数组 `c` 中。
我们在数组 `a` 中寻找 `3`，发现它在索引 `2` 的位置（`a[2]=3`），于是我们选择 `c[2] = a[2] = 3`。这个选择导致我们不能再选择 `b` 中对应索引的元素（即 `b[2]=2`）。因此，我们又必须从 `a` 中找到 `2` 并加入 `c`。我们在 `a` 中找到 `2` 在索引 `1` 的位置（`a[1]=2`），所以选择 `c[1] = a[1] = 2`。这次，`b` 在该索引对应的元素是 `1`（`b[1]=1`），而 `1` 已经因为我们最初的选择被包含在数组 `c` 中了。这样，我们就不再被强制要求从 `a` 中选择新的元素了，形成了一个闭环。
我们观察到，我们最初选择的元素 `1`，以及之后被“强制”选择的元素 `2` 和 `3`，即 `[1,3,2]`（按选择顺序），与它们在 `b` 数组中对应位置的元素 `[3,2,1]` 构成了相同元素的排列。这些元素形成了一个“分组”。对于每个大小超过 `1` 的分组，我们都有 `2` 个选择：
1. 将这个分组对应的所有元素都从 `a` 中选取。
1. 将这个分组对应的所有元素都从 `b` 中选取。
所以，这个简化版问题的答案就是：找出所有这样相互关联的分组，统计其中大小超过 `1` 的分组数量（我们称之为 `p`），最终答案就是 2p。
---
### **那么，如果数组** **`d`** **不全是** **`0`** **该怎么办呢？**
这种情况我们只需要在之前的逻辑上增加一个约束。对于我们找到的每一个分组，我们必须检查其所有成员在 `d` 数组中对应的位置是否全为 `0`。
- **如果一个分组对应的所有** **`d`** **数组位置上的值都是** **`0`**，那么这个分组就有两种选择（要么全选 `a`，要么全选 `b`），对最终答案的贡献是乘以 `2`。
- **如果一个分组中，哪怕只有一个成员在** **`d`** **数组中对应的位置不为** **`0`**（意味着这个位置的选择已经被 `d` 数组固定了），那么整个分组的选择也就被唯一确定了，它只有一种选择方案。这种分组对最终答案的贡献是乘以 `1`，我们就不需要把它计入 `p` 中。
这个解法可以通过多种方式实现，但在我看来，**使用并查集（Disjoint Set Union, DSU）**来将每个分组的元素合并在一起，是实现这个逻辑最优雅的方式。
## AC代码
[https://codeforces.com/contest/1670/submission/330958420](https://codeforces.com/contest/1670/submission/330958420)
::: 源代码
```cpp
// Problem: C. Where is the Pizza?C. 披萨在哪里？
// Contest: Codeforces - Codeforces Round 788 (Div. 2)
// URL: https://codeforces.com/contest/1670/problem/C
// Memory Limit: 256 MB
// Time Limit: 1000 ms
// by Gospel_rock
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define pb push_back
#define EB emplace_back
#define EM emplace
#define FI first
#define SE second
#define SZ(a) ((int) a.size())
#define FOR(i, a, b) for (long long i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (long long i = (a); i >= (b); --i)
#define debug(var) cerr << #var <<":"<<var<<"\n";
#define cend cerr<<"\n-----------\n"
#define lson(var) (var<<1)
#define rson(var) ((var<<1)+1)
#define fsp(x) fixed<<setprecision(x)
using namespace std;
using ll = long long;using ull = unsigned long long;
using DB=double;using LD=long double;
// using i128 = __int128;
using pdd = pair<DB,DB>;using plb = pair<ll,bool>;
using pll = pair<ll,ll>;using vll=vector<ll>;using vb=vector<bool>;
using tll = tuple<ll,ll,ll>;
using vpll = vector<pll>;using vtll = vector<tll>;
using arr3 = array<ll,3> ;using arr2 = array<ll,2>;
constexpr ll MAXN=(ll)1e5+10,INF=(ll)1e17+9; // 1e18+9也是素数
constexpr ll mod=(ll)1e9+7;
constexpr double eps=1e-8;const double pi=acos(-1.0);
ll N,M,Q,X,K,T,lT,A[MAXN],B[MAXN],C[MAXN];
inline void __();
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>lT;
while(lT--)
__();
return 0;
}
/*
*/
ll posa[MAXN],posb[MAXN];
bool vis[MAXN];
struct DSU { // 并查集
vector < int > fa, siz;
int ln;
DSU(int n) {
ln = n;
fa.resize(ln + 5, 0), siz.resize(ln + 5, 0);
FOR(i, 1, n) {
fa[i] = i;
siz[i] = 1;
}
}
int find(int x) {
while (fa[x] != x) {
x = fa[x];
fa[x] = fa[fa[x]];
}
return x;
}
bool same(int x, int y) {
return find(x) == find(y);
}
bool merge(int x, int y) {
x = find(x);
y = find(y);
if (x == y) {
return false;
}
siz[x] += siz[y];
fa[y] = x;
return true;
}
int size(int x) {
return siz[find(x)];
}
int countFa() {
int res = 0;
FOR(i, 1, ln) {
if (fa[i] == i) ++res;
}
return res;
}
};
ll binpow(ll a,ll k,const ll &p=mod){ // 迭代快速幂
ll res=1;
a%=p; // 防止a*a溢出
while(k>0){
if((k&1)==1) res=a*res%p;
a=a*a%p;
k>>=1;
}
return res;
}
inline void __(){
cin>>N;
DSU fa(N);
FOR(i,0,N+5){
vis[i]=0;
}
vector<vector<ll> > g(N+5);
FOR(i,1,N){
cin>>A[i];
posa[A[i]]=i;
}
FOR(i,1,N){
cin>>B[i];
posb[B[i]]=i;
}
FOR(i,1,N){
cin>>C[i];
}
if(N==0){
cout<<0<<"\n";return;
}
FOR(i,1,N){
if(vis[i]) continue;
ll idx=posa[i];
while(!vis[A[idx]]){
fa.merge(A[idx],B[idx]);
vis[A[idx]]=true;
idx=posa[B[idx]];
}
}
vb viss(N+5);
ll ans=1;
FOR(i,1,N){
ll pa=fa.find(i);
if(viss[pa]) continue;
viss[pa]=true;
if(fa.size(i)>=2){
ans*=2;
ans%=mod;
}
}
vector<ll> wp;
FOR(i,1,N){
if(C[i]==0) continue;
wp.pb(fa.find(C[i]));
}
sort(all(wp));wp.resize(unique(all(wp))-wp.begin());
ll inv2=binpow(2,mod-2);
FOR(i,0,SZ(wp)-1){
ll rt=wp[i];
if(fa.size(rt)>=2){
ans*=inv2;
ans%=mod;
}
}
cout<< ans <<"\n";
}
/*
AC
https://codeforces.com/contest/1670/submission/330958420
*/
```
:::
## 心路历程（WA，TLE，MLE……）