• 欢迎光临~

# Good Bye 2022: 2023 is NEAR

## D. Koxia and Game

``````1 2 3
1 2 3
``````

(1)

``````1 2 1
1 3 1
``````

(2)

``````3 3 1
3 3 1
``````

(1)

``````1 2 3
1 2 3
``````

(2)

``````1 2 2
1 3 3
``````

(1) 贡献为 (3)，会发现第 (2)(3) 两个位置直接数字 (2,3) 二选一就行了。
(2,3) 两个成环，当 (i=2) 时，将 (a_2)(b_2) 双向边连起来，当 (i=3) 时，将 (a_3)(b_3) 双向边连起来，这时数字 (2)(3) 就是一个环，那么可以知道整个环贡献是 (2)

(3)

``````4
1 3 3 4
2 3 4 4
``````

``````3
1 2 3
1 3 3
``````

``````#include "bits/stdc++.h"

using namespace std;
using i64 = long long;

constexpr int M = 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]--;
}
for (int i = 0; i < n; i++) {
cin >> b[i];
b[i]--;
}
vector<bool> vis(n);
for (int i = 0; i < n; i++) {
if (a[i] == b[i]) {
if (vis[a[i]]) {
cout << 0 << 'n';
return;
}
vis[a[i]] = 1;
}
}
vector<vector<int>> g(n);
for (int i = 0; i < n; i++) {
g[a[i]].push_back(b[i]);
g[b[i]].push_back(a[i]);
}
for (int i = 0; i < n; i++) {
if ((int) g[i].size() == 0) {
cout << 0 << 'n';
return;
}
}
vis.assign(n, 0);
i64 ans = 1;
for (int i = 0; i < n; i++) {
if (a[i] == b[i]) {
ans = ans * n % M;
}
}
for (int i = 0; i < n; i++) {
if (vis[i]) {
continue;
}
int add = 2;
int cnt1 = 0, cnt2 = 0;
function<void(int)> dfs = [&](int cur) {
vis[cur] = 1;
cnt1++;
for (auto x : g[cur]) {
if (cur == x) {
}
cnt2++;
if (!vis[x]) {
dfs(x);
}
}
};
dfs(i);
if (cnt1 * 2 != cnt2) {
cout << 0 << 'n';
return;
}
ans = ans * add % M;
}
cout << ans << 'n';
}

int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int tt = 1;
cin >> tt;
while (tt--) {
solve();
}
return 0;
}
``````