子问题1

题意：

给定三个长度为 $n$ 的数组 $a,b,c$ ，$1\le a_i,b_i,c_i\le n$。两个人 $Alice$ 和 $Bob$ 分别拿数 $n$ 次，第 $i$ 次拿数时，两人从 { a i , b i , c i } \{a_i,b_i,c_i\} {ai​,bi​,ci​} 三个数中选择两个，每次拿数 $Alice$ 先手选择一个，拿完后 $Bob$ 从剩下的两个数中选择一个。问是否有 $Alice$ 的一种拿数选择，使得拿完后 $Bob$ 的数恰好是一个 $1-n$ 的排列。

数据范围：$1\le n\le 10^5$

题解：

首先，在每个位置 $Alice$ 拿完数后，至少有一个位置使得 $Bob$ 有两种选择（即剩下的两个数不相同），这样，$Bob$ 必然就可以有一种选择使得自己拿到的 $n$ 个数构不成排列。

证明：假设存在一种选择方式使得 $Bob$ 拿到的 $n$ 个数为一个排列。因为 $Bob$ 至少存在一个位置两个数不同，故找到这个位置，将数字换成另一个，此时 $Bob$ 选择的 $n$ 个数就构不成排列了。

因此，$Alice$ 拿完数后，每个位置剩下的数都得是两个相同的数 $x_i$，且 $x_i$ 各不相同，则 $Bob$ 选择的 $n$ 个数就是一个排列了，否则 $Bob$ 选择的 $n$ 个数至少有一种选择使得其不为排列。

代码：

#include <bits/stdc++.h>
using namespace std;void solve() {int n;cin >> n;vector<int> a(n), b(n), c(n);for (int i = 0; i < n; ++i) cin >> a[i], a[i] -= 1;for (int i = 0; i < n; ++i) cin >> b[i], b[i] -= 1;for (int i = 0; i < n; ++i) cin >> c[i], c[i] -= 1;vector<int> cnt(n);bool ok = true;for (int i = 0; i < n; ++i) {vector<int> vec = {a[i], b[i], c[i]};sort(vec.begin(), vec.end());if (vec[1] != vec[0] && vec[1] != vec[2]) {ok = false;break;} else {cnt[vec[1]] += 1;}}if (ok) {for (int i = 0; i < n; ++i) {if (cnt[i] == 0) {ok = false;break;}}}if (ok) cout << "YES\n";else cout << "NO\n";
}int main()
{ios::sync_with_stdio(false);cin.tie(nullptr);int T = 1;cin >> T;while (T--) solve();return 0;
}

子问题2

题意：

给定两个长度为 $n$ 的数组 $a,b$ ，$1\le a_i,b_i\le n$。需要构造一个长度为 $n$ 的数组 $c$，$1\le c_i\le n$。两个人 $Alice$ 和 $Bob$ 分别拿数 $n$ 次，第 $i$ 次拿数时，两人从 { a i , b i , c i } \{a_i,b_i,c_i\} {ai​,bi​,ci​} 三个数中选择两个，每次拿数 $Alice$ 先手选择一个，拿完后 $Bob$ 从剩下的两个数中选择一个。问是否有 $Alice$ 的一种拿数选择，使得拿完后 $Bob$ 的数恰好是一个 $1-n$ 的排列。

数据范围：$1\le n\le 10^5$

题解：
相较于子问题1，子问题2需要构造一个 $c$，满足 $Bob$ 拿的数恰好是一个 $1-n$ 的排列。

可以知道的是，如果 $a_i=b_i$，则 $c_i$ 为什么数都无所谓了。
如果存在 $a_i=b_i=a_j=b_j,i\ne j$，则无论怎么构造 $c$，$Bob$ 都有至少一种选择方式使得拿到的数构不成一个排列。

故我们现在面对的局面是，有 $k$ 个 $a_i=b_i$，且这 $k$ 个 $a_i$ 各不相同，其中 $0\le k\le n$。

对于剩下的 $n-k$ 个位置，其需要填充剩下的数，这里剩下的数是指除了 $k$ 个 $a_i$ 以外其他的数。

故我们需要思考的是如何在 $n-k$ 个位置填充剩下的 $n-k$ 个数，使得我们选择的一定是一个排列？

将问题转换为图论，对于 $a_i,b_i$，考虑在 $a_i$ 和 $b_i$ 之间连一条边。要确定这条边的方向，如果是从 $a_i$ 指向 $b_i$ ，表示选择 $b_i$，否则表示选择 $a_i$，我们需要对每条边都选择一个方向，使得每个点的入度都恰好为 $1$，对于 $a_i=b_i$ 的情况也可以一并操作。

由于一共 $n$ 个点，$n$ 条边，可能构成 $m$ 个连通分量。对于每个连通分量，其中的点数和边数必须相同，否则就没办法使得每个点的入度都为 $1$ 了。

