Codeforces Round 788 (Div. 2)——C. Where is the Pizza?

思路讲解（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 中选取。

2. 将这个分组对应的所有元素都从 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

源代码

// 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……）