Koxia and Game

发表于 分类于 ，

    Koxia 和 Mahiru 正在玩一个游戏。游戏使用 $a,b,c$ 三个长度为 $n$ 的数组，共进行 $n$ 轮。

    每一轮中，Koxia 先在 $a_i,b_i,c_i$ 中选择一个数字，Mahiru 再从未选择的两个数字中选择一个。

    如果 $n$ 轮后 Mahiru 选择的数字刚好包含 $1$ 至 $n$ 中每个数字各一个（即为 $1$ 至 $n$ 的一个排列），则 Koxia 获胜。否则，Mahiru 获胜。

    假设双方都采取最优策略，给定 $a,b$ 数组，求使得 Koxia 必胜的 $c$ 数组的个数。

Koxia and Game

Created by LXC on Wed Apr 24 20:43:54 2024

https://codeforces.com/problemset/problem/1770/D

ranting: 2000

tag: constructive algorithms, data structures, dfs and similar, dsu, flows, games, graph matchings, graphs, implementation

problem

Koxia 和 Mahiru 正在玩一个游戏。游戏使用 $a,b,c$ 三个长度为 $n$ 的数组，共进行 $n$ 轮。

每一轮中，Koxia 先在 $a_i,b_i,c_i$ 中选择一个数字，Mahiru 再从未选择的两个数字中选择一个。

如果 $n$ 轮后 Mahiru 选择的数字刚好包含 $1$ 至 $n$ 中每个数字各一个（即为 $1$ 至 $n$ 的一个排列），则 Koxia 获胜。否则，Mahiru 获胜。

假设双方都采取最优策略，给定 $a,b$ 数组，求使得 Koxia 必胜的 $c$ 数组的个数。

solution

看连通块的个数。连通块中边的个数必须等于点的个数。一个连通块只要没有自边，则有两种方式，否则是n种方式。乘法原理累乘。

code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77

#include <bits/stdc++.h>
// #define SINGLE_INPUT
#define ll long long
#define ull unsigned long long
#define N 500005
#define MOD 998244353
using namespace std;

random_device seed;
ranlux48 engine(seed());
int random(int l, int r) {
    uniform_int_distribution<> distrib(l, r);
    return distrib(engine);
}
template<class t,class u> ostream& operator<<(ostream& os,const pair<t,u>& p) {
    return os<<'['<<p.first<<", "<<p.second<<']';
}
template<class t> ostream& operator<<(ostream& os,const vector<t>& v) {
    os<<'['; int s = 1;
    for(auto e:v) { if (s) s = 0; else os << ", "; os << e; }
    return os<<']';
}
template<class t,class u> ostream& operator<<(ostream& os,const map<t,u>& mp){
    os<<'{'; int s = 1;
    for(auto [x,y]:mp) { if (s) s = 0; else os << ", "; os<<x<<": "<<y; }
    return os<<'}';
}

void sol() {
    int n;
    cin >> n;
    vector<int> a(n), b(n);
    for (auto& i:a) cin >> i, i--;
    for (auto& i:b) cin >> i, i--;
    vector<int> fa(n, -1), ce(n, 0), cv(n, 1), cy(n, 0);
    auto merge = [&](int x, int y) {
        ce[x] += ce[y];
        cv[x] += cv[y];
        cy[x] |= cy[y];
        fa[y] = x;
    };
    function<int(int)> ufind = [&](int x) {
        return fa[x] == -1 ? x : fa[x] = ufind(fa[x]);
    };
    for (int i=0; i<n; i++) {
        int fx = ufind(a[i]), fy = ufind(b[i]);
        if (fx != fy) merge(fx, fy);
        ce[fx]++;
        if (a[i] == b[i]) cy[ufind(a[i])] = 1;
    }
    ll ans = 1;
    for (int i=0; i<n; i++) {
        if (fa[i] != -1) continue;
        if (ce[i] != cv[i]) ans = 0;
        ans = ans*(cy[i] ? n : 2)%MOD;
    }
    cout << ans << "\n";
}

int main() {
    cout << setprecision(15) << fixed;
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
#ifndef SINGLE_INPUT
    int t;
    cin >> t;
    while (t--) {
        sol();
    }
#else
    sol();
#endif
    return 0;
}