故只需要建完图后，求每个连通分量的点数和边数是否相同即可。

即我们构造的 $c$ 满足 $c_i=a_i$ 或者 $c_i=b_i$ 即可。特殊地，对于 $a_i=b_i$ 时，$c_i\in [1,n]$。

代码：

#include <bits/stdc++.h>
using namespace std;constexpr int MOD = 998244353;void solve() {int n;cin >> n;vector<int> a(n), b(n);for (int i = 0; i < n; ++i) cin >> a[i], a[i] -= 1;for (int i = 0; i < n; ++i) cin >> b[i], b[i] -= 1;vector<int> p(n), points(n, 1), edges(n, 0);iota(p.begin(), p.end(), 0);auto getp = [&](int x) {int root = x;while (root != p[root]) root = p[root];while (x != p[x]) {int nx = p[x];p[x] = root;x = nx;}return root;};for (int i = 0; i < n; ++i) {int pa = getp(a[i]), pb = getp(b[i]);if (pa != pb) {points[pb] += points[pa];points[pa] = 0;edges[pb] += edges[pa];edges[pa] = 0;p[pa] = pb;} else {edges[pb] += 1;}}bool ok = true;for (int i = 0; i < n; ++i)if (i == getp(i)) {if (edges[i] != points[i]) {ok = false;break;}}if (ok) cout << "YES\n";else cout << "NO\n";
}int main()
{ios::sync_with_stdio(false);cin.tie(nullptr);int T = 1;cin >> T;while (T--) solve();return 0;
}

原问题

题意：

给定两个长度为 $n$ 的数组 $a,b$ ，$1\le a_i,b_i\le n$。需要构造一个长度为 $n$ 的数组 $c$，$1\le c_i\le n$。两个人 $Alice$ 和 $Bob$ 分别拿数 $n$ 次，第 $i$ 次拿数时，两人从 { a i , b i , c i } \{a_i,b_i,c_i\} {ai​,bi​,ci​} 三个数中选择两个，每次拿数 $Alice$ 先手选择一个，拿完后 $Bob$ 从剩下的两个数中选择一个。问：有多少种构造 $c$ 的方式，使得有 $Alice$ 的一种拿数选择，使得拿完后 $Bob$ 的数恰好是一个 $1-n$ 的排列。

数据范围：$1\le n\le 10^5$

题解：

在子问题 2 的基础上继续考虑。

对于每个连通分量，点数和边数相同。可以看成是一棵树加上一条边。

• 如果该连通分量中有自环边，那么这个自环边对应的点的其他边必然全是出边，该连通分量对应的方案数为 $1$。对于 $c_i$ 的选择呢？自环边对应的点可以任意选择，即 $n$ 个选择，其他边由于方向确定，故只有一种选择。
• 如果该连通分量中没有自环边，那么这个多的边会和树中的一些边构成一个环，这个环上的边使得每个点的入度都已为 $1$，剩余的边必然都是出边，该连通分量对应的方案数为 $2$。对于 $c_i$ 的选择呢？环边对应的点有两种选择，即环的两个方向。其他边由于方向确定，故只有一种选择。

代码：

#include <bits/stdc++.h>
using namespace std;constexpr int MOD = 998244353;void solve() {int n;cin >> n;vector<int> a(n), b(n);for (int i = 0; i < n; ++i) cin >> a[i], a[i] -= 1;for (int i = 0; i < n; ++i) cin >> b[i], b[i] -= 1;vector<int> p(n), points(n, 1), edges(n, 0);iota(p.begin(), p.end(), 0);auto getp = [&](int x) {int root = x;while (root != p[root]) root = p[root];while (x != p[x]) {int nx = p[x];p[x] = root;x = nx;}return root;};vector<int> self_loop(n);for (int i = 0; i < n; ++i) {int pa = getp(a[i]), pb = getp(b[i]);if (pa != pb) {points[pb] += points[pa];points[pa] = 0;edges[pb] += edges[pa] + 1;edges[pa] = 0;self_loop[pb] += self_loop[pa];self_loop[pa] = 0;p[pa] = pb;} else {edges[pb] += 1;}if (a[i] == b[i]) self_loop[pb] += 1;}bool ok = true;int ans = 1;for (int i = 0; i < n; ++i)if (i == getp(i)) {if (edges[i] != points[i]) {ok = false;break;}if (self_loop[i] == 0) ans = ans * 2 % MOD;else ans = 1ll * ans * n % MOD;}if (!ok) {cout << "0\n";return;} else {cout << ans << "\n";}}int main()
{ios::sync_with_stdio(false);cin.tie(nullptr);int T = 1;cin >> T;while (T--) solve();return 0;
